概要

\(N\) 個のプレゼントを持って \(N\) 人の友人の家を順番に訪れ、道中でつまずいて落としたり友人に渡したりしながら、最終的に何人の友人にプレゼントを渡せるかをシミュレーションする問題です。

考察

この問題で重要なのは、「高橋君が今何個のプレゼントを持っているか」という状態を順番に更新していくことです。

1. 初期状態: 最初に持っているプレゼントは \(N\) 個です。
2. 道中での紛失: 友人 \(i\) の家に行くまでに \(F_i\) 回つまずきます。プレゼントを \(1\) 個以上持っていれば \(1\) 個減りますが、\(0\) 個なら何も起きません。これは、数式で表すと 現在の個数 = max(0, 現在の個数 - F_i) となります。
3. プレゼントを渡す: 友人 \(i\) の家に着いたとき、プレゼントが \(1\) 個以上あれば \(1\) 個渡し、渡せた人数をカウントします。

制約を見ると、友人の数 \(N\) は最大 \(2 \times 10^5\) です。友人 \(1\) から \(N\) まで順番に処理を行えば、合計 \(N\) 回の計算で済むため、制限時間内に十分に間に合います。 つまずく回数 \(F_i\) は最大 \(10^9\) と非常に大きいですが、持っているプレゼントの数（最大 \(N\)）から引くだけなので、計算量には影響しません。

アルゴリズム

以下の手順でシミュレーションを行います。

1. プレゼントの現在の所持数 current_presents を \(N\) で初期化し、渡せた人数 count を \(0\) で初期化します。
2. \(i = 1, 2, \dots, N\) について、以下の処理を繰り返します。
   • current_presents から \(F_i\) を引きます。もし結果がマイナスになる場合は \(0\) にします。
   • もし current_presents が \(1\) 以上であれば：
     • current_presents を \(1\) 減らします。
     • count に \(1\) 加算します。
3. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 友人の数 \(N\) に対して、ループを \(1\) 回回すだけなので、入力の大きさに比例した時間で終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(F_i\) の値をすべてリストに保持する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• 大きな入力の読み込み: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() を使って一括で入力を読み込むと実行速度が向上します。

• プレゼントが 0 個未満にならない処理:

  current_presents -= f_i
  if current_presents < 0:
    current_presents = 0
  

  このように、引き算の後に \(0\) と比較して補正することで、「プレゼントがない状態でつまずいても何も起こらない」という条件を正しく実装できます。

  ソースコード

import sys

def main():
    # 入力を一括で読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 友人の人数
    n = int(input_data[0])
    
    # current_presents: 現在持っているプレゼントの数（最初はN個）
    current_presents = n
    # count: プレゼントを渡せた友人の人数
    count = 0
    
    # 友人1から友人Nまで順番に処理
    for i in range(1, n + 1):
        # f_i: 友人iの家に向かう道中でつまずく回数
        f_i = int(input_data[i])
        
        # つまずくたびにプレゼントを1個失う（0個未満にはならない）
        current_presents -= f_i
        if current_presents < 0:
            current_presents = 0
            
        # 友人iの家に到着したとき、プレゼントがあれば1個渡す
        if current_presents > 0:
            current_presents -= 1
            count += 1
            
    # 結果を出力
    print(count)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。