Editional の訳:

\(i\) 日目のすべてのマークの数を \(t_i\) とする. \(t_i = m_i + 1 + d_i\) となる. \(\sum d_i\) を最小化するということは, \(t_i\) を最小化することと同じである.

\(i\) 日目の最小の \(t_i\) を求めたい.

当然ながら, \(t_i \geq \max(t_{i-1}, m_i+1)\) となる.

すべての日において \(t\) は多くとも1しか増やせないので, \(t_i \geq t_{i+1}-1\) であり, ここから任意の \(j \gt i\) において \(t_i \geq t_j - (j-i)\) が成り立つ.

ひとつ目の条件は左から右に見ていくことで簡単に満たせる. これを記録しておこう. さて, ふたつ目の条件をどのように満たせば良いだろうか.

その方法のひとつは, 逆から見ることである. 右から左に見ていき, 日ごとに1ずつ減り, 現在の \(t_i\) との最大値を取るカウンタを用意する. このカウンタはふたつ目の条件を満たす最小の \(t_i\) になる.

この方法で決めたある \(t_i\) を増やしても, 他の \(t_i^{\prime}\) を減らすことはできない. よってこの合計が最適であり, 計算量は \(O(N)\) である.