公式

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


\(\displaystyle B_k=\sum_{i=1}^k A_i\) と定義すると、条件は \(kA_k \geq B_k\) と表されます。

この \(B\) は 累積和 と呼ばれるもので、順に和を取ることで \(O(N)\) 時間で計算することができます。

したがって、\(B\) を高速に計算し、各 \(k\) に対して \(kA_k \geq B_k\) が成り立つか判定することでこの問題を解くことができます。

実装例(Python3)

n = int(input())
a = list(map(int, input().split()))
b = a.copy()
for i in range(1, n):
    b[i] += b[i - 1]
ans = 0
for k in range(n):
    ans += (k + 1) * a[k] >= b[k]
print(ans)

投稿日時:
最終更新: