ここ数日でやったこと

6,006で学んだDynamic Programmingを適用する手続きを実際に試してみたくてAOJの問題をいくつかやってみた。

典型問題リストらしき位置にあるけども、講義で扱っていた問題よりも1ランクレベルが高い。ただ多項式時間に落とすだけでは足りなくて、もう一工夫して計算量を落とす必要があったり(Coin Changing, Knapsack, LIS)、そもそもうまい部分問題を見つけるのが難しかったり(Traveling Salesman)する。

経路問題としてグラフを描いてみると、グラフの対称性から時間/空間計算量を落とせる部分が見つかってなるほどという感じがある。

LISのO(NlogN)とかのものは自分で思いつける気がしないし、経路問題としてみた時にO(N^2)のものからどういう工夫をしているのかという意味付けがまだ見出だせていない。O(NlogN)のアルゴリズムに関してはここが参考になった。

1問1問結構な時間がかかってしまうが、基本的な考え方を身につけてから試してみると楽しいんだなぁ。
もっと問題やってみたい。

雑感

あまり時間を有効に使えていない。最近勉強が楽しくて時間が惜しい。