概要

各棚を入口側から順に見ていき、商品数の累積和 \(A_1 + A_2 + \cdots + A_k\) を管理します。
その累積和が初めて \(X\) 以上になった棚番号を出力し、最後まで届かなければ -1 を出力すればよい問題です。

考察

求めたいのは、最初に累積和が \(X\) 以上になる位置です。

例えば
\(A = [2, 3, 1, 5, 4]\), \(X = 10\) のとき、累積和は

• 1番目まで: \(2\)
• 2番目まで: \(2+3=5\)
• 3番目まで: \(2+3+1=6\)
• 4番目まで: \(2+3+1+5=11\)

となり、初めて \(10\) 以上になるのは 4番目 です。

素朴な方法

各 \(k\) について毎回 \(A_1 + A_2 + \cdots + A_k\) を最初から計算すると、
合計で

\[ 1 + 2 + 3 + \cdots + N = O(N^2) \]

かかってしまいます。

\(N \leq 5 \times 10^5\) なので、\(O(N^2)\) では間に合いません。

どう改善するか

一度見た棚までの合計を変数 s に持っておけば、次の棚に進むたびに

\[ s \leftarrow s + A_i \]

と更新するだけで済みます。
これなら各棚を 1 回ずつ見るだけなので、全体で \(O(N)\) です。

アルゴリズム

1. 累積和 s = 0 を用意する。
2. 棚を 1 番目から順に見る。
3. 各棚 \(i\) について s += A_i を行う。
4. もし s >= X になったら、その時点の棚番号 \(i\) を出力して終了する。
5. 最後まで見ても一度も s >= X にならなければ -1 を出力する。

計算量

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

実装のポイント

• 棚番号は 1 始まり なので、enumerate(A, 1) を使うとそのまま答えの番号が得られます。

• 条件を満たしたらすぐ print(i) して return すれば、余計な処理をしなくて済みます。

• \(X\) は最大で \(10^{15}\) ですが、Python の整数型ならそのまま安全に扱えます。

• この実装では高速入力のために sys.stdin.buffer.read() を使っています。制約が大きいので有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, X = data[0], data[1]
    A = data[2:2 + N]

    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.4-high によって生成されました。