14 September 2009

Dynamic Programming: From novice to advanced

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

Dynamic Programming: From novice to advanced

ポイントは、

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

練習問題

Google Code Jam 敗北

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

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

今後の対策は、

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