概要

各回で「合計 \(K\) 以下の連続区間」を取り除けるとき、最終的に搬出できる荷物の最大個数を求める問題です。結論として、答えは \(A_i \le K\) を満たす荷物の個数になります。

考察

重要な観察は次の2点です（制約より \(A_i \ge 1\) の正の整数であることが効きます）。

1. \(A_i > K\) の荷物は絶対に搬出できない

どんな搬出操作でも選ぶ区間の重さ合計は \(K\) 以下でなければなりません。
しかし \(A_i > K\) の荷物を含む区間を選ぶと、その区間の合計は少なくとも \(A_i\) なので必ず \(K\) を超えます（他の荷物は正なので足すほど増える）。

したがって、\(A_i > K\) の荷物はどの操作でも取り除けません。

2. \(A_i \le K\) の荷物は必ず搬出できる

逆に \(A_i \le K\) なら、その荷物だけの区間（長さ1）を選べば合計は \(A_i \le K\) なので、単独で搬出可能です。
これを全ての \(A_i \le K\) について繰り返せばよく、途中で列が詰まって隣接関係が変わっても「単独で選ぶ」戦略には影響がありません。

以上より、 - 搬出できない荷物：\(A_i > K\) - 必ず搬出できる荷物：\(A_i \le K\)

なので最大搬出個数は \(A_i \le K\) の個数です。

（例）\(K=5,\ A=[2,7,3,10,5]\)
\(7,10\) は \(K\) を超えるので絶対に無理。\(2,3,5\) は単独で搬出できるので最大は \(3\) 個。

素朴なアプローチが不要な理由

一見すると「区間を選ぶ」ので、貪欲やDPで最適な区間の取り方を考えたくなります。しかし上の観察により、区間の取り方を工夫しても \(A_i>K\) を消せないため、問題は単なる個数カウントに帰着します。
そのため、区間探索やシミュレーション（最悪 \(O(N^2)\) など）は過剰で、制約 \(N \le 2\times 10^5\) では無駄になります。

アルゴリズム

1. 配列 \(A\) を左から順に見る。
2. \(A_i \le K\) ならカウントを1増やす。
3. カウントを出力する。

これが最大搬出個数です（各荷物は単独搬出でき、\(A_i>K\) は不可能）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力を逐次処理するなら追加配列不要）

実装のポイント

• \(K, A_i\) が最大 \(10^{18}\) ですが、Python の int ならそのまま扱えます。

• A = map(int, input().split()) として逐次走査し、sum(1 for x in A if x <= K) で簡潔に数えられます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())
    ans = sum(1 for x in A if x <= K)
    print(ans)

if __name__ == "__main__":
    main()

---

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