※ほぼ自分用
ゲーム
このようなよくわからないゲームにも最善手というものは存在します。 基本的にゲームは真似っ子戦略や、Nim, Grundy数を考えるとよいです。 また、再帰やDPで、現在の状態からスタートすると勝ち・負けを判断できるようにすることもありますね。
上に貼ったような問題は、適切な場合分けをすることで、「この状態は先手必勝」などを判断することができます。単なる傾向としては先手が有利なものが多く、これを考察に使うのもいいかもです。
よくわからないときに大切なのは、実験です。手元で小さいケースで実験し、わからなければ機械にも頼るかめんどければ飛ばして次の問題に行きます。
- ARC137-C Distinct Numbers
この問題はまじで実験ゲー感があります。実験してみて、そして余力があれば実際に証明しましょう。この手の問題は証明に帰納法使ったりします。「この状態だと勝つと仮定すると、これも勝てます」みたいな。
- ARC143-C Piles of Pebbles
この問題は手元でやってみて「数字小さい方が有利だな」という些細なことに気づけるかが肝です。実際にX, Yの大小で場合分けして証明しましょう。解説にあるX+Yで割った余りを考えるってのは、真似っ子戦略ですね。
- ARC148-D mod M Game
これも手元でやってみるなり実験が大切です。これは僕個人の感覚なのですが、modといえば周期です。周期といえば約数です。Mの約数を感じ取りながら、差の変化を見てみましょう。
これはちょっと違う。計算量いい感じに落とせるやつ。制約から√ってわかる。
操作が2種類しかない。プロットしてみて実際に勝つ状態をメモってみると性質が見えてくる。
包除原理
- コピペ用
- 符号・偶奇で遷移を簡単にできる
矛盾省いたら終わる典型
尺取り
- N通りの数列に対して順番に行うやつに有効？
順列
ARC典型、「順列はグラフで考えろ」
辞書順
- 矛盾省くだけ
- めんどい
- うまくやる
連結成分・閉路
- 辞書順
挿入DP
- 逆から考える atcoder.jp
piとiの距離が関係してくるやつは箱根
- bitDPなのは制約からわかる。
これの>=バージョンがあった気がする。覚えてる人いたら教えてください。
- よくわからん多項式時間の問題は(数え上げなら)DPって決まってる。(最大値とかならフロー)
その他
- ただの筋肉
- 中央値、その値から見て大きいか小さいかを考える典型
グラフ
木
- swapするタイミング、次数に注目。木DP
- BIT, いもす, オイラーツアー
- 立式して木DP
その他のグラフ
- ハイパーグラフ？小さいものから確かめてちゃんと考えると二部グラフがでてくる。
- グラフで考える、彩色
その他のDP
- iが連続するのはi個まで。これはadhocなDPだと思う。
数学
- 小さい桁から埋めていくの非自明
- CHT
XOR
- 木の構築
- XOR基底
- XOR基底
N個全部使うやつを除いた最大値探したいときは、除外するのを固定すればよい。
解の範囲を絞っていくやつ
- O(N)
上界を考える感じのやつ
- やや数学
- 幾何、最悪ケースを考えると良さそう。
区間クエリ？
セグ木で端を1個ずつずらして進めていくやつ
乱択
過半数という文字とか過半数に帰着できるような問題設定のとき、乱択であるケースが多い
文字列
- 辞書順・LCPなどに使える定理
貪欲
- 「前にこうしてばおけばよかった…」「今からでも取り戻せます！」の気持ちになると解ける
その他
- 高橋君歩かせてぶつかったら反転できるやつ。距離最大化
- 負の数考慮すんのめんどい
- その分割は非自明、バケット
- 逆からもやって状態数小さくできるやつ
- 正の閉路と負の閉路それぞれ見つけたら終わり
次追記するときに記事分ける
