E: guruguru - AtCoder Regular Contest 077
整数xを一つ決める。ある数a[i]に対して、a[i] + 1 またはxに遷移する、という操作を行い、a[1]～a[n]までの遷移を実現する。この操作の回数が最小になるようにxを決めた時、その最小回数を求めよ。
素直にやるとO(NM)の問題で当然間に合わない。そこでx=kのときの操作回数f_k(x)を考えると、xの不連続点が存在する高々1次関数の組み合わせになっていることがわかる。例えばa[i] < a[i + 1]であれば、a[i] < x <= a[i + 1]のときはxに遷移したほうが操作回数が最小になる。この場合はxの1次関数になる。それ以外のときは+1を繰り返したほうが最小になる。この場合はxの0次関数(定数関数)になる。
そこで、[f_1(x), f_2(x), ... , f_m(x)] という数列を構成することを考えると、この数列に1次関数を一気に足す、という操作がO(1)やO(logN)程度でできれば解決である。
そこでimos法を用いる。具体的には、n次関数の係数ごとにimos法を用いて、最後にx^nを書けながらf_k(x)を復元する、という操作になる。O(N)。
n次関数の和はそれぞれの次数の係数の和をとった関数に等しい、つまり
(ax + b) + (cx + d) = (a + c)x + (b + d)
という当たり前のロジックを使うものだけど慣れてないと思いつくのは難しい気がした。
