はじめに
思考の整理も兼ねて 緊急時に読み返せるように 昨日のCで解法ガチャがハマったのでこの機にまとめて整理します
このリストが役立つのは水くらいからですかね？
(ネタバレ防止用の空白)
二分探索を適用したいとき
- 最大値の最小化は二分探索！(素振り) 意識しないと抜けがち
- 単調性が自明だったら二分探索を早めに検討した方がいい? これとか
- 解の決め打ちで判定できるとき、単調性があるか確かめるとイイ感じに二分探索へ持ち込める(単調性がないこともある→そのときは解の候補を減らしにかかる)
- $K$番目の値系 最近のABCでN回見た
- 中央値を取り出す系と二分探索は相性がいい これとか こういうの
↑この相性の良さはもうちょっと一般化できそう
ランレングス圧縮
AGC-Aだとよく見る 値が2種類のときはランレングス圧縮して損はない
ランレングス上で考えて計算量を圧縮する まだ解いてないけどこれもたぶんそう
階差を取る
気づかず破滅するタイプ 実は階差が不変量みたいなの
区間に対する操作は階差を取ると見通しが良くなることが多い
偶奇
パズルゲーで真っ先に見るのはこれ
a+bとa-bは偶奇が等しい(例: 任意の正の整数tに対し(x+y)(x-y)=2*5tなる整数x,yが存在しないことを示せ)
不変量
ゲームの場合の不変量が一番有名だが、変な操作をする問題でも不変量に気づくことを要求する場合がある
不変量に気づけば別の操作に言い換えられる問題
不変量から別の操作への言い換えを用いる http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2617&lang=jp
↑総和が変わらないことに気づき、累積和をとると累積和配列のswapに帰着される
https://atcoder.jp/contests/agc016/tasks/agc016_d
↑総XORが不変
見るべき候補はそんなに多くない
よくわからない最大最小系は貪欲を考えてみる
$N!$通りから最適なものを選ぶような問題だと最初に最適な順になる比較関数を考えてソートする
実は間に合う系
2で割る操作とか2倍する操作が絡んでると実は$\rm{log} N$個しか見なくてよくなることがある
E - Reversing and Concatenating
操作が$\rm{log} N$回程度で終了するのを見つけるのが本質のことも
全体で見ると操作がならしO(なんとか)で間に合うやつ JOIに多い(偏見)
更新のあるところだけ更新するとなんか間に合うやつ(全体で何らかの値が1ずつ減っていくような状況を考える)
こういうのは気づかないと一巻の終わりなので大きめのテストケースを生成してストレステストするのが良さげ
とりあえず1か所決めてみる
1か所決めると他が高々数通りしかないやつ
DPとの組み合わせは割と多い
木が与えられたときに試した方がいい性質
- 直径
- 二部グラフ性
- 中心
- 重心
この辺見ればほぼ間違いはなさそう
2点取る系はLCAに注目すると良いことが多い
あと上(根)から見るか下(葉)から見るか両方確かめる
どっちから見るか迷うやつ C - Folia
木DPっぽさそうなときは適切なマージが可能か考える 全方位木DPは最後の手段
信じる心/きっと同値
こういう条件を満たしてたらきっと全部作れる/最適っぽさそうなのができるだろうと信じる で、実際全部作れる
例:
1回の操作で個の要素が減るので、操作回数は最小で
の切り上げになりそうだとわかる
で、実際にうまく操作をやれば最小が実現できる
やたらと人が通してるように見えたら信じる心系を疑った方がいいかもしれない
逆から見る
最初の方に行った操作が後の方ではぐちゃぐちゃになってるとき 上書き保存系も逆操作と相性がいい
これは本当に納得いってない 目的のところまで行くには道が多すぎるが、目的のところからスタートへ帰ると見ると楽になる とでも言えばいいのだろうか...
本当に忘れがちなので注意
余事象を取る
AndとOrを反転させる 束縛条件が多いときにやってみるとやりやすくなることがある
余事象をとった後にOrの条件が出てきた場合、包除原理を考えるとよい(Orに対処できるのは包除ぐらいしかない)
マンハッタン距離系
その1. $x$軸と$y$軸でバラす
その2. 45度回す
(x,y)→(x+y,x-y)
-元の座標でxかy方向に±1動く運動が両方に±1動く運動になる - マンハッタン距離がX座標/Y座標の差のmaxになる
だからといって何でもかんでも回せばいいというものでもないので注意
オイラー路とハミルトン路の行き来
ハミルトン路への帰着が自明なときはオイラー路に変換できないか考える
添え字と値を入れ替えるテク
本番で詰め切れませんでした(泣)
C - スタンプラリー 3 (Collecting Stamps 3)
D - Complexity 解けてないけどこれっぽい
変なマッチングではマッチングアルゴは要らない
B - 展覧会 (Exhibition) ←一見マッチングだが制約が特殊なので、貪欲でOK
B - Powers of two 一般マッチングが脳裏をよぎるが、そんなことはない
変なデータ構造とかアルゴを要求しそうだと思ったら一度立ち止まった方がよさそう 特にAtCoder
困ったら実験
文字通り
おわりに
雑でごめんなさい
