概要

与えられた \(N\) 個の荷物のうち、重さの合計が \(K\) 以下となる連続区間を選んで取り除く操作を繰り返したとき、最終的に取り除ける荷物の最大個数を求める問題です。

考察

一見すると、「どの区間をどの順番で選ぶか」「隙間を詰めた後にどの荷物が隣接するか」を考える複雑な動的計画法やシミュレーションが必要な問題に見えるかもしれません。しかし、操作の条件を整理すると、非常にシンプルな結論にたどり着きます。

1. 搬出できない荷物の条件 ある荷物の重さ \(A_i\) が \(K\) を超えている場合（\(A_i > K\)）、その荷物を含むどのような連続区間を選んでも、その合計重さは必ず \(K\) を超えてしまいます。したがって、重さが \(K\) より大きい荷物は絶対に搬出することができません。

2. 搬出できる荷物の条件 逆に、ある荷物の重さが \(A_i \le K\) である場合、その荷物は必ず搬出できます。なぜなら、搬出操作では「連続する1個以上の荷物」を選べるため、その荷物1個だけを区間として選べば、合計重さは \(A_i \le K\) となり、条件を満たすからです。

3. 操作の順序と個数の関係 「荷物を取り除いた後に隙間を詰める」というルールにより、元々離れていた荷物同士をまとめて搬出できるようになる場合があります。しかし、本問題で求められているのは「搬出できる荷物の最大個数」です。 荷物をまとめて搬出しても、1つずつバラバラに搬出しても、最終的に取り除ける荷物の総数は変わりません。また、ある荷物を搬出したせいで、本来搬出できたはずの別の荷物が搬出できなくなるという状況も起こりません。

以上のことから、この問題の答えは単純に「重さが \(K\) 以下である荷物の個数」となります。

アルゴリズム

1. 荷物の個数 \(N\) と上限 \(K\) を読み込む。
2. 荷物の重さの配列 \(A\) を順番に確認する。
3. 各 \(A_i\) について、\(A_i \le K\) であればカウントを1増やす。
4. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の荷物を1回ずつ走査して比較を行うため、線形時間で計算が終わります。\(N \le 2 \times 10^5\) という制約下で十分に高速です。
• 空間計算量: \(O(N)\) 入力された荷物の重さをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入力: \(N\) が大きいため、Pythonでは sys.stdin.read().split() を利用して一括で入力を読み込むと実行時間を短縮できます。

• 型変換: 入力は文字列として読み込まれるため、比較を行う前に int() で整数型に変換する必要があります。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    # sys.stdin.read().split() は高速な入力読み込み方法です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合や制約に満たない場合のガード
    if len(input_data) < 2:
        return
    
    # 荷物の数 N とトラックの積載量上限 K を取得
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 荷物の重さのリストを取得（インデックス 2 以降）
    A = input_data[2:]
    
    # 搬出できる荷物の最大数をカウントする
    # 各荷物について、その重さが K 以下であれば、単独で搬出することが可能です。
    # 逆に、重さが K を超える荷物は、どのような連続区間に含まれていても
    # その区間の合計重さが K を超えてしまうため、決して搬出できません。
    # 「荷物を取り除いた後に詰め直す」というルールがありますが、
    # 最終的に搬出できる荷物の数は、各荷物が単独で K 以下であるかどうかにのみ依存します。
    
    removable_count = 0
    # N 個の荷物について順番に判定を行う
    # N は最大 2 * 10^5 であるため、O(N) のループで十分に高速です
    for i in range(N):
        if int(A[i]) <= K:
            removable_count += 1
            
    # 搬出できる荷物の最大数を出力
    print(removable_count)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。