概要

高橋君が \(N\) 人の友人に順番にプレゼントを配るとき、途中でつまずいてプレゼントを失う可能性がある。最終的に何人の友人にプレゼントを渡すことができるかを求める問題。

考察

この問題では、高橋君が最初に \(N\) 個のプレゼントを持っており、各友人 \(i\) の家に向かう途中で \(F_i\) 回つまずく。つまずくたびに持っているプレゼントが1個減るが、0個のときは何も起こらない。友人の家に着いたら、持っているプレゼントがあれば1個を渡す。

素朴な方法として、実際に毎回1個ずつ減らすシミュレーションを行うと、最悪の場合 \(F_i\) が \(10^9\) になるため、全体で \(O(N \cdot F_i)\) の計算量となり、TLE（時間超過）になる。

そこで重要なのは、「つまずいた回数 \(F_i\)」に対して毎回処理をするのではなく、現在持っているプレゼントの数と比較して「最大で何回つまずけるか」だけを考えることである。つまり、持っているプレゼントの数が \(x\) で、つまずく回数が \(f\) 回なら、実際に失うプレゼントの数は \(\min(x, f)\) 個となる。

このように、つまずきによるプレゼントの減少を一括で処理することで、ループ回数を大幅に削減できる。

さらに、プレゼントを渡せるかどうかは「その時点で持っているプレゼントが1個以上か」だけで決まるので、シミュレーションは各友人に対して定数時間で行える。

アルゴリズム

1. 最初に持っているプレゼントの数は \(N\) 個。
2. 各友人 \(i\) について以下の処理を行う：
   • つまずく回数 \(F_i\) に対して、持っているプレゼントの数を \(\max(0, \text{present} - F_i)\) に更新。
   • その後、持っているプレゼントが1個以上あれば1個渡し、カウントを増やす。
3. 全ての友人に対する処理が終わったら、カウントを出力。

この方法により、各友人に対して定数時間の処理で答えを求めることができる。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• sys.stdin.read を使うことで高速な入力処理を行う（Pythonでは重要）。

• min(present, f) を使って、つまずきによるプレゼントの減少を効率的に処理する。

• カウントはプレゼントを実際に渡したときだけ増やす。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    F = list(map(int, data[1:N+1]))
    
    present = N
    count = 0
    
    for f in F:
        # Reduce presents due to stumbling
        if present > 0:
            present -= min(present, f)
        
        # Give present to friend if possible
        if present > 0:
            present -= 1
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。