概要

一直線上に並んだ宝箱から魔法の杖を使ってコインを回収し、合計コイン数を求める問題です。

考察

問題を素朴に解くには、各魔法に対して全ての宝箱をチェックして範囲内にあるか判定する方法が考えられますが、これでは計算量が \(O(N \times M)\) となり、\(N, M\) が最大 \(2 \times 10^5\) の場合 \(4 \times 10^{10}\) 回の操作が必要で現実的ではありません。

効率的に解くためには、以下の観察が重要です： 1. 宝箱は座標順にソート可能 2. 各魔法の範囲 \([L_j, R_j]\) に対して、対応する宝箱のインデックス範囲を二分探索で高速に特定できる 3. 連続した魔法の処理では、前回の処理結果を活用できる可能性がある

アルゴリズム

1. 前処理: 宝箱を座標 \(X_i\) でソートし、座標リストとコインリストを作成
2. イベント処理: 魔法の範囲を \(L_j\) を優先キー、\(R_j\) を副キーとしてソート
3. 範囲特定: 各魔法に対して、二分探索で範囲内の宝箱の開始インデックスと終了インデックスを特定
4. アクティブリスト管理: 現在の魔法の範囲内にある宝箱のインデックスを保持するリストを管理
   • 前回の処理結果を活用しながら、新しい範囲に含まれる宝箱を追加
   • 範囲外になった宝箱をリストから除去
5. 合計計算: アクティブリスト内の宝箱のコインを合計に加算し、リストをクリア

このアプローチでは、各宝箱が最大1回しかアクティブリストに追加されず、各魔法の処理で範囲外の宝箱の除去が行われます。

計算量

• 時間計算量: \(O(N \log N + M \log M + M \log N)\)
  • 宝箱のソート: \(O(N \log N)\)
  • 魔法のソート: \(O(M \log M)\)
  • 各魔法での二分探索: \(O(M \log N)\)
  • アクティブリストの操作: 合計 \(O(N)\)
• 空間計算量: \(O(N + M)\)

実装のポイント

• 二分探索モジュール bisect を活用して範囲内の宝箱インデックスを効率的に特定

• アクティブリストを活用して重複計算を回避

• イテレータを使用して大量データの読み込みを効率化

• ソート順を工夫することで、連続する魔法の処理を最適化

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    chests = []
    for _ in range(n):
        x = int(next(it)); c = int(next(it))
        chests.append((x, c))
    
    chests.sort(key=lambda x: x[0])
    xs = [x for x, c in chests]
    coins = [c for x, c in chests]
    
    events = []
    for _ in range(m):
        l = int(next(it)); r = int(next(it))
        events.append((l, r))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    import bisect
    total = 0
    ptr = 0
    active = []
    
    for l, r in events:
        left_idx = bisect.bisect_left(xs, l)
        right_idx = bisect.bisect_right(xs, r) - 1
        
        if left_idx > right_idx:
            continue
            
        while ptr <= right_idx:
            if ptr >= left_idx:
                active.append(ptr)
            ptr += 1
        
        while active and xs[active[0]] < l:
            active.pop(0)
            
        while active and xs[active[-1]] > r:
            active.pop()
            
        for idx in active:
            total += coins[idx]
        active.clear()
    
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。