■A - Not Overflow
オーバーフローに注意
■B - Matrix Transposition
やるだけ
■C - kasaka
まず前のaの数と後ろのaの数を揃えられるなら揃える
その後に回分判定
回分判定はreverseして一致判定したら添字でバグらないので楽
■D - LR insertion
後ろから考える
■E - Skiing
解けませんでした恥。
x>yとして
x->y:=h[x]-h[y]
y->x:=2(h[y]-h[x])
後半が見通しが悪いので
y->x:=h[y]-h[x] +(h[y]-h[x])
これらを足したところで前半部分はh[start]-h[end]になるので
x->y:=0
y->x:=h[y]-h[x]としたときに各行き先への喜びを最大化すればいい。
なのでダイクストラ。
■F - |LIS| = 3
今の状態の最長増加部分列のうち辞書順最小なものごとに管理してdpを行う。
■G - Range Sort Query
xの場所だけわかればいい、
操作後にx以上なものの場所は、区間内にxより小さいものがどれだけあるかで決まるので
00001111のように持ち替えて操作を行う
x-1でも同様に行うと差分がある部分が答えになる。
操作は区間変更、区間加算なので遅延セグ木。
■Ex - Hakata
まず回分の種類はSの長さにしかならない。
そのため全列挙が間に合う、
また、回分の種類の少なさと成約から、回文が回文の部分列になっているかの判定も工夫せずとも間に合う。
列挙さえできればグラフが作れる。
あとは最小パス被覆に落ちるので、最大流。
