概要

最初に \(N\) 個あるプレゼントが、各区間の「つまずき」と各友人への「手渡し」で減っていくとき、最終的に何人に渡せるかを数える問題です。

考察

重要なのは、プレゼントの個数だけを追跡すれば十分、という点です。

• 友人 \(i\) に向かう途中で \(F_i\) 回つまずくと、持っている個数 \(p\) は最大で \(F_i\) 個減りますが、\(p\) が \(0\) ならそれ以上減りません。
  つまり区間後の個数は
  • \(p \leftarrow \max(0,\, p - F_i)\) と表せます。
• 到着時に \(p \ge 1\) なら 1 個渡して
  • \(p \leftarrow p - 1\) となり、その友人は受け取れた（人数カウント +1）ことになります。

素朴な方法がダメな理由

各つまずきを 1 回ずつシミュレーションすると、合計つまずき回数 \(\sum F_i\) が最大で \(2\times 10^5 \times 10^9\) になり得て、到底間に合いません（TLE）。

解決策

「つまずき \(F_i\) 回」をまとめて処理して \(p\) を一気に減らします。
特に \(F_i \ge p\) のときは必ず \(p\) が \(0\) になるので、そこで打ち切れます。

具体例

例えば \(N=3\), \((F_1,F_2,F_3)=(1,5,0)\)、初期 \(p=3\) とすると： - 友人1まで：\(p=3-1=2\)、渡して \(p=1\)（1人） - 友人2まで：\(p=1-5 \rightarrow 0\)、渡せない（1人のまま） - 友人3まで：\(p=0\)、渡せない
答えは 1 人です。

アルゴリズム

1. プレゼントの残数 \(p\) を \(N\)、答え \(ans=0\) で初期化する。
2. \(i=1\) から \(N\) まで順に処理：
   1. つまずきで減る分を反映：
      • \(p>0\) なら
        
      • \(F_i \ge p\) のとき \(p \leftarrow 0\)
      • そうでなければ \(p \leftarrow p - F_i\)
        • \(p=0\) なら何もしない
   2. 到着時に \(p>0\) なら 1 個渡す：
      • \(p \leftarrow p - 1\)
      • \(ans \leftarrow ans + 1\)
3. \(ans\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各友人につき定数回の計算）
• 空間計算量: \(O(N)\)（入力配列を保持する分。逐次読みでも解ける）

実装のポイント

• \(F_i\) が非常に大きいので、必ず「まとめて減算」する（1回ずつ減らさない）。

• \(p\) が \(0\) のときは何をしても増えないので、分岐で無駄な計算を避けられます。

• 入力が最大 \(2\times 10^5\) 行あるため、sys.stdin.buffer.read() のような高速入力が安全です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    F = data[1:]
    p = N
    ans = 0
    for i in range(N):
        fi = F[i]
        if p > 0:
            if fi >= p:
                p = 0
            else:
                p -= fi
        if p > 0:
            p -= 1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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