問題が解けないとき/20分経っても方針が見えないならここを見る。

helpme.txt

20分経っても方針が見えないならここを見る。数字が小さいほど優先度高い。

1. 問題文に見落としはないですか
- そもそもちゃんと問題読んだ？別の問題を解こうとしてない？
-- 似た問題を解いたことがある場合は特に注意する。
- 制約条件はちゃんと読みましたか
-- 指数時間のアルゴリズムで間に合ったりしない？
-- グラフは特殊な形をしてませんか
--- 木だったり、閉路の数だったり
--解けるものを「解けない」と勘違いしてませんか
--- O(n^4) なら 50ぐらいまでなら大丈夫。これはTopcoderでは頻出のサイズ。
--- O(nlogn) なら 1000000(10^6) が解ける。

2. 例示は理解の試金石
- サンプルを手で解いてみましたか
- 問題の理解と、サンプルの答えは合致してますか
-- 違うなら、おそらく問題を読み間違えてる。1に戻る

3. 発想の転換
- 固定するものを変えてみる
- 最終状態から逆に処理するとうまく行ったりしない？
- 実は2部グラフかも・・・（グリッドの場合は特に注意する）
- もらうDP ⇔ 配るDP 　書き換えてみるとうまくいくかも
- 一旦、もらうDPの形でナイーブなDPを書きだしてみる。更新部分を効率良く処理できないか？
-- 区間の最小値なら -> SegTree
-- 区間の和なら -> BIT