概要

\(N\) 個の棚を順番に見ていき、商品の合計数が初めて閾値 \(X\) 以上になるのは何番目の棚かを求める問題です。もし最後まで見ても \(X\) に達しない場合は -1 を出力します。

考察

この問題で重要な点は、「前から順番に足していき、条件を満たした瞬間に終了する」というシンプルなシミュレーションで解けるという点です。

各棚の商品数 \(A_i\) は \(1\) 以上の正の整数であるため、棚を読み進めるほど商品の合計数は必ず増えていきます（単調増加）。したがって、途中で合計が \(X\) を超えた後に、再び \(X\) 未満に戻ることはありません。

• 素朴なアプローチ: 1番目の棚から順に合計を計算し、その値が \(X\) 以上になったらその時の番号を出力してプログラムを終了します。
• 注意点:
  • \(X\) は最大 \(10^{15}\) と非常に大きくなる可能性があるため、合計値を保持する変数は大きな数（64ビット整数など）を扱える必要があります。Pythonの場合は標準の int 型で自動的に大きな値を扱えるため、オーバーフローの心配はありません。
  • \(N\) が最大 \(5 \times 10^5\) と大きいため、効率的な入出力やループ処理が求められます。

アルゴリズム

1. 現在の商品の合計を保持する変数 current_sum を \(0\) で初期化します。
2. 棚の番号 \(i = 1, 2, \dots, N\) について、以下の操作を繰り返します。
   • current_sum に \(i\) 番目の棚の商品数 \(A_i\) を加算する。
   • もし current_sum >= X ならば、現在の棚の番号 \(i\) を出力して処理を終了する。
3. 全ての棚を調べ終えても current_sum が \(X\) に達しなかった場合は、-1 を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 棚の数 \(N\) に対して、各棚の商品数を 1 回ずつ確認するため、計算量は \(N\) に比例します。\(N \le 5 \times 10^5\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 入力された \(A_1, \dots, A_N\) をリストとして保持する場合、その分のメモリが必要になります。

実装のポイント

• 1-indexed への対応: プログラミング言語の配列（リスト）は通常 0 番目から始まりますが、問題文では棚の番号は 1 番目から始まっています。出力する際に i + 1 とするか、ループの範囲に注意しましょう。

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() などを使って一括で入力を読み込むと、実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力を高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    X = int(input_data[1])
    A = input_data[2:]
    
    current_sum = 0
    # 各棚の商品数を順番に足していく
    for i in range(N):
        current_sum += int(A[i])
        # 合計が X 以上になった時点でその棚の番号を出力して終了
        if current_sum >= X:
            print(i + 1)
            return
    
    # 全ての棚を確認しても X 以上にならなかった場合
    print("-1")

if __name__ == "__main__":
    solve()

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