Official

B - 合格ラインの日々 / Days of the Passing Line Editorial by admin

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

  1. Initialize a variable \(s\) to hold the cumulative sum to \(0\).
  2. Initialize a counter count for the number of satisfied days to \(0\).
  3. For \(k = 1, 2, \dots, N\), repeat the following:
    • Add \(A_k\) to \(s\).
    • If \(k \times A_k \geq s\), increment count by \(1\).
  4. 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 long is 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\) is k + 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.