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

2020年12月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}\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t, n;
    cin >> t;
    int ans[t];
    for (int i = 0; i < t; i++) {
        cin >> n;
        if (n == 1) {
            ans[i] = 0;
        } else {
            int a = sqrt(n);
            if (a * a == n) {
                ans[i] = 2 * a - 2;
            } else {
                ans[i] = ceil(sqrt(n) * 2) - 2;
            }
        }
    }
    for (int i : ans) {
        cout << i << "\n";
    }
    return 0;
}