概要

高橋君が \(N\) 個のプレゼントを持って \(N\) 人の友人の家を順番に訪ねる際、道中で落としたり友人に渡したりした結果、最終的に何人の友人がプレゼントを受け取れるかを求める問題です。

考察

この問題のポイントは、高橋君の行動を時系列に沿って順番にシミュレーションすることです。

1. プレゼントが減るタイミング プレゼントが減るタイミングは 2 つあります。

   • 友人 \(i\) の家に向かう途中でつまずいたとき（\(F_i\) 個減る可能性がある）
   • 友人 \(i\) の家でプレゼントを渡したとき（\(1\) 個減る）

2. 「\(0\) 個未満にならない」という条件 つまずいてプレゼントを落とす際、「持っているプレゼントが \(0\) 個の状態でつまずいた場合は、何も起こらない」とあります。これは、プレゼントの残数を計算した結果がマイナスになる場合は \(0\) で止める（max(0, 残数 - つまずいた回数) とする）必要があることを意味します。

3. 計算量の注意点 つまずく回数 \(F_i\) は最大で \(10^9\) と非常に大きな値です。そのため、「つまずくたびに \(1\) ずつ減らす」という処理をループ（繰り返し）で書くと、制限時間内に終わりません（TLE）。しかし、「一気に \(F_i\) を引いて、\(0\) 未満なら \(0\) に更新する」という計算方法をとれば、各友人に対して定数時間で処理が終わります。

アルゴリズム

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

1. 現在持っているプレゼントの数 current_presents を \(N\) で初期化します。
2. プレゼントを受け取れた人数 count を \(0\) で初期化します。
3. 友人 \(i = 1, 2, \dots, N\) について、以下の処理を順番に行います。
   • 移動中: current_presents から \(F_i\) を引きます。もし結果がマイナスになったら、current_presents を \(0\) にします。
   • 到着時: もし current_presents が \(1\) 以上なら：
     • プレゼントを \(1\) 個渡すため、current_presents を \(1\) 減らします。
     • count に \(1\) 加算します。
4. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\) 友人の人数 \(N\) に対して \(1\) 回ずつループを回し、その中で定数時間の計算を行っているため、友人 \(1\) 人あたり \(O(1)\) で処理できます。
• 空間計算量: \(O(N)\) 入力をリスト等で保持する場合に \(O(N)\) のメモリを使用します。

実装のポイント

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

• マイナスの処理: current_presents -= f_i の後に if current_presents < 0: current_presents = 0 とするか、current_presents = max(0, current_presents - f_i) と書くことで、プレゼントが負の数になるのを防げます。

  ソースコード

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-high によって生成されました。