[Codeforces] Codeforces Round #674 (Div. 3) C. Increase and Copy

2020年10月12日

問題

方針

\( i \) 回目の操作後の数列の総和を \( s_i \)、数列の最大値を \( b_i \) とすると、

\[
s_{i + 1} =
\begin{cases}
s_i + 1 \\
s_i + b_i
\end{cases}\]

となるので、先にインクリメントしてからコピーする方が最適だと考えられます。ここで、インクリメントした回数を \( x \) とし、コピーすべき回数を \( m \) とすると、

\[ m = \dfrac{n – (1 + x)}{1 + x}\]

となります。したがって、相加相乗平均を用いて、

\[ \begin{eqnarray}
x + m &=& x +\dfrac{n – (1 + x)}{1 + x} \\
&=& 1 + x + \dfrac{n}{1 + x} – 2\\
&\geq& 2 \sqrt{n}  -2
\end{eqnarray}\]

となります。

コード