概要

この問題は、各ダーツの投擲距離が与えられたとき、その距離がいずれかのボーナスエリアに含まれているかどうかを判定し、条件に応じて得点を計算して合計する問題です。

考察

各投擲距離 \(D_i\) について、それがいずれかのボーナスエリア \([L_j, R_j]\) に含まれるかどうかを判定する必要があります。素朴なアプローチでは、各 \(D_i\) に対してすべてのボーナスエリア（\(M\) 個）をチェックすると、計算量が \(O(N \times M)\) となり、\(N\) と \(M\) が最大 \(2 \times 10^5\) ずつあるため、合計 \(4 \times 10^{10}\) 回のチェックが必要となり、時間内に処理できません。

そこで、ボーナスエリアを効率的に管理し、各 \(D_i\) がボーナスエリアに含まれるかどうかを高速に判定する方法が必要です。ボーナスエリアは区間の集合であり、これらの区間の和集合を求めることで、ボーナスエリアがカバーする連続区間を特定できます。ただし、ボーナスエリアは重なる可能性があるため、和集合を取ると複数の連続区間（セグメント）に分割されます。このセグメントを事前に計算しておけば、各 \(D_i\) がこれらのセグメントのいずれかに含まれるかどうかを二分探索で高速に判定できます。

アルゴリズム

1. ボーナスエリアの和集合の計算:

   • 各ボーナスエリア \([L_j, R_j]\) に対して、開始点 \(L_j\) で +1、終了点 \(R_j+1\) で -1 のイベントを作成します。
   • これらのイベントを座標の昇順にソートします。
   • ソートされたイベントを順に処理し、アクティブな区間の数（カウンタ）を管理します。カウンタが正の間はボーナスエリアが連続しているため、和集合のセグメントを記録します。

2. 各投擲距離の判定:

   • 前ステップで得られたセグメントのリストは、ソートされた連続区間の集合です。
   • 各 \(D_i\) について、セグメントのリストに対して二分探索を行い、\(D_i\) がどのセグメントにも含まれないかどうかを判定します。
   • 含まれる場合は得点を \(2 \times D_i\)、含まれない場合は \(D_i\) として合計に加算します。

計算量

• 時間計算量: \(O(M \log M + N \log M)\)
  • イベントのソートに \(O(M \log M)\)
  • セグメントの構築に \(O(M)\)
  • 各 \(D_i\) の二分探索に \(O(\log M)\) ずつ、合計 \(O(N \log M)\)
• 空間計算量: \(O(M)\)
  • イベントのリストとセグメントのリストのサイズが \(O(M)\)

実装のポイント

• イベントの処理では、区間の和集合を取るためにスイープラインアルゴリズムを使用します。カウンタが正から0になるときにセグメントが終了するため、終了点は \(R_j+1\) としてイベントを登録する必要があります。

• セグメントのリストは昇順にソートされているため、二分探索が適用できます。各セグメントは \((start, end)\) のタプルで表現され、\(D_i\) が \(start \leq D_i \leq end\) を満たすかどうかをチェックします。

• 入力データの読み込みには sys.stdin.read を使用し、大量のデータを効率的に処理します。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    D_list = list(map(int, data[idx:idx+N]))
    idx += N
    intervals = []
    for _ in range(M):
        L = int(data[idx]); R = int(data[idx+1]); idx += 2
        intervals.append((L, R))
    
    events = []
    for L, R in intervals:
        events.append((L, 1))
        events.append((R+1, -1))
    
    events.sort(key=lambda x: x[0])
    
    current = 0
    active_intervals = 0
    last_pos = 0
    segments = []
    for pos, delta in events:
        if active_intervals > 0:
            segments.append((last_pos, pos-1))
        active_intervals += delta
        last_pos = pos
    
    total_score = 0
    for d in D_list:
        low, high = 0, len(segments) - 1
        found = False
        while low <= high:
            mid = (low + high) // 2
            seg_start, seg_end = segments[mid]
            if seg_start <= d <= seg_end:
                found = True
                break
            elif d < seg_start:
                high = mid - 1
            else:
                low = mid + 1
        
        if found:
            total_score += 2 * d
        else:
            total_score += d
    
    print(total_score)

if __name__ == "__main__":
    main()

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