Official

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

GPT 5.2 High

概要

各日 \(k\) について「その日の点数 \(A_k\) が、1日目〜\(k\)日目の平均点 \(M_k\) 以上か」を判定し、満足する日の数を数える問題です。

考察

満足条件は \(A_k \ge M_k\) ですが、平均 \(M_k\) を毎回実数で計算すると誤差が気になったり、毎回 \(A_1+\dots+A_k\) を足し直すと \(O(N^2)\) になってしまいます。

ここで重要な観察は、条件が次のように整数だけで判定できることです:

[ A_k \ge \frac{A_1+\dots+A_k}{k} \iff k\cdot A_k \ge A_1+\dots+A_k ]

したがって、各日までの累積和 \(S_k = A_1+\dots+A_k\) を順に更新しながら、\(k\cdot A_k \ge S_k\) をチェックすればよいです。

素朴に「毎日、平均を計算するために過去の点数を合計し直す」方法だと、\(1+2+\dots+N = O(N^2)\) 回の足し算になり、\(N \le 2\times 10^5\) では間に合いません。累積和を使えば合計の更新は \(1\) 回で済みます。

アルゴリズム

  1. 変数 s を累積和(最初は \(0\))、ans を満足した日数(最初は \(0\))とする。
  2. \(k=1\) から \(N\) まで順に:
    • s += A_k として累積和 \(S_k\) を更新
    • もし \(k\cdot A_k \ge S_k\) なら ans += 1
  3. ans を出力する。

(例)\(A=[3,1,4]\) のとき
- \(k=1\): \(S_1=3\), \(1\cdot 3 \ge 3\) → 満足
- \(k=2\): \(S_2=4\), \(2\cdot 1 =2 \not\ge 4\) → 不満
- \(k=3\): \(S_3=8\), \(3\cdot 4 =12 \ge 8\) → 満足
よって答えは \(2\)。

計算量

  • 時間計算量: \(O(N)\)(各日1回ずつ処理)
  • 空間計算量: \(O(1)\)(累積和と答えなど定数個の変数のみ)

実装のポイント

  • 平均を浮動小数で扱わず、\(k\cdot A_k \ge S_k\) の形で整数比較にすると安全です。

  • \(A_i\) は最大 \(10^9\)、\(S_k\) は最大で \(2\times 10^5 \times 10^9 = 2\times 10^{14}\) 程度になるため、Python なら自動で大整数対応できます(他言語では 64bit 整数を使う)。

  • 入力が大きいので sys.stdin.buffer.read() を使うと高速に読み込めます。

    ソースコード

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()

この解説は gpt-5.2-high によって生成されました。