この解説ではシミュレーションによる貪欲法の解法を解説します。

\(i=2,3,...,N\) の順に \((A_1,A_2,\dots,A_i)\) が広義単調増加になるように操作をしていきます。ただし、\(A_i\) に \(1\) 増やす代わりに今後これ以降の要素のいずれかを \(-1\) する(いわば借金のような)操作も許可することとします。このとき、何回分借金をしているかを表す変数 \(x\) も持つこととします。

このとき、\(A_i\) も \(x\) も小さい方が良いことが示すことが出来ます。この事実は \(i\) を途中まで見たときに \(A_i\) が小さい方が損しないこと、\(x\) が小さい方が損しないことから証明することが出来ます。更に、それぞれ同時に下界を達成するような操作列が存在します。

• $A_{i-1} > A_i$ のとき
$A_i$ を $A_{i-1} - A_i$ 増やし、$x$ に $A_{i-1} - A_i$ を足す。
• $A_{i-1} \le A_i$ のとき
• $A_{i-1}> A_i - x$ のとき
$A_i$ を $A_{i-1}$ にし、$x$ から $A_i - A_{i-1}$ を引く。
• $A_{i-1} \le A_i - x$ のとき
$(A_1,A_2,...,A_i)$ を広義単調増加である中で今までと総和が一致していて $A_i$ が最も小さいものに置き換えることが出来る。そのような操作をした上で $x$ を $0$ にする。

上記のシミュレーションは \(A_i\) も \(x\) も最小化していて、かつ \(\mathrm{O}(N)\) 時間で行うことが出来ます。