問題の読み方
- 問題文は音読をする。
- 制約はちゃんと見る
- mod が書いてあったらすぐソースコードに書く
- 入力例1、出力例1に書いてある説明を理解する
- (入力例1の出力が出力例1になることをだけを確認すると、たまに誤解していても通ってしまうことがある）
- 他の入力例にも目を通す
考察の仕方
- 愚直を考える
- 簡単な問題を考える
- 小さな値で実験をしてみる
- 見方を変える
- 主客転倒（for ループの順序交換）
- 補集合を考える
- 後ろから考える
- 直和分解
- 最大化問題はその値を達成可能か考える
- 決め打ち二分探索
- 最適化問題を判定問題に帰着させる
- 条件を言い換える
- なにか知ってる典型を使う
- ありえそうな解法を列挙する
- なにかアイデアが浮かんだら、「本当にそれで大丈夫」かを検証する（自問する）
- 形式的な証明をすることが望ましい。
- できない場合でも大丈夫だと自分で納得できるくらいには考えるほうがよい。
- 大丈夫でない例
- 特定のサンプルでしか成り立っていなかった（サンプルに引っ張られすぎ）
- 条件が不足していた。他にも考えるべき対象があった。
- なにかアイデアが浮かんだたら、他にいいアイデアがないかを考える
- 方針が立ったら、サンプルを見て検証をする
- ただし、サンプルが弱い場合もあるので、注意。抽象と具体を行き来するイメージで検証をする。
- 部分問題に関しても主問題と同様に上記の考察をする
- ボツ案
考察が詰まったとき