201の自分の解放メモ見ても全くわからなくて
ここの存在意義を見失いかけた。
橙diffだし仕方ないよね。
■201F - Insertion Sort
固定する、ソート後の一番右の要素をiとする
それより右のものは動かす必要がなくても動かすこととする
すると
dp[i] = 固定するソート後の一番右の要素をiとし、iまでを昇順に並べるのに掛かるコスト。
と定めると
dp[i] = min(dp[j] + Σ(k = j + 1,i-1)a[k])となる
ただし、jはソート前の時点でiより左にあるもの。
また、iは唯一の固定なことを考慮する必要がある。
とすると答えは、min(dp[i] + Σ(j = i + 1,n - 1)min(a[j],c[j]))
あと必要なのは、dp[j] + Σ(k = j + 1,i-1)a[k]の区間min
この部分はΣ(j = 0,j-1)a[j] +(dp[j]-Σ(k = 0,j)a[k])
であり左のシグマはiを固定したときに定数なので
dp[j]-Σ(k = 0,j)a[k] の部分をセグ木に乗せればいい
乗せる場所は
＞ただし、jはソート前の時点でiより左にあるもの。
を扱えるようにするために、ソート前のidxに乗せる必要がある。
■202F - Integer Convex Hull
これはできなくていいと思う。
まず凸包の実装方法を把握しているかが重要。
つまり上凸と下凸。
まず、左下の点を固定する。
upper[j][k][l] := 最後に選んだ2点がj,kでここまで作った部分の面積の倍の2で割ったあまりがl
となる頂点の選ぶ通り数。
通り数には直接選んでいなくても選んだ中に含まれている頂点のことも考慮する必要がある。
lowerも同様にやる
ここまで求めると右を固定すればすべての通り数が求まる。
■203F - Weed
貰うdpのほうが解りやすいと思う。
dp[i][j]:= iまで処理して、takahashiの試行回数がjの時のaokiの行動回数のmin
とdpテーブルを処理する。
dp[i][j]への遷移は
dp[i-1][j]からaokiが一本抜くケース
と
dp[x][j-1]からtakahashiがa[i]/2+1以上のものを全部引っこ抜くケース
■204F - Hanjo 2
当時の自分のupsolveよりよっぽど簡潔になったが。。。
dp[i][j] = i列目より前は全て埋まっている、i列目の状態をbitで表したものがj
研鑽料を無視して遷移させると
dp[i][j0]からdp[i+1][j1]に遷移させることとなるがこれは行列累乗にあたるものなので簡単に高速化できる
状態j0から状態j1への遷移が面倒ですがO(4^h*h)あれば列挙できる。
■205F - Grid and Tokens
最大流問題ということさえわかれば、上手に構築するだけ。
各行と列に１つしか置けないので
s->行と列->tにcap1の辺を貼る。
駒に関しては行と列のある範囲内に一つだけ置けるので
[a,b]*[c,d]の間に辺を貼ればいい。
しかしこれだと同じ駒を大量に置くことになるので
駒の頂点を倍にして、cap1で結ぶと良い。
