数列¶
ソートをしても一般性を失わないならソートする¶
ソートされていると扱うのが簡単になる例は多い
条件を満たすi,jのペアの数¶
値を辞書で管理しておくと判定が簡単になる場合が多い
条件を満たすi,j,kの3値の数¶
どれかの値を固定すると見通しがよくなる。 最初に全ての値をdataRに入れておき、jをシフトすると共にdataLにjだった値を入れていけば、jを中心とした時の左右の値を管理できる。
管理の仕方としては存在確認をしたいなら辞書、ある範囲の数を数えたいなら、BITなどで持たせる。
例、 jの値を中心として、より小さい左の値、より大きい右の値の数をカウントしたいならBIT管理が適する
区間和の最大¶
初期値を0として頭から和にして、値が負になったら0にリセットし、次の数からスタートとする。 ある地点で負になった場合、その値を次からに持ち越す必要はなく、次の値から始めた方が良い。
グラフ¶
ダイクストラ法¶
単一始点、全終点を求める。
負のサイクルがあってはいけない。負の辺があること自身は許容される
各点について更新した１つ前の点を覚えておくことで始点からのパスを求めることが可能
全点についてこのパスを復元すると、辺数は$n-1$の全域木となる（最小全域木とは限らない)
ハミルトン¶
閉路を含むグラフ¶
強連結成分分解をするとDAGになるので、木にできる
木¶
葉から辿る・根から辿るにはトポロジカルソートを使っても良い¶
根からトポロジカルソートをすると、順に辿れば根から辿れる。逆に辿れば葉から辿れる。DFSして良いが、なにも考えずにライブラリで配列の形で計算を流せる。
データ構造¶
SparseTable¶
更新不可、区間クエリO(1)
事前計算 O(logN) クエリO(1)