B - 合格ラインの日々 / Days of the Passing Line Editorial by admin Editorial for printing
Claude 4.6 Opus (Thinking)概要
\(N\) 日間の試験で、各日の点数がその日までの平均点以上であるような日が何日あるかを数える問題です。
考察
\(k\) 日目に高橋君が満足する条件は \(A_k \geq M_k\)(その日の点数がその日までの平均点以上)です。
この条件を式変形してみましょう。
\[A_k \geq \frac{A_1 + A_2 + \dots + A_k}{k}\]
両辺に \(k\) を掛けると(\(k > 0\) なので不等号の向きは変わりません):
\[k \cdot A_k \geq A_1 + A_2 + \dots + A_k\]
この変形により、割り算を使わず整数のまま判定できるようになります。これが重要なポイントです。割り算を使うと浮動小数点の誤差が生じる可能性がありますが、整数の掛け算と比較だけで正確に判定できます。
具体例で確認しましょう。点数が \([5, 3, 7]\) の場合:
- \(k=1\): 累積和 \(= 5\)、\(1 \times 5 = 5 \geq 5\) → ✅ 満足
- \(k=2\): 累積和 \(= 8\)、\(2 \times 3 = 6 \geq 8\)? → ❌ 不満足(平均4に対して3)
- \(k=3\): 累積和 \(= 15\)、\(3 \times 7 = 21 \geq 15\) → ✅ 満足
答えは \(2\) 日です。
素朴に毎回 \(A_1 + A_2 + \dots + A_k\) を計算し直すと \(O(N^2)\) になりますが、累積和を変数で管理すれば各日 \(O(1)\) で処理でき、全体 \(O(N)\) で解けます。
アルゴリズム
- 累積和を保持する変数 \(s\) を \(0\) で初期化する。
- 満足した日数を数えるカウンタ
countを \(0\) で初期化する。 - \(k = 1, 2, \dots, N\) について以下を繰り返す:
- \(s\) に \(A_k\) を加算する。
- \(k \times A_k \geq s\) ならば
countを \(1\) 増やす。
countを出力する。
計算量
- 時間計算量: \(O(N)\) — 配列を1回走査するだけ
- 空間計算量: \(O(N)\) — 入力配列の保持(累積和は変数1つで管理)
実装のポイント
浮動小数点を使わない: 平均点を直接計算すると小数になり誤差が生じます。\(k \cdot A_k \geq S_k\) と整数のまま比較するのが安全です。
オーバーフローに注意: \(k\) は最大 \(2 \times 10^5\)、\(A_k\) は最大 \(10^9\) なので、\(k \times A_k\) は最大約 \(2 \times 10^{14}\) になります。C++ などでは
long longが必要ですが、Python では整数のオーバーフローがないため気にする必要はありません。コード中のインデックス: コードでは0-indexedの
range(N)を使っているため、\(k\) 日目に対応する日数はk + 1となっています。ソースコード
N = int(input())
A = list(map(int, input().split()))
count = 0
s = 0
for k in range(N):
s += A[k]
if (k + 1) * A[k] >= s:
count += 1
print(count)
この解説は claude4.6opus-thinking によって生成されました。
posted:
last update: