アルゴリズムコンテストの勘所

contest

一度も書いたことが無いと意外と手こずる、再帰的な/再帰的に問題をシラミ潰す方法… 深さ優先探索, 幅優先探索, 分割統治法, メモ化, 動的計画法 … はひととおり把握しておいた方がよいかも。

d.y.d - アルゴリズムコンテストの挑み方

そうですね！　そこが今の自分の課題です。たぶんそれぞれの方法は一回以上書いたことあるけれども、そういう手法だと意識して使ってはいなくて、典型的パターンとして自分の中に蓄積されていません。だから現状では勘とひらめきだけで考えることになって、慣れている人には一瞬な問題でも、方針を立てるまでにけっこうな時間を食ってしまう。
なので、基本的な手法をすぐ頭の中の道具箱から出してこれるようになると、けっこう伸びそうな気がしています。


そしてさらにもうワンステップのためには、上で引用した各種手法とか、引用元記事で言及されてる計算量の概算とかに加えてきっとこういったことが必要。

  • 高校数学は一通りしっかり理解しておく
  • 問題文を正確に読み取れる（素早く読めることよりもこちらが大事かなと。題意を取り違えたら大打撃なので）
  • いざコーディングするときに凡ミス連発しない

このへんが抑えられてると、TopCoderで言ったらレート2000、Google Code Jamだと上位500人（ローカルオンサイト進出）程度までは行けるのではないでしょうか。大学の専門課程で習うほどのアルゴリズムの知識がなくてもたぶん大丈夫。自分がそこまで達してないので説得力ないですが…。あと1年くらいのうちにそのレベルに到達することを目標としています。


自分の場合だと、このリストの上2つはまずまず大丈夫だと思うけど、3つめがかなり怪しくてネックになっている感じです。けど、どうなんだろ。やっぱり上位の人になるほど、コーディング時のイージーミスは少ないものなのでしょうか？