概要

高橋君がN人の友人に順番にプレゼントを配る際、各友人の家への道中でつまずく回数と到着時のプレゼント配布の条件から、プレゼントを受け取れた友人の人数を求める問題です。

考察

問題を解く鍵は、現在持っているプレゼント数（current）と各友人iへの道中でのつまずき回数（F_i）の関係を適切に処理することにあります。重要な観察点は以下の通りです：

1. つまずきによるプレゼント減少は、現在持っているプレゼント数が0でない場合にのみ発生します
2. 友人iにプレゼントを渡せる条件は、到着時にプレゼントが1個以上あることです
3. 各ステップで、現在のプレゼント数がF_iより大きいかどうかで処理が分かれます

素朴なアプローチとして、各ステップでF_i回のつまずきを1回ずつシミュレーションすると、F_iが最大10^9まで大きくなるため、明らかに時間計算量がO(N×max(F_i))となり、制約条件下ではTLEとなります。

アルゴリズム

効率的なアルゴリズムは以下のように動作します：

1. 初期状態：プレゼント数current = N、カウントcount = 0
2. 各友人i（0-indexed）について：
   • current > F_iの場合：
     • つまずきでF_i個減少し、到着時に1個渡すので、合計(F_i + 1)個減少
     • currentから(F_i + 1)を引く
     • プレゼントを渡せたのでcountを1増やす
   • current ≤ F_iの場合：
     • つまずきでcurrent個まで減少（0個以下にはならない）
     • 到着時にはプレゼントが0個なので何も渡せない
     • currentを0に設定

このアルゴリズムでは、各友人に対する処理が定数時間で行えるため、効率的に計算できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力データの格納に必要な分）

実装のポイント

1. 入力データを一度に読み込むことで効率化

2. 条件分岐を明確にし、数値の更新を適切に行う

3. currentが負になる場合を防ぐためにmin関数を使用

4. 各ステップで現在のプレゼント数を更新しながら、プレゼントを渡せたかどうかを判定

   ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    F = list(map(int, data[1:1+n]))
    
    current = n
    count = 0
    
    for i in range(n):
        if current > F[i]:
            current -= (F[i] + 1)
            count += 1
        else:
            current = min(current, current - F[i])
            if current < 0:
                current = 0
                
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3.1 によって生成されました。