B - 合格ラインの日々 / Days of the Passing Line 解説 by admin
Qwen3-Coder-480BOverview
This is a problem where we count the number of days on which Takahashi scored at or above his average score up to that day, given his exam scores for each day.
Analysis
In this problem, for each day \(k\), we need to compute the average score up to that day \(M_k = \frac{A_1 + A_2 + \dots + A_k}{k}\) and determine whether \(A_k \geq M_k\) holds.
However, if we naively compute the average each time, summing up the scores takes \(O(k)\) per day, resulting in \(O(N^2)\) overall. Since \(N\) can be up to \(2 \times 10^5\), this would not finish in time (TLE).
Therefore, we transform the condition \(A_k \geq M_k\) as follows:
\[ A_k \geq \frac{A_1 + A_2 + \dots + A_k}{k} \Rightarrow k \cdot A_k \geq A_1 + A_2 + \dots + A_k \]
In other words, for each day \(k\), we simply need to compare “that day’s score × \(k\)” with “the cumulative sum of scores up to that day.”
By performing this algebraic transformation, we can efficiently check the condition using a running sum.
Also, since the 1st day always satisfies the condition, it must be included in the count from the start.
Algorithm
- For each day \(k = 1, 2, ..., N\), perform the following:
- Add that day’s score \(A_k\) to the running total
total_score. - Check whether the condition \((k \cdot A_k) \geq \text{total\_score}\) holds (note that \(k\) is 1-indexed, so the array index is \(k-1\)).
- If the condition is satisfied, increment the count of “satisfied days.”
- Add that day’s score \(A_k\) to the running total
- Output the final count.
With this approach, each day can be checked in constant time, and the entire process runs in linear time.
Complexity
- Time complexity: \(O(N)\)
- Space complexity: \(O(1)\) (excluding the input array)
Implementation Notes
Be careful about the difference between 1-indexed and 0-indexed (in the code,
k+1is used).The variable
total_scorethat holds the cumulative sum is incrementally updated within the loop.The first day (\(k=1\)) always satisfies the condition, so make sure it is correctly counted.
Source Code
N = int(input())
A = list(map(int, input().split()))
satisfied_days = 0
total_score = 0
for k in range(N):
total_score += A[k]
if (k + 1) * A[k] >= total_score:
satisfied_days += 1
print(satisfied_days)
This editorial was generated by qwen3-coder-480b.