公式

B - 合格ラインの日々 / Days of the Passing Line 解説 by admin 印刷ページ

GPT 5.2 High

Overview

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

  1. Initialize variable s as the prefix sum (initially \(0\)) and ans as the number of satisfied days (initially \(0\)).
  2. 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
  3. 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.

投稿日時:
最終更新: