HaskellでDP(動的計画法)に向けて - Study : Google Code Jam 2009 - Round 1-C Problem C

Haskellって、一度ある引数で計算した関数を同じ引数で呼ぶと再度計算しちゃうんですね。
せっかく参照透明なんだから覚えてくれててもよさそうなもんだけど。
全部おぼえたらメモリが爆発するかもだから、関数定義で再計算の可能性があると宣言すると
覚えてくれるとかならないものでしょうかね。

プログラムコンテストではDPを使わないと計算量が爆発する問題がよく出るということで
Haskellではどうするのだろうと試してみました。

Wikipediaを参考にControl.Monad.STとData.Mapを使ったメモ化の実装をしてみました。

題材はGCJ2009 Round1Cの問題Cです。
下記のコードで、Largeサイズの解答に約16秒でした。

しかし型がやたらにややこしいですね。
また[Monad m a]から[a]を取り出すのにハマってしまいました。。。

ロジックを考えるよりも型エラーを取るほうに、まだまだ四苦八苦しています。

ちなみに問題を解くアルゴリズムの本体は53行目以降です。
そこまでは標準入力からの読み込みとメモ化の道具のライブラリとなっています。

再帰の際に「withMemo (Memo r) f」を書いているのがイマイチかも。

タグ：動的計画法 DP Haskell gcj Google Code Jam