B - 合格ラインの日々 / Days of the Passing Line Editorial by admin Editorial for printing
Claude 4.6 Opus (Thinking)Overview
This is a problem where, over \(N\) days of exams, we count how many days the score on that day is greater than or equal to the average score up to that day.
Analysis
The condition for Takahashi to be satisfied on day \(k\) is \(A_k \geq M_k\) (the score on that day is greater than or equal to the average score up to that day).
Let’s transform this condition algebraically.
\[A_k \geq \frac{A_1 + A_2 + \dots + A_k}{k}\]
Multiplying both sides by \(k\) (since \(k > 0\), the direction of the inequality does not change):
\[k \cdot A_k \geq A_1 + A_2 + \dots + A_k\]
Through this transformation, we can determine the condition using only integers without division. This is the key point. Using division could introduce floating-point errors, but we can make an exact determination using only integer multiplication and comparison.
Let’s verify with a concrete example. If the scores are \([5, 3, 7]\):
- \(k=1\): cumulative sum \(= 5\), \(1 \times 5 = 5 \geq 5\) → ✅ satisfied
- \(k=2\): cumulative sum \(= 8\), \(2 \times 3 = 6 \geq 8\)? → ❌ not satisfied (score of 3 against an average of 4)
- \(k=3\): cumulative sum \(= 15\), \(3 \times 7 = 21 \geq 15\) → ✅ satisfied
The answer is \(2\) days.
If we naively recompute \(A_1 + A_2 + \dots + A_k\) each time, it becomes \(O(N^2)\), but by maintaining the cumulative sum in a variable, we can process each day in \(O(1)\), solving the entire problem in \(O(N)\).
Algorithm
- Initialize a variable \(s\) to hold the cumulative sum to \(0\).
- Initialize a counter
countfor the number of satisfied days to \(0\). - For \(k = 1, 2, \dots, N\), repeat the following:
- Add \(A_k\) to \(s\).
- If \(k \times A_k \geq s\), increment
countby \(1\).
- Output
count.
Complexity
- Time complexity: \(O(N)\) — just a single pass through the array
- Space complexity: \(O(N)\) — for storing the input array (the cumulative sum is managed with a single variable)
Implementation Notes
Do not use floating-point numbers: Computing the average directly results in decimals and can introduce errors. It is safe to compare as integers using \(k \cdot A_k \geq S_k\).
Watch out for overflow: \(k\) can be up to \(2 \times 10^5\) and \(A_k\) can be up to \(10^9\), so \(k \times A_k\) can be up to approximately \(2 \times 10^{14}\). In C++ and similar languages,
long longis required, but in Python there is no integer overflow so this is not a concern.Indexing in the code: Since the code uses 0-indexed
range(N), the day number corresponding to day \(k\) isk + 1.Source Code
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)
This editorial was generated by claude4.6opus-thinking.
posted:
last update: