はじめに
人間は，忘れる．
どうせいっぱい文字書いて詳細を書いても忘れる．
忘れるので
めもたち
Reverse Sort
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2443&lang=jp
1stepで状態がめっちゃ増える．指数的に増えるような時はスタートから何stepかだけ探索，ゴールから何stepかだけ探索して真ん中ですり合わせる．
魔法使い高橋君タイプの貪欲
沈んで上がる，だけのギザギザ線をいっぱいならべる．高く保つためには？みたいなやつ． カッコ並べるときに頻出．
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2681
期待値の線形性
一連の操作をしたとき、各操作それぞれが独立に一連の操作の中で行われる確率が求まるなら一連の操作の操作回数の期待値は各操作の確率の和
https://atcoder.jp/contests/arc114/tasks/arc114_e
木を細切れにする，直径最大値がK以下, 数え上げ
木DPで十分, dp[cur]とするときに，curを端点とする最長パスだけ持ってればよい．それ以下の部分木の別のパス持っててももうそれは今後伸びないから考えても仕方ない．
String hash
文字列の同型判定
RollingHashをセグメント木でとる． 文字に対するハッシュ値はクエリごとに計算するので，セグメント木に乗せる
https://codeforces.com/contest/985/problem/F
差が一定やつ，畳み込み
普通の畳み込み，添え字の和が一定なものを集める．
つまり一方を反転すれば差が一定なものを集めれる
包除をDP
dp[i][j] : i番目まで見てj個ほげほげ jの偶奇で最後包除．みたいな時，jの偶奇しかいらないのでjを0~kとかにする必要がない場合があって，O(NK) じゃなくてO(N)になる場合があるかもしれないしないかもしれない
任意位置のものを端に置く
問題他にもあった気がする
F - Insertion Sort
↑の問題は任意位置を左端，右端，自由位置へ移動させることが出来て，それぞれコストが定まっている．
この場合は，1, 2, ...のどこまでを左端へ，自由位置への操作で殺すかをdpで処理できるので終わる
Connect, (2N) * (2N)のDPをしなくてもよい
多分俺が見たことあまりないだけで典型 (2N)(2N)のDPをN(2N)に落とす
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449
直線状を歩いてぶつかったら向きを変えてまた歩く
No.1608 Yet Another Ants Problem - yukicoder
ブルーフカ法
真面目に辺をはると，O(ElogV)である，最小全域木アルゴリズム． 各連結成分から最小のコストの辺を求めて辺を張ることを繰り返すとlogN回の繰り返しで求まる． 毎度頂点を全部舐めて，辺を全部舐めないで最小辺を求めれるような状況ならこれをやればよい．
xyに平行な線のみからなる多角形と点の包含判定
右側をみて，縦棒が奇数本あればin
下の問題は多角形が複数あって，何個にinしているかをクエリで答える． これはy軸小さい方からみていってセグメント木で縦棒を管理して平面操作で解ける． atcoder.jp
ソート，swap数
差が1の値同士しかswapできません -> invP[P[i]] = iを考えると，ただの転倒数
自由にswapできる -> cycleを考える
他重要かもしれない考察のとっかかり - 1回のswapを使って2つのcycleを1つにまとめれる(https://atcoder.jp/contests/arc124/submissions/24550202)
