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