概要

左から順に棚の商品数を足し合わせていき、累積和が初めて \(X\) 以上になる位置（棚番号）を求める問題です。
見つかった時点でその番号を出力し、最後まで届かなければ -1 を出力します。

考察

重要な観察は次の1点です：

• 「初めて \(X\) 以上になる瞬間」を知りたいだけなので、左から1回見るだけで十分。

例えば \(A = [2, 4, 3, 5], X = 8\) のとき： - 1番目まで：\(2\) - 2番目まで：\(2+4=6\) - 3番目まで：\(6+3=9 \ge 8\)

初めて条件を満たすのは3番目なので答えは 3 です。

素朴でまずい方法として、各 \(k\) ごとに
\(A_1 + \cdots + A_k\) を毎回最初から計算すると、
\(1 + 2 + \cdots + N = O(N^2)\) になり、\(N \le 5 \times 10^5\) では間に合いません。

そこで、現在の合計を変数 s に持っておき、棚を1つ進むたびに s += A_i と更新すれば、各要素を1回ずつ処理するだけで済みます。これで高速に解けます。

アルゴリズム

1. s = 0（現在までの累積和）を用意する。
2. 棚を左から順に見る（i = 1..N）。
3. 各棚で s += A_i。
4. もし s >= X になったら、その時の i を出力して終了。
5. 最後まで s < X のままなら -1 を出力。

この処理は「初めて条件を満たす位置」をそのままシミュレーションしています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

• enumerate(A, 1) を使うと棚番号を1始まりで扱えて、そのまま出力できます。

• 合計値は最大で \(N \times A_i \approx 5 \times 10^{14}\) になり得るため、十分大きい整数型が必要です（Python の int なら問題なし）。

• 条件を満たしたらすぐ return して、最初の位置だけを出力するのがポイントです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    
    s = 0
    for i, a in enumerate(A, 1):
        s += a
        if s >= X:
            print(i)
            return
    print(-1)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。