[Codeforces] Codeforces Round #674 (Div. 3) C. Increase and Copy
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません