TopCoderのDPのチュートリアルを、半分くらい読みました。

Dynamic Programming: From novice to advanced

ポイントは、

• 状態の定義。状態とは、部分問題。
• 各状態間の関係のモデル化。j

練習問題

• ZigZag - 2003 TCCC Semifinals 3
• BadNeighbors - 2004 TCCC Round 4
• FlowerGarden - 2004 TCCC Round 1

敗北です。実力不足でした。以下敗因分析。

• 理論、定石の不足。DPとかグラフとか、知っていればできそうだという問題がいくつかあった。さっと書けるようになるくらい、理解して慣れておく必要がある。
• スピード不足。特に以下の2点。
  • デバッグに時間がかかる。バグが入りにくい奇麗な書き方が必要。
  • 他言語の経験不足。gcjは何を使って解いても良い。例えばRound1BのDecision TreeなんかはS式のパーサを書くのがメインの問題なので、lisp系の言語を使えばすぐにできたと思う。c/c++以外はまだ調べながらじゃないとかけない。また、適材適所で言語を使えることは、こういうコンテストだけじゃなく日常でも役立つと思う。
• 実装力の不足。具体的には、複雑なアルゴリズムを考えられない。これは経験で補えると思う。たくさんコーディングを続けるうちに、イディオムや定石が手癖のように溜まっていく。そうすることで、瑣末な部分に脳のリソースを割かずに、難しい部分を集中して考えることができるようになる、と思う。

今後の対策は、

• とりあえずTopCoderのチュートリアルをやる。今まではただ過去問を順に解いていたけど、こっちのほうが効率がいいと思う。
• 別の言語をやる。とりあえず途中で止まっているGaucheを再開するのがいいかな。
• ひたすら書く。非コンテストな日常のコーディング含め。