• 長さ \(n\) の整数列 \(c=(c_1,c_2,\ldots,c_n)\) が与えられる。隣接 \(2\) 項 \(c_i,c_{i+1}\) を選び、それらを \(\max(c_i,c_{i+1})+1\) に置き換える操作を \(n-1\) 回行う。最終的な \(c_1\) の値の最小値を求めよ。

この問題は \(\max(c_i,c_{i+1})\) が最小な \(i\) （複数ある場合は \(i\) が最小のもの）を取りそれらをマージすれば良いです。

証明：

整数列 \(c\) に対して操作を行った時の最終的な \(c_1\) の最小値を \(F(c)\) と書きます。

操作は以下の \(2\) つに分解することができます：

• 任意の要素の値を \(1\) 増やす。
• 隣接する \(2\) つの等しい要素をマージし、値を \(1\) 増やす。

まず、同じ長さの整数列 \(a,b\) が全ての \(i\) に対して \(a_i \le b_i\) を満たすなら \(F(a) \le F(b)\) が成り立ちます。また、整数列 \(a\) が整数列 \(b\) を含むなら \(F(b) \le F(a)\) が成り立ちます。

整数列 \(a\) に対し、その最小値を \(v=\min_i a_i\) とします。上で示した操作により \(a\) の中で値 \(v\) が \(x\) 個連続している場所を連続した \(\displaystyle \left\lceil \frac x2\right\rceil\) 個の値 \(v+1\) に置き換えることができます。この操作を \(\rho\) で表し、操作後の整数列を \(\rho(a)\) とします。このとき、\(F(a) = F(\rho(a))\) が成立します。

証明：

明らかに \(F(a) \le F(\rho(a))\) が成立します。

初期状態で値が \(v\) であった各要素に注目すると、値が \(v\) でなくなる方法は以下の \(2\) つしかないです：

• 隣の \(v\) とマージされて \(1\) つの \(v+1\) になる。
• 値が増やされて \(v+1\) になる。

\(v+1\) として残る要素の数は小さい方が良いので、これら \(x\) 個の値はできる限りマージすることが最適です。したがって、これらは連続した \(\displaystyle \left\lceil \frac x2\right\rceil\) 個の値 \(v+1\) に置き換えて良く、これにより \(F(a) \geq F(\rho(a))\) が分かります。

この補題より、最小値が隣接している場所があればその中で最も左の \(2\) つをマージして良いです。また、最小値が隣接している場所が無い場合は最小値である要素を \(1\) 増やすことを考えると、この \(F\) の値を保ちながら列を圧縮していく操作は貪欲法と一致することが分かります。