B - 合格ラインの日々 / Days of the Passing Line 解説 by admin 印刷ページ
GPT 5.2 HighOverview
For each day \(k\), determine whether “that day’s score \(A_k\) is at least the average score \(M_k\) from day \(1\) through day \(k\),” and count the number of satisfied days.
Analysis
The satisfaction condition is \(A_k \ge M_k\), but computing the average \(M_k\) as a real number each time raises concerns about precision errors, and recomputing \(A_1+\dots+A_k\) from scratch each time would result in \(O(N^2)\) complexity.
The key observation here is that the condition can be checked using only integers:
[ A_k \ge \frac{A_1+\dots+A_k}{k} \iff k\cdot A_k \ge A_1+\dots+A_k ]
Therefore, we can maintain a running prefix sum \(S_k = A_1+\dots+A_k\), updating it incrementally, and check \(k\cdot A_k \ge S_k\) for each day.
The naive approach of “recomputing the sum of all past scores each day to calculate the average” requires \(1+2+\dots+N = O(N^2)\) additions, which is too slow for \(N \le 2\times 10^5\). Using a prefix sum, updating the total requires only \(1\) operation.
Algorithm
- Initialize variable
sas the prefix sum (initially \(0\)) andansas the number of satisfied days (initially \(0\)). - For \(k=1\) through \(N\) in order:
- Update the prefix sum \(S_k\) with
s += A_k - If \(k\cdot A_k \ge S_k\), then
ans += 1
- Update the prefix sum \(S_k\) with
- Output
ans.
(Example) When \(A=[3,1,4]\): - \(k=1\): \(S_1=3\), \(1\cdot 3 \ge 3\) → satisfied - \(k=2\): \(S_2=4\), \(2\cdot 1 =2 \not\ge 4\) → not satisfied - \(k=3\): \(S_3=8\), \(3\cdot 4 =12 \ge 8\) → satisfied
Thus the answer is \(2\).
Complexity
- Time complexity: \(O(N)\) (each day is processed once)
- Space complexity: \(O(1)\) (only a constant number of variables such as the prefix sum and the answer)
Implementation Notes
Instead of handling the average as a floating-point number, comparing integers in the form \(k\cdot A_k \ge S_k\) is safe.
\(A_i\) can be up to \(10^9\), and \(S_k\) can be up to approximately \(2\times 10^5 \times 10^9 = 2\times 10^{14}\), so in Python this is handled automatically with arbitrary-precision integers (in other languages, use 64-bit integers).
Since the input can be large, using
sys.stdin.buffer.read()allows for faster reading.Source Code
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()
This editorial was generated by gpt-5.2-high.
投稿日時:
最終更新: