概要

与えられた距離 \(D_i\) がボーナスエリアに含まれるかどうかを判定し、含まれる場合は得点を \(2 \times D_i\)、そうでない場合は \(D_i\) として合計を得点とする問題。

考察

この問題の肝は、「各距離 \(D_i\) が \(M\) 個のボーナスエリアのどれかに含まれるかどうかを高速に判定する」ことです。

素朴な方法では？

最も単純なのは、各 \(D_i\) に対して、すべてのボーナスエリア \((L_j, R_j)\) を見て、\(L_j \leq D_i \leq R_j\) かどうかをチェックすることです。これは1つの \(D_i\) に対して最大 \(M\) 回の比較が必要なので、全体で最大 \(O(N \times M)\) かかります。
制約より、\(N, M\) は最大 \(2 \times 10^5\) なので、最悪ケースで \(4 \times 10^{10}\) 回の計算が必要になり、時間内に処理できません（TLE）。

改善のアイディア

ボーナスエリアは区間（一次元区間）なので、区間をマージして重複や隣接する区間をまとめることで、最終的に「互いに離れた区間のリスト」を作ることができます。
このリストはソートされているので、ある値 \(D_i\) がどの区間に入っているかを二分探索で調べることが可能になります。これにより、1回の判定が \(O(\log M)\) で可能になります。

区間のマージとは？

例えば、区間 \([1,3], [2,5], [6,7]\) は、\([1,5], [6,7]\) とマージできます。このように、重なる区間をまとめておくことで、後の探索が効率的になります。

アルゴリズム

1. まず、すべてのボーナスエリアの区間 \((L_j, R_j)\) を取得し、左端 \(L_j\) で昇順にソートします。
2. ソートされた区間を前から見ながら、重なる・または隣接する区間をマージしていきます（隣接とは \(R_{prev} + 1 \geq L_{next}\) のとき）。
3. 各投擲の距離 \(D_i\) について、マージされた区間リストに対して二分探索を行い、\(D_i\) が含まれる区間があるかを判定します。
4. 含まれる場合は得点 \(2 \times D_i\)、そうでない場合は \(D_i\) を加算します。

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • 区間のソートに \(O(M \log M)\)
  • マージに \(O(M)\)
  • 各 \(D_i\) に対する二分探索に \(O(N \log M)\)
• 空間計算量: \(O(M + N)\)
  • 区間の保存および入力の保持

実装のポイント

• bisect モジュールを使うことで、二分探索が簡単に実装できます。

• マージの条件は「現在の区間の左端が、前の区間の右端以下（または+1）」のときに結合します。

• ボーナスエリアがなくてもエラーにならないように、空リストの処理を入れておくと安全です。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    D = list(map(int, data[2:2+N]))
    
    intervals = []
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        intervals.append((L, R))
        idx += 2
    
    # 区間をソート
    intervals.sort()
    
    # 区間のマージ
    if not intervals:
        merged = []
    else:
        merged = [list(intervals[0])]
        for L, R in intervals[1:]:
            last = merged[-1]
            if L <= last[1] + 1 - 1:  # L <= last[1] で重なりあり
                if R > last[1]:
                    merged[-1][1] = R
            else:
                merged.append([L, R])
    
    # 各D_iに対して、少なくとも一つの区間に含まれるかどうかを判定
    total = 0
    for d in D:
        # 二分探索で d が含まれるか判定
        # merged は [L,R] のリストでソートされている
        pos = bisect_right(merged, [d, float('inf')])  # L > d となる最初の位置
        # pos-1 が候補
        if pos > 0:
            L_prev, R_prev = merged[pos-1]
            if L_prev <= d <= R_prev:
                total += 2 * d
                continue
        # 次に pos
        if pos < len(merged):
            L_next, R_next = merged[pos]
            if L_next <= d <= R_next:
                total += 2 * d
                continue
        total += d
        
    print(total)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。