AtCoder Regular Contest 085 F - NRE メモ

解説とちょっと違う方法だったので記事を書くことにしました。

まず、区間を終点でソートする。
そして、以下のようなDPを考える。

DP[i] = a1~aiまでの数値を決定したときに、その部分で求められるハミング距離の最小値

順番に区間を見ていく。ここでその区間が[L, R]だったとすると、

DP[i] = min(DP[i], DP[L-1] + zero(L, i)) (L <= i && i <= R)
DP[i] = min(DP[i], DP[R] + one(R, i)) (R+1 <= i && i <= N)

の更新式が成り立つ。
（ここで、zero(a, b)は[a, b]の中にあるbi = 0の数。）
気持ちとしては、一つ目の更新式はこの区間を使う場合の更新。
二つ目の更新式はこの区間を使った場合に、ズレが生じるので、その補正を行なっている。

しかし、当然このDPを直接更新していては、計算量が間に合わない。
ここで、式の変形を行なって高速化することを考える。
具体的には、

1つ目の式について、DP[L-1] + zero(L, i) = zero(1, i) + (DP[L-1] - zero(1, L-1))
2つ目の式について、DP[R] + one(R, i) = one(1, i) + (DP[R] - one(1, R-1))

という形に変形する。この右辺の第二項の値をそれぞれLの関数、Rの関数と捉えて、それらの値がどのように変化するかをセグメント木で管理する。そして、DP[i]の値にアクセスしたくなったら、セグメント木に保存されている値を取り出して計算する。

想定解とどのような場所が本質的に違っているのか、この解法が本当にあっているのか、ちゃんと考えたい（記事にしたのはとりあえずです）

さかなの思い