C - Range Increment 解説
by 
maspy
公式解説が難読に感じられたため，一応書きます．ちゃんと読めば同じ説明であるという可能性もあります．
[1] インクリメント回数と操作回数
最終的に \(A_i\) に \(x_i\) 回のインクリメントが行われるとします．このとき，それを実現する最小操作回数は
\[\mathrm{cost}=\sum_{i=1}^N\max(0, x_i-x_{i-1})\]
となります．ただし，\(x_0=0\) であると定義することにします．
\(\mathrm{cost}\) 回以上の操作が必要であること
\(x_i-x_{i-1}\) は \(l=i\) であるような操作によってしか増えないので，\(l=i\) であるような操作が \(\max(0, x_i-x_{i-1})\) 以上必要だと分かります．全体ではその総和以上必要です．
\(\mathrm{cost}\) 回以上の操作が十分であること
\(i=1,2,\ldots\) 順に操作の仕方を決めていくことができます． \(i-1\) への加算を行っている操作をそのまま延長すると，\(x_{i}=x_{i-1}\) が達成できます．そこから
- \(x_{i-1}>x_i\) ならばいくつかの操作を終了すれば（\(r=i-1\) とすれば）よいです．
- \(x_{i}>x_{i-1}\) ならばそこに，\(l=i\) であるような新規の操作を \(x_i-x_{i-1}\) 個追加すればよいです．
操作回数は上の手順で操作を決めたときに，新規の操作を追加する回数なので，\(\mathrm{cost}\) に等しくなります．
[2] 目標とする数列を決めたときのコスト
目標とする数列を決めた（インクリメント回数は決めていない）ときの最小コストを求める問題について考えてみます．
言い換えれば，次の問題を考えます．
- \(0\leq a_i<M\) を満たす非負整数列 \(a=(a_1,a_2,\ldots,a_n)\) が与えられる．
- 非負整数列 \(x=(x_1,x_2,\ldots,x_n)\) を，\(x_i\equiv a_i\pmod{M}\) を満たすように作るとき，\(\mathrm{cost}=\sum_{i}(0,x_i-x_{i-1})\) を最小化せよ．
\(x_i\) の代わりに，\(x_i=a_i+t_iM\) により非負整数列 \(t\) を定める問題と考えます．そして，\(\mathrm{dp}_i(t)\) を，\(t_i=t\) であるときの \(\mathrm{cost}=\sum_{j\leq i}(x_j-x_{j-1})\) の最小値とします．
\(\mathrm{dp}_{i-1}\) から \(\mathrm{dp}_i\) への遷移は，次のようなある種の min-plus 畳み込みによって表されます．（凸数列の min-plus 畳み込み が理解の役に立ちますが，負添字を持つ列を考えるなどの細かい違いがあります）．
まず，（非負とは限らない）整数 \(t\) に対して
\[f(t)=\max(0,Mt+(a_i-a_{i-1}))\]
により定めます．すると，関数 \(\mathrm{dp}_i\) は
- \(\mathrm{dp}_{i-1}\) と \(f\) の min-plus 畳み込みをとる．（定義域は整数全体になる）
- 定義域を非負整数全体に制限する．
という手順で得られることが分かります．\(\mathrm{dp}_i\) の定義や min-plus 畳み込みの性質から，次のことが分かります．
- \(\mathrm{dp}_i\) は単調増加（定義からも簡単）．
- \(\mathrm{dp}_i\) は下に凸である．
階差数列に注目すれば，おおよそ次が分かります．
- 階差数列は，\(M\) 未満の非負整数 \(O(i)\) 個および，無限個の \(M\) からなる．
- 階差数列のうち \(M\) 未満のものに注目すると，\(\mathrm{dp}_{i}\) の階差数列は，\(\mathrm{dp}_{i-1}\) の階差数列に高々ひとつの要素を追加して，高々ひとつの要素を削除したものである．
\(f(t)\) の階差数列の \(0,M\) 以外の項が高々ひとつあり，それが追加する要素と対応します．定義域を非負整数全体に制限する際に，傾きの削除が行われる可能性があります．ただし，\(a_i\) と \(a_{i+1}\) の大小関係によって処理の細部が変わるため，慎重に考えてみてください．
階差数列の多重集合および \(\mathrm{dp}_i(0)\) の値を適切に管理しながら計算をすすめれば，目標とする数列を決めたときのコストは \(O(N\log N)\) 時間で計算できます．
[3] 本問の解法
[2] のコストの計算と，目標とする数列の prefix の確定を同時に行っていけばよいです．
投稿日時:
最終更新: