Official
B - 合格ラインの日々 / Days of the Passing Line Editorial by admin Editorial for printing
DeepSeek V3概要
各日までの試験の平均点とその日の点数を比較し、平均点以上であれば満足する日が何日あるかを数える問題です。
考察
問題の条件は、\(k\)日目において \(A_k \geq M_k\) が成り立つかどうかですが、これは式変形すると \(k \cdot A_k \geq S_k\) となります(\(S_k = A_1 + A_2 + \dots + A_k\))。この条件は毎日計算可能で、\(S_k\)(累積和)を保持しながら各日について条件をチェックすることで効率的に解くことができます。
素朴なアプローチとして、毎日それまでの全点数を合計して平均を計算すると、各日で\(O(k)\)時間かかるため、全体で\(O(N^2)\)時間となり、\(N\)が最大200,000なので時間制限に間に合いません。しかし、累積和を利用することで各日のチェックを\(O(1)\)で行え、全体で\(O(N)\)時間で解けます。
アルゴリズム
- 累積和 \(total\) を0で初期化する
- 各日 \(i\) (0-indexed) について以下を行う:
- \(total\) に \(A_i\) を加算する(これが \(S_{i+1}\) になる)
- 条件 \((i+1) \cdot A_i \geq total\) をチェックする
- 条件が真ならカウントを1増やす
- 最終的なカウントを出力する
このアルゴリズムでは、各日について必要な計算は加算と比較のみなので、非常に効率的です。
計算量
- 時間計算量: \(O(N)\)
- 空間計算量: \(O(N)\)(入力配列の保持)
実装のポイント
累積和を保持する変数
totalを用意し、毎日更新する日数は0-indexedで処理しているため、条件チェック時に \((i+1)\) を使う
入力の読み込みには
sys.stdin.read()を使用して効率化しているソースコード
def main():
import sys
data = sys.stdin.read().split()
n = int(data[0])
A = list(map(int, data[1:1+n]))
count = 0
total = 0
for i in range(n):
total += A[i]
if (i + 1) * A[i] >= total:
count += 1
print(count)
if __name__ == "__main__":
main()
この解説は deepseekv3 によって生成されました。
posted:
last update: