概要

\(N\) 冊の本を、重さの条件を満たす本棚の \(M\) 個の空きスペースのうち「最も左側にあるもの」に順番に置いていき、最終的に何冊の本を置くことができるかを求める問題です。

考察

各本について、条件を満たすスペースを左から順番に探すという素朴な方法（線形探索）を考えてみます。 この場合、1冊の本に対して最大 \(M\) 個のスペースを確認する必要があるため、最悪のケースでの計算量は \(O(N \times M)\) となります。本問題の制約では \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（TLE）を超えてしまいます。

効率的に解くためには、以下の2点を高速に行う必要があります。 1. 耐荷重が \(R_i\) 以上である空きスペースのうち、最もインデックスが小さいものを探す。 2. 本を置いたスペースを「使用済み」として更新する。

これを実現するために、セグメント木（Segment Tree）というデータ構造を利用します。

アルゴリズム

セグメント木の各ノードに、その区間内にある空きスペースの「耐荷重の最大値」を保持させます。

1. セグメント木の構築

本棚の各スペースの耐荷重 \(C_1, C_2, \ldots, C_M\) を葉（最下層）に並べ、親ノードには左右の子の最大値を持たせます。これにより、任意の区間内における最大耐荷重を \(O(1)\) で参照できるようになります。

2. 条件を満たすスペースの探索

ある重さ \(R_i\) の本を置く場所を探す際、木の根（全体範囲）から以下のように探索します（\(O(\log M)\)）： - 現在のノードの最大値が \(R_i\) 未満であれば、その区間に置ける場所はありません。 - 左側の子ノードの最大値が \(R_i\) 以上であれば、左側の区間に条件を満たすスペースが存在するため、左へ進みます。 - 左側の子ノードの最大値が \(R_i\) 未満で、右側の子ノードの最大値が \(R_i\) 以上であれば、右へ進みます。

これを葉に到達するまで繰り返すことで、「条件を満たす最も左側のスペース」を高速に見つけることができます。

3. スペースの更新

本を置いたスペースの耐荷重を \(0\) に書き換えます。その後、その葉から根に向かって最大値を再計算し、木の状態を更新します（\(O(\log M)\)）。

4. 全体の流れ

すべての本 \(R_1, R_2, \ldots, R_N\) について上記の探索と更新を繰り返します。本を置くことができた回数をカウントし、最終的な答えとします。

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • セグメント木の構築に \(O(M)\)
  • 各本に対する探索と更新に \(O(\log M)\)。これが \(N\) 冊分あるため \(O(N \log M)\) となります。
• 空間計算量: \(O(M)\)
  • セグメント木を管理するための配列に \(O(M)\) のメモリを使用します。

実装のポイント

• セグメント木のサイズ: \(M\) 以上の最小の2のべき乗（\(2^k\)）を葉の数とすることで、実装がシンプルになります。

• 高速な入出力: Pythonの場合、データ量が多い（\(4 \times 10^5\) 個以上の整数）ため、sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 更新の最適化: 親ノードの値を更新する際、値が変化しなくなった時点で更新を打ち切ることで、定数倍の高速化が期待できます。

  ソースコード

import sys

# 本棚への配架問題を解決するために、セグメント木（Segment Tree）を使用します。
# セグメント木は、各区間における耐荷重の最大値を保持します。
# これにより、ある重さ以上の耐荷重を持つ「最も左側（番号が小さい）の空きスペース」を効率的に探索できます。

def solve():
    # 標準入力からすべてのデータを一括で読み込み、高速化を図ります。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 本の冊数, M: 本棚のスペース数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # R: 各本の重さ, C: 各スペースの耐荷重
    R = list(map(int, input_data[2:2+N]))
    C = list(map(int, input_data[2+N:2+N+M]))
    
    # セグメント木のサイズを決定します（M以上の最小の2のべき乗）。
    size = 1
    while size < M:
        size <<= 1
    
    # tree[1]をルートとし、tree[size]以降を葉とする配列を初期化します。
    # 各要素は、その範囲内にある空きスペースの耐荷重の最大値を表します。
    tree = [0] * (2 * size)
    for i in range(M):
        tree[size + i] = C[i]
    
    # ボトムアップでセグメント木を構築します。
    for i in range(size - 1, 0, -1):
        left_val = tree[i << 1]
        right_val = tree[(i << 1) | 1]
        if left_val > right_val:
            tree[i] = left_val
        else:
            tree[i] = right_val
            
    placed_books_count = 0
    
    # 各本について順番に配架場所を検討します。
    for r in R:
        # 本棚全体の最大耐荷重が本の重さ未満であれば、その本は置けません。
        if tree[1] < r:
            continue
        
        # 条件を満たす最も左側のスペースを木の上から探索します。
        idx = 1
        while idx < size:
            left_child = idx << 1
            # 左側の子（より小さい番号のスペースを含む範囲）に条件を満たすスペースがあるか確認
            if tree[left_child] >= r:
                idx = left_child
            else:
                # 左側にない場合は右側の子へ
                idx = left_child | 1
        
        # 本を置くことができたのでカウントを増やします。
        placed_books_count += 1
        
        # 本を置いたスペースの耐荷重を0に更新（既に使用済みであることを示す）。
        tree[idx] = 0
        
        # 木を葉からルートに向かって更新します。
        idx >>= 1
        while idx >= 1:
            left_val = tree[idx << 1]
            right_val = tree[(idx << 1) | 1]
            
            if left_val > right_val:
                new_max = left_val
            else:
                new_max = right_val
            
            # 最大値が変化しなくなったら、それ以上の親の更新は不要です。
            if tree[idx] == new_max:
                break
            tree[idx] = new_max
            idx >>= 1
                
    # 最終的に本棚に置くことができた本の冊数を出力します。
    sys.stdout.write(str(placed_books_count) + '\n')

if __name__ == '__main__':
    solve()

---

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