概要

各投擲の距離がボーナスエリア（リング状の領域）に含まれるかを判定し、含まれれば得点を2倍にして合計得点を求める問題です。

考察

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

各投擲 \(D_i\) について、\(M\) 個すべてのボーナスエリアを順に調べて「\(L_j \leq D_i \leq R_j\) を満たす \(j\) があるか？」を判定する方法が最もシンプルです。しかし、この方法では各投擲ごとに最大 \(M\) 回の判定が必要なため、全体で \(O(N \times M)\) の計算量となります。\(N, M\) が最大 \(2 \times 10^5\) のとき、最悪 \(4 \times 10^{10}\) 回の処理が必要となり、TLE（制限時間超過）になります。

重要な気づき

1. ボーナスエリアの統合（マージ）: ボーナスエリア同士が重なっていることがありますが、ある距離がボーナスエリアに含まれるかどうかだけが重要なので、重なりや隣接する区間をまとめて1つにできます。例えば、\([2, 5]\) と \([4, 8]\) は \([2, 8]\) にマージできます。

2. 二分探索で高速判定: マージ後の区間は互いに重ならず、左端でソートされています。このため、ある距離 \(d\) がいずれかの区間に含まれるかを 二分探索 で \(O(\log M)\) で判定できます。

アルゴリズム

ステップ 1: 区間のマージ

1. \(M\) 個のボーナスエリア \([L_j, R_j]\) を左端 \(L_j\) の昇順にソートする。
2. ソート順に区間を見ていき、前の区間と重なるか隣接していれば統合する。具体的には、現在の区間の \(L\) が直前のマージ済み区間の \(R + 1\) 以下なら、直前の区間の \(R\) を \(\max(R_{\text{前}}, R_{\text{現}})\) に更新する。

例: \([1, 5], [3, 7], [10, 15]\) → マージ後 \([1, 7], [10, 15]\)

ステップ 2: 各投擲の判定

各 \(D_i\) に対して：

1. マージ済み区間の左端の配列 starts に対し、bisect_right(starts, d) - 1 で「左端が \(d\) 以下である最後の区間」のインデックス pos を求める。
2. pos >= 0 かつ d <= ends[pos] なら、\(D_i\) はボーナスエリアに含まれるので得点は \(2 \times D_i\)。
3. そうでなければ得点は \(D_i\)。

なぜこれで正しいか: マージ済み区間は互いに重ならずソートされているため、\(d\) を含みうる区間は「左端が \(d\) 以下の区間のうち最も右にあるもの」だけです。その区間の右端が \(d\) 以上であれば \(d\) は含まれます。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • 区間のソートに \(O(M \log M)\)
  • 各投擲の二分探索に \(O(\log M)\)、\(N\) 回で \(O(N \log M)\)
• 空間計算量: \(O(N + M)\)
  • 投擲データとマージ済み区間の保持

実装のポイント

• 区間マージの条件: 整数値なので、\(L \leq R_{\text{前}} + 1\) で隣接も統合しています（例: \([1,3]\) と \([4,6]\) は \([1,6]\) に）。ただし本問題では「以上・以下」の判定なので、隣接統合をしなくても正解にはなります。

• bisect_right の使い方: bisect_right(starts, d) - 1 により、左端が \(d\) 以下 の区間のうち最も右のインデックスが得られます。結果が \(-1\)（該当区間なし）の場合はボーナスエリア外と判定します。

• 出力が大きくなる可能性: \(D_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、合計は最大約 \(4 \times 10^{14}\) になります。Python は多倍長整数なので問題ありませんが、他の言語では64ビット整数型を使う必要があります。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    D = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    # Read bonus areas and merge them
    intervals = []
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        intervals.append((L, R))
    
    # Merge overlapping intervals
    intervals.sort()
    merged = []
    for L, R in intervals:
        if merged and L <= merged[-1][1] + 1:
            merged[-1] = (merged[-1][0], max(merged[-1][1], R))
        else:
            merged.append((L, R))
    
    # For each D_i, check if it falls in any merged interval using binary search
    # merged is sorted by start. For a query d, find the rightmost interval whose start <= d,
    # then check if d <= that interval's end.
    starts = [m[0] for m in merged]
    ends = [m[1] for m in merged]
    
    total = 0
    for d in D:
        # Find the index of the last interval with start <= d
        pos = bisect_right(starts, d) - 1
        if pos >= 0 and d <= ends[pos]:
            total += 2 * d
        else:
            total += d
    
    print(total)

main()

---

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