Skip to content

Instantly share code, notes, and snippets.

@hamadu
Created November 15, 2012 06:19
Show Gist options
  • Save hamadu/4076944 to your computer and use it in GitHub Desktop.
Save hamadu/4076944 to your computer and use it in GitHub Desktop.
問題が解けないとき/20分経っても方針が見えないならここを見る。
20分経っても方針が見えないならここを見る。数字が小さいほど優先度高い。
1. 問題文に見落としはないですか
- そもそもちゃんと問題読んだ?別の問題を解こうとしてない?
-- 似た問題を解いたことがある場合は特に注意する。
- 制約条件はちゃんと読みましたか
-- 指数時間のアルゴリズムで間に合ったりしない?
-- グラフは特殊な形をしてませんか
--- 木だったり、閉路の数だったり
--解けるものを「解けない」と勘違いしてませんか
--- O(n^4) なら 50ぐらいまでなら大丈夫。これはTopcoderでは頻出のサイズ。
--- O(nlogn) なら 1000000(10^6) が解ける。
2. 例示は理解の試金石
- サンプルを手で解いてみましたか
- 問題の理解と、サンプルの答えは合致してますか
-- 違うなら、おそらく問題を読み間違えてる。1に戻る
3. 発想の転換
- 固定するものを変えてみる
- 最終状態から逆に処理するとうまく行ったりしない?
- 実は2部グラフかも・・・(グリッドの場合は特に注意する)
- もらうDP ⇔ 配るDP  書き換えてみるとうまくいくかも
- 一旦、もらうDPの形でナイーブなDPを書きだしてみる。更新部分を効率良く処理できないか?
-- 区間の最小値なら -> SegTree
-- 区間の和なら -> BIT
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment