動的計画法のおさらい

平日の夜に久しぶりに AtCoder の過去問をやったら、 DP Table の問題に思いがけずつまずいてしまった。自意識としてはなんども転んでいいかげん克服できたつもりでいたので、またしても同じ壁にはねかえされてしまったことが悔しく、この土曜日は丸一日を復習にあてた。

別の機会にアルゴ式というサービスがあるのを知り、眺めてみると動的計画法のおおきなセクションがある様子であったので、いいタイミングとおもってこれを活用させてもらった。「動的計画法ってなに？」というところからはじまって、懸念の二次元動的計画法をカバーしたうえで、ナップサック問題につながる。これをひととおりやった。

やってみると、心配していたとおり、手が止まってしまう場面がちらほらあった。しかも序盤のほうでのこと。過ぎてみれば、愚直な解を作る前から最適解を考え始めているようなところがあり、そのうえようやく愚直解にたどりついてみると、そのままでじゅうぶん制約を満たせているような有様なので、たちが悪い。頭が先走ってしまっている。多重ループや条件分岐を過剰に嫌って自縄自縛しているようなところがある。平たくいうと、勘を失っている。

序盤の壁を超えて、ナップサック問題にたどりつくころには手もすらすら動くようになった。しばらくコンテスト参加の間もあいており、瞬発力がなくなっているし、慣れもなくしている様子。ひとまずは回復できたような気はするが、それも一時的なものとおもうとこころもとない。

続けて AtCoder の Educational DP Contest の問題を解いた。アルゴ式を流したあとだと、さすがにそれなりに解ける。結局は手を動かさないとだめということらしい。しかしこうしてリブートしてみてもやがて記憶が枯れるのだとおもうと切ない。ティーンの頃にもっとやれていれば、とつい頭によぎってしまうが、結局のところは気づいたときにやるしかないわけで、気づく機会をこうして持てたことこそ幸運であった。

夕食にふるさと納税で届いた高知のうなぎを食べた。