B - 合格ラインの日々 / Days of the Passing Line Editorial by admin
GPT 5.2 High概要
各日 \(k\) について「その日の点数 \(A_k\) が、1日目〜\(k\)日目の平均点 \(M_k\) 以上か」を判定し、満足する日の数を数える問題です。
考察
満足条件は \(A_k \ge M_k\) ですが、平均 \(M_k\) を毎回実数で計算すると誤差が気になったり、毎回 \(A_1+\dots+A_k\) を足し直すと \(O(N^2)\) になってしまいます。
ここで重要な観察は、条件が次のように整数だけで判定できることです:
[ A_k \ge \frac{A_1+\dots+A_k}{k} \iff k\cdot A_k \ge A_1+\dots+A_k ]
したがって、各日までの累積和 \(S_k = A_1+\dots+A_k\) を順に更新しながら、\(k\cdot A_k \ge S_k\) をチェックすればよいです。
素朴に「毎日、平均を計算するために過去の点数を合計し直す」方法だと、\(1+2+\dots+N = O(N^2)\) 回の足し算になり、\(N \le 2\times 10^5\) では間に合いません。累積和を使えば合計の更新は \(1\) 回で済みます。
アルゴリズム
- 変数
sを累積和(最初は \(0\))、ansを満足した日数(最初は \(0\))とする。 - \(k=1\) から \(N\) まで順に:
s += A_kとして累積和 \(S_k\) を更新- もし \(k\cdot A_k \ge S_k\) なら
ans += 1
ansを出力する。
(例)\(A=[3,1,4]\) のとき
- \(k=1\): \(S_1=3\), \(1\cdot 3 \ge 3\) → 満足
- \(k=2\): \(S_2=4\), \(2\cdot 1 =2 \not\ge 4\) → 不満
- \(k=3\): \(S_3=8\), \(3\cdot 4 =12 \ge 8\) → 満足
よって答えは \(2\)。
計算量
- 時間計算量: \(O(N)\)(各日1回ずつ処理)
- 空間計算量: \(O(1)\)(累積和と答えなど定数個の変数のみ)
実装のポイント
平均を浮動小数で扱わず、\(k\cdot A_k \ge S_k\) の形で整数比較にすると安全です。
\(A_i\) は最大 \(10^9\)、\(S_k\) は最大で \(2\times 10^5 \times 10^9 = 2\times 10^{14}\) 程度になるため、Python なら自動で大整数対応できます(他言語では 64bit 整数を使う)。
入力が大きいので
sys.stdin.buffer.read()を使うと高速に読み込めます。ソースコード
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
N = data[0]
A = data[1:1+N]
s = 0
ans = 0
for k, a in enumerate(A, 1):
s += a
if k * a >= s:
ans += 1
print(ans)
if __name__ == "__main__":
main()
この解説は gpt-5.2-high によって生成されました。