公式

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

Qwen3-Coder-480B

概要

高橋君が毎日受けた試験の点数から、その日までの平均点以上を取った日数を数える問題です。

考察

この問題では、各日 \(k\) について、その日までの点数の平均 \(M_k = \frac{A_1 + A_2 + \dots + A_k}{k}\) を計算し、\(A_k \geq M_k\) が成り立つかどうかを判定する必要があります。

しかし、素朴に毎回平均を計算すると、各日で合計を取る処理が \(O(k)\) かかり、全体では \(O(N^2)\) となってしまいます。\(N\) が最大 \(2 \times 10^5\) なので、これは時間内に処理しきれません(TLE)。

そこで、条件式 \(A_k \geq M_k\) を変形して考えます:

\[ 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 \]

つまり、各日 \(k\) において「その日の点数 × \(k\)」と「それまでの点数の合計」を比較すればよいのです。

このように式変形を行うことで、累積和を使うことで効率的に判定できるようになります。

また、\(1\) 日目は必ず満足するという条件があるため、最初からカウントに入れる必要があります。

アルゴリズム

  1. 各日 \(k = 1, 2, ..., N\) に対して、以下のように処理を行う:
    • これまでの点数の合計 total_score にその日の点数 \(A_k\) を加える。
    • 条件 \((k \cdot A_k) \geq \text{total_score}\) をチェックする(ただし \(k\) は 1-indexed なので、配列のインデックスは \(k-1\))。
    • 条件を満たせば「満足した日」としてカウントアップする。
  2. 最終的なカウントを出力する。

この方法により、各日につき定数時間で判定ができ、全体で線形時間で処理できます。

計算量

  • 時間計算量: \(O(N)\)
  • 空間計算量: \(O(1)\) (入力の配列を除く)

実装のポイント

  • 1-indexed と 0-indexed の違いに注意すること(コード中では k+1 としている)。

  • 合計値を保持する変数 total_score はループ内で逐次更新する。

  • 最初の日(\(k=1\))も必ず条件を満たすので、正しくカウントされるようにする。

    ソースコード

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)

この解説は qwen3-coder-480b によって生成されました。