AOJでHaskell: 1188 階層民主主義 (Hierarchical Democracy)

こんにちはtatsyです。

今日はHaskellの勉強を兼ねてAOJの関数型向きっぽい問題をやってみます。やる問題は1188番の階層民主主義という問題です。
 

問題の内容


入力は[[123][4567][89]]のようなかっこで区切られた文字列です。この中身は有権者の人数を表していて、この半分以上を取ればこの地区で勝利できます。

上の入力例ではかっこで囲まれた数字が3個ありますが、候補者はこの3個のうちの半数以上で勝利すれば当選です。なので、上の例では123の半分である62と89の半数である45の合計である107が当選に必要な最小票数ということになります。

上の例では階層が2つだけでしたが、実際の入力はこれが複数の層になっています。
 

解法


問題自体はそれほど難しくないので解法はすぐ思いつきそうです。単純に考えれば、かっこで囲まれた範囲を再帰的に展開して、下から計算をしていけばいいだけです。

なので、C++とかでやるのであれば、かっこで囲まれた同階層の内容をsplitする関数を書いて、splitされた各要素を計算する関数を呼び出せばよさそうです。

それで書いた解答がこちらになります。

単純ですね。でも、これを関数型でやろうとすると、案外に文字列を分割する処理が面倒そうです。

上のC++のコードでは、かっこを左から順にみていって[が出てきたら1を足して、]が出てきたら1を引くという処理を行い、この数が0になったところで文字列を分割しています。

HaskellでもSTモナドとか使えばできると思いますが、あまりエレガントじゃないですし、そもそも関数型の勉強にならないので、再帰関数で考えてみます。

基本的な考え方として[が出てきたら、新しい階層に入ったと見なして、再帰関数を1つ下に下ります。各再帰関数は現れた数字を保存しておくstackのようなものを持たせておいて、]が現れたらstack内に積まれた数字の小さいもの半分の合計を上に返すようにします。

と、さらっと書きましたが、結構考えるのに時間かかりました(笑)。実装したコードは次のようになります。

再帰関数を工夫した分だけコードの量は短くなってますね。

自分なりには結構エレガントなんじゃないかと思います。が、C++のやり方の方が直感的に分かりやすいというのは否定できないですね。

こういう再帰関数を使った書き方がささっと思いつくようになるといいなぁと思います。

というわけで内容がないですが、これで今回の記事を終わります。

お読みいただきありがとうございました。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください