概要

高橋君が \(N\) 個のプレゼントを持って \(N\) 人の友人を順に訪問する際、道中でつまずいてプレゼントを落としながらも、各友人にプレゼントを渡せるかをシミュレーションする問題です。

考察

この問題は、プレゼントの個数を管理しながら順番に処理していく単純なシミュレーションで解けます。

重要な観察は以下の通りです：

• 友人 \(i\) の家に向かう途中で \(F_i\) 回つまずくが、プレゼントが \(0\) 個になったらそれ以上減らない
• つまり、友人 \(i\) の家に到着した時点でのプレゼント数は \(\max(\text{現在のプレゼント数} - F_i, 0)\) で計算できる
• 到着時にプレゼントが \(1\) 個以上あれば渡す（プレゼント数が \(1\) 減る）

具体例: \(N = 3\), \(F = [2, 1, 0]\) の場合

答え: 1人

\(F_i\) が非常に大きい値（最大 \(10^9\)）になる可能性がありますが、1回ずつプレゼントを落とすシミュレーションを \(F_i\) 回繰り返すと TLE になります。しかし、\(\max(\text{プレゼント数} - F_i, 0)\) という式で一度に計算すれば、\(O(1)\) で処理できます。

アルゴリズム

1. プレゼントの数を \(N\) で初期化する
2. 友人 \(1\) から友人 \(N\) まで順に以下を行う：
   • プレゼント数を \(\max(\text{プレゼント数} - F_i, 0)\) に更新する（つまずきによる損失）
   • プレゼント数が \(1\) 以上であれば、プレゼントを \(1\) 個渡し（カウントを増やす）、プレゼント数を \(1\) 減らす
3. カウントを出力する

計算量

• 時間計算量: \(O(N)\) — 各友人について \(O(1)\) の処理を行う
• 空間計算量: \(O(1)\) — プレゼント数とカウントの変数のみ使用

実装のポイント

• \(F_i\) が最大 \(10^9\) と非常に大きいため、for ループで \(1\) 回ずつ減らすのではなく、max(presents - F, 0) で一括計算することが重要です

• Python では max 関数を使うことで、プレゼント数が負にならないよう簡潔に書けます

• 入力を1行ずつ読み込みながら処理すれば、全体を配列に格納する必要もなく、メモリ効率も良くなります

  ソースコード

N = int(input())
presents = N
count = 0
for _ in range(N):
    F = int(input())
    presents = max(presents - F, 0)
    if presents >= 1:
        presents -= 1
        count += 1
print(count)

この解説は claude4.6opus-thinking によって生成されました。