TopCoder

565 ：デフォルトの名無しさん：2008/08/17(日) 00:43:25

>>562
うーん、それは俺も常日頃思ってることだな。
上位陣が問題解くときの頭の中を見てみたい。
少なくとも俺が知る限りじゃそれらが詳しく書いてある本とかサイトはないねー。
だからとぷこだに参加してる人の参加日記とかを読んでどうにかそこから見出すようにしてる。

>>563
それそれ、その方法。

いきなりピンポイントにオーダー求めて解法探すのは無理だから、俺は大体
1. 最低限必要なオーダーを考える。
2. そのオーダー以内で探索、既存のアルゴリズムが適用できるなら適用する。
（つまりBFS 、DFS 、とかで十分解ける問題なら2.の時点で解けることになる。）
3. 問題の性質から全探索するとどのくらいのオーダーになるか考える。
4. 指数時間的に爆発するけど、重複削除やメモが有効そうならメモ化したときのオーダーを考え、いけそうならそれで解く。
(この時点で、DFS+メモ、BFS+メモ、メモ化探索的な意味合いでのDPは解ける。）
5. 3.の考察でDPっぽいなと感じたらDP解をひたすら探す。（あえて分けていうとテーブルDP的な問題）
6. ここまできたら恐らく過去に類題を解いたことのない、未経験な問題、数学的要素が大きい問題、
実は1〜5に当てはまるべき問題だけど、自分の力不足でわからなかった問題ってことが多いからもう新しい気持ちで挑むかひらめきを待つ。

こんな感じ。