概要

棚を順番に見ていき、商品数の累積和が初めて \(X\) 以上になる棚の番号を求める問題です。

考察

この問題では、\(1\) 番目の棚から順に商品数を足していき、その合計が初めて \(X\) 以上になるタイミングを見つける必要があります。

具体例で考えてみましょう。

例えば \(N = 5\)、\(X = 10\)、\(A = [3, 4, 5, 2, 1]\) の場合：

よって答えは \(3\) です。

素朴なアプローチで十分か？

この問題は、前から順に足していくだけの単純な線形走査で解けます。棚の数 \(N\) は最大 \(5 \times 10^5\) なので、\(O(N)\) のループを 1 回回すだけで十分に間に合います。特別なアルゴリズム（二分探索など）は不要です。

注意すべき点として、\(X\) が最大 \(10^{15}\)、\(A_i\) が最大 \(10^9\) なので、累積和は非常に大きくなる可能性があります。C++ などでは 64 ビット整数型を使う必要がありますが、Python では整数のオーバーフローが起きないため心配ありません。

アルゴリズム

1. 累積和を管理する変数 total を \(0\) で初期化する。
2. \(i = 1, 2, \ldots, N\) の順に棚を見ていく。
   • total に \(A_i\) を加算する。
   • total \(\geq X\) となったら、その棚番号 \(i\) を出力して終了する。
3. 最後の棚まで見ても total \(< X\) なら -1 を出力する。

計算量

• 時間計算量: \(O(N)\) — 最悪でも全棚を 1 回ずつ見るだけ
• 空間計算量: \(O(N)\) — 入力配列の格納（累積和の計算自体は \(O(1)\) の追加メモリ）

実装のポイント

• 累積和をその場で計算する: 事前に累積和配列を作る必要はなく、ループ中に変数 total に足し込んでいけば十分です。

• 見つかった時点で即座に break する: 「初めて」\(X\) 以上になった棚を求めるので、条件を満たしたらすぐにループを抜けます。

• 棚番号は 1-indexed: 配列のインデックスは \(0\) から始まりますが、出力する棚番号は \(1\) から始まるので i + 1 を出力します。

• \(X\) の上限が \(10^{15}\): Python では整数の桁数に制限がないため問題ありませんが、他の言語では long long 型などを使う必要があります。

  ソースコード

N, X = map(int, input().split())
A = list(map(int, input().split()))

total = 0
result = -1
for i in range(N):
    total += A[i]
    if total >= X:
        result = i + 1
        break

print(result)

この解説は claude4.6opus-thinking によって生成されました。