概要

一列に並んだ荷物から、連続する区間（重さの合計が \(K\) 以下）を繰り返し搬出するとき、最大何個の荷物を搬出できるかを求める問題です。答えは「重さが \(K\) 以下である荷物の個数」に等しくなります。

考察

重要な気づき：搬出できる荷物の条件

まず、重さが \(K\) を超える荷物（\(A_i > K\)）は、単独でも搬出できないため、絶対に搬出できません。

次に、重さが \(K\) 以下の荷物（\(A_i \leq K\)）は、必ず搬出できることを示します。

なぜ \(A_i \leq K\) なら必ず搬出できるのか

搬出操作では「現在残っている列で連続する区間」を選びます。荷物を1個だけ選ぶ（区間の長さ1）ことも許されています。

したがって、\(A_i \leq K\) である荷物は、たとえ他の荷物に挟まれていても、その荷物1個だけを区間として選んで搬出すればよいのです。

具体例で確認しましょう。荷物が \([3, 100, 5, 100, 2]\) で \(K = 10\) のとき：

• \(A_1 = 3 \leq 10\)：1個だけ選んで搬出可能
• \(A_2 = 100 > 10\)：搬出不可能
• \(A_3 = 5 \leq 10\)：1個だけ選んで搬出可能
• \(A_4 = 100 > 10\)：搬出不可能
• \(A_5 = 2 \leq 10\)：1個だけ選んで搬出可能

答えは \(3\) です。

まとめて搬出する方が得になることはないのか？

複数の荷物をまとめて搬出すれば操作回数は減りますが、問題で問われているのは「搬出できる荷物の最大個数」です。操作回数に制限はないため、1個ずつ搬出しても損にはなりません。

逆に、まとめて搬出しようとすると合計が \(K\) を超えて搬出できないケースが生じるだけで、個数が増えることはありません。

結論

搬出できる荷物の最大個数 \(=\) \(A_i \leq K\) を満たす \(i\) の個数

アルゴリズム

1. 各荷物 \(A_i\) について、\(A_i \leq K\) かどうかを判定する。
2. \(A_i \leq K\) を満たす荷物の個数を数え、それを出力する。

計算量

• 時間計算量: \(O(N)\)（各荷物を1回ずつ確認するだけ）
• 空間計算量: \(O(N)\)（入力の読み込み分。逐次読み込みにすれば \(O(1)\) も可能）

実装のポイント

• \(K\) や \(A_i\) が最大 \(10^{18}\) と非常に大きいため、C++ などでは long long を使う必要があります。Python では整数のオーバーフローを気にする必要はありません。

• 操作の自由度が高く一見複雑に見えますが、「1個ずつ搬出すれば十分」という本質に気づけば、非常にシンプルな実装になります。

  ソースコード

def main():
    import sys
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    count = 0
    for i in range(N):
        if int(input_data[2 + i]) <= K:
            count += 1
    print(count)

main()

---

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