典型の典型.html

<title>典型の典型</title>

はむこさんの典型
<a href="https://github.com/hamko/procon">オリジナル</a>
typical.png
遷移条件は判別できなかった。
<pre>
*[問題]
[文字列]
	マッチング
	一致判定
		(1,2次元)ロリハ
		(1次元)SA-IS
[ゲーム]
	アドホック
	後ろから確定
	WL-Algorithm
	猿真似→Grundy Number→分裂

[XOR]
	a xor a = 0
	桁ごと固定
	Trie木
	01が立っている様子を思い浮かべる(XOR<=SUM)
	ANDと共にGF(2)→行列累乗

約数,gcd
	約数全列挙→sum_g n/gはO(n long n)


[YES/NO]
	乱択→[構築]
	大量制約→[SAT]

[SAT]
	3-SAT
	2-SAT
		Segment Tree SAT

[構築]
	[SAT]
	満たす解を1つ想定してそこからの操作ができるかを考える
	連立方程式の解の一例
		DFSで矛盾検知
		重み付きUnion Find
		最短距離問題双対(牛ゲー)
	構築すべき盤面
		列固定
		カギ型
		L字型→左右をとりあえず白黒に分ける
	小制約の全探索ができる
		辞書順最小の解を出して法則を見出す
	[構築すべきグラフ]

[構築すべきグラフ]
	二部グラフ
	二部グラフの両端がいくつか連結
	クリーク
	線グラフ
	ウニグラフ
	ウニのカップリンググラフ
	ファンクショナルグラフ
	[木]

[木]
	直径
	中心
	重心
	同型
	木DP
	全方位DP
	パス→根付き木にして、パスは(lca-a)+(lca-b)-2(r-lca)
	部分木
		[オイラーツアー]

[列]
	累積和を折れ線としてみる
[クエリ]
	木のクエリ
		[オイラーツアー]
		LCA
		HL分解
		木の切断→Link-Cut Tree
	クエリスキップ
	オンラインクエリ
		平方分割
		連結行列のセグ木
	範囲クエリ
		imos的操作で点の操作に言い換える
	クエリ平方分割
		木のクエリ平方分割
	オフラインクエリ
		クエリソート→Mo
		Decomposable searching problem
[辞書順最小化]
	上から貪欲
	同じ桁なら数字比較と辞書順比較は一致
	最近のものを26分木でまとめていく
[多次元]
	一次元固定
	[xy独立]
[マンハッタン距離]
	[xy独立]
	45度回転
	数え上げ

[xy独立]
	グラフ
		辺に着目
		最短経路として使われうる辺は最短経路問題で
		最短経路DAG
		小さい制約(5歩で,10回で)

[数え上げ]
(:ちょうどX)X以上の関数を作る
(:ちょうどX)X以下の関数を作る
	[二分探索]
	[DP]
	半分全列挙
	包除原理(ほうじょげんり)
	高速ゼータ・メビウス変換
	区間の数え上げ
		count_{l,r}f(l) <= f(r)に落す
	種類の数え上げ
		直前に出てきたところをメモ

[DP]
	順序を貪欲に決める
	巨視的に見てデータ構造ゲー

[最小化]
	1変数固定
	Totally monotone minima
	[DP]
	フロー
	最小値全探索
	[二分探索]

[共通]
	小さいものから見ていく()
	問題制約を減らして解いてみる
	操作を逆順に見る
	対称
	固定するなら真ん中
	被覆
		後ろから見て塗り剥がして?を埋めておく
	環状
		環状を切る部分を全探索
		環状を切って始めを固定
	区間
		終端でソート
		始点を固定
			終点に対して単調
				[二分探索]
			終点の境界位置が始点に対して単調
				しゃくとり

*[対象]
	平均値と中央値が一致
</pre>