概要

\(N\) 冊の本を順番に、耐荷重の条件を満たす最も左の空きスペースに配架していき、最終的に置けた本の冊数を求める問題です。セグメント木を使って「条件を満たす最左位置」を高速に求めます。

考察

素朴なアプローチの問題点

各本について、スペースを左から順に走査して「まだ使われていない＆耐荷重が足りる」スペースを見つける方法が最も直感的です。しかし、この方法では最悪の場合、本1冊あたり \(O(M)\) かかり、全体で \(O(N \times M)\) となります。\(N, M\) が最大 \(2 \times 10^5\) なので、\(4 \times 10^{10}\) 程度の計算量となり TLE になります。

重要な気づき

必要な操作は以下の2つです：

1. 検索: 空きスペースの中で「耐荷重が \(R_i\) 以上」を満たす最も左の位置を見つける
2. 更新: 本を置いたスペースを「使用済み」にする（もう選ばれないようにする）

これはセグメント木を使えば、どちらの操作も \(O(\log M)\) で実現できます。

アルゴリズム

セグメント木による解法

セグメント木の各ノードに、その区間内の耐荷重の最大値を持たせます。

検索（find_leftmost_ge）

値 \(val\) 以上の耐荷重を持つ最左のスペースを見つけるには、根から以下のように木を降りていきます：

1. 根ノードの最大値が \(val\) 未満なら、条件を満たすスペースは存在しない → \(-1\) を返す
2. 左の子の最大値が \(val\) 以上なら、左の子に進む（左側に条件を満たす位置がある）
3. そうでなければ右の子に進む
4. 葉ノードに到達したら、その位置が答え

この探索は木の高さ分だけ進むので \(O(\log M)\) です。

更新（update）

本を置いたスペースの耐荷重を \(0\) に書き換えます（\(R_i \geq 1\) なので、\(0\) にすれば二度と選ばれません）。葉から根に向かって最大値を再計算し、\(O(\log M)\) で完了します。

全体の流れ

1. 耐荷重配列 \(C\) でセグメント木を構築する
2. 本 \(1, 2, \ldots, N\) を順番に処理する
   • セグメント木で \(R_i\) 以上の最左位置を検索
   • 見つかれば、そのスペースの値を \(0\) に更新し、カウントを \(+1\)
   • 見つからなければスキップ
3. カウントを出力

具体例

\(M = 5\), スペースの耐荷重が \(C = [3, 1, 4, 1, 5]\) のとき、セグメント木の根には最大値 \(5\) が入ります。

• 重さ \(2\) の本 → 左から探して \(C_1 = 3 \geq 2\) → スペース1に配架、\(C_1\) を \(0\) に更新
• 重さ \(4\) の本 → \(C_1=0, C_2=1, C_3=4 \geq 4\) → スペース3に配架、\(C_3\) を \(0\) に更新
• 重さ \(5\) の本 → \(C_5 = 5 \geq 5\) → スペース5に配架

計算量

• 時間計算量: \(O((N + M) \log M)\) — セグメント木の構築に \(O(M)\)、各本の処理に \(O(\log M)\)
• 空間計算量: \(O(M)\) — セグメント木の配列サイズ

実装のポイント

• セグメント木のサイズは \(M\) 以上の最小の2冪にする。余った葉は \(0\) で埋めることで、耐荷重の条件 \(R_i \geq 1\) を満たさず自然に無視される。

• 使用済みスペースの耐荷重を \(0\) に更新することで、以降の検索で自動的にスキップされる仕組みになっている。

• Python では入力を stdin.buffer.read() でまとめて読み込むことで、入力処理の高速化を図っている。

  ソースコード

import sys
from sys import stdin

def main():
    input_data = stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    R = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(M)]; idx += M

    # Segment tree with max, supporting:
    # - query: find leftmost position where C[pos] >= value
    # - update: set position to -infinity (mark as used)
    
    size = 1
    while size < M:
        size *= 2
    
    tree = [0] * (2 * size)
    
    # Build
    for i in range(M):
        tree[size + i] = C[i]
    for i in range(M, size):
        tree[size + i] = 0
    for i in range(size - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    
    def find_leftmost_ge(val):
        # Find leftmost index where C[index] >= val
        if tree[1] < val:
            return -1
        node = 1
        while node < size:
            if tree[2 * node] >= val:
                node = 2 * node
            else:
                node = 2 * node + 1
        return node - size
    
    def update(pos, val):
        pos += size
        tree[pos] = val
        pos >>= 1
        while pos >= 1:
            tree[pos] = max(tree[2 * pos], tree[2 * pos + 1])
            pos >>= 1
    
    count = 0
    for i in range(N):
        pos = find_leftmost_ge(R[i])
        if pos != -1:
            count += 1
            update(pos, 0)
    
    print(count)

main()

---

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