概要

ダーツの投擲結果と複数のボーナスエリア（区間）が与えられたとき、各投擲がボーナスエリアに含まれるかどうかを判定し、合計得点を計算する問題です。

考察

この問題の制約では、投擲回数 \(N\) とボーナスエリアの数 \(M\) がともに最大 \(2 \times 10^5\) となっています。 各投擲 \(D_i\) について、すべてのボーナスエリアを \(1\) つずつ確認する素朴な方法（二重ループ）では、計算回数が最大で \(N \times M = 4 \times 10^{10}\) 回に達してしまい、実行時間制限（TLE）に引っかかってしまいます。

これを高速化するためには、以下の2つの工夫が必要です。

1. 区間のマージ（結合） ボーナスエリアは互いに重なっている場合があります。例えば、\([1, 5]\) と \([3, 7]\) という2つのエリアがある場合、これらは実質的に1つの大きなエリア \([1, 7]\) として扱うことができます。あらかじめ重なっている区間をすべて結合しておくことで、「互いに重ならない独立した区間の集まり」を作ることができます。

2. 二分探索による高速な判定 区間が互いに重ならない状態になっていれば、各 \(D_i\) がどの区間に含まれる可能性があるかを二分探索を使って高速に見つけ出すことができます。これにより、判定にかかる時間を大幅に短縮できます。

アルゴリズム

1. 区間のソートとマージ

   • 与えられた \(M\) 個のボーナスエリア \([L_j, R_j]\) を、左端 \(L_j\) が小さい順にソートします。
   • ソートした区間を順番に見ていき、前の区間と重なっていれば結合し、重なっていなければ新しい区間としてリスト（merged）に追加していきます。
   • 具体例：\([1, 5], [3, 7], [8, 10]\) とソートされている場合、\([1, 5]\) と \([3, 7]\) は重なっているため \([1, 7]\) にマージされます。結果として merged は \([1, 7], [8, 10]\) となります。

2. 左端のリスト作成

   • 二分探索を行うために、マージされた区間の左端だけを取り出したリスト L_list を作成します。
   • 上の例なら、L_list = [1, 8] となります。

3. 各投擲の得点計算

   • 各投擲 \(D_i\) について、L_list に対して二分探索（bisect_right）を行います。これにより、\(D_i\) 以下で最大の左端を持つ区間をすぐに見つけることができます。
   • 見つけた区間を \([L, R]\) としたとき、\(D_i \leq R\) を満たしていれば、ダーツはボーナスエリアに含まれていると判定でき、得点に \(2 \times D_i\) を加算します。
   • 含まれていなければ、通常の得点 \(D_i\) を加算します。

計算量

• 時間計算量: \(O((N + M) \log M)\)
  • 区間のソートに \(O(M \log M)\) かかります。
  • 区間のマージは \(O(M)\) で完了します。
  • \(N\) 回の投擲それぞれに対して二分探索を行うため、\(O(N \log M)\) かかります。
  • 全体として高速に動作し、制約内でも余裕で間に合います。
• 空間計算量: \(O(N + M)\)
  • 投擲データやボーナスエリアの区間データを保持するために使用します。

実装のポイント

• bisect_right の使い方 Pythonの bisect_right(A, x) は、配列 A の中で x より大きい要素が最初に現れるインデックスを返します。そのため、x 以下の最大の要素を見つけるには、返ってきたインデックスから -1 を引く必要があります。また、その結果が 0 以上である（配列の範囲外になっていない）ことを確認する i >= 0 のチェックが重要です。

• オーバーフローへの配慮 ダーツの距離 \(D_i\) は最大 \(10^9\) であり、合計得点は非常に大きな値（最大 \(4 \times 10^{14}\) 程度）になります。Pythonでは整数型のサイズに上限がないため自動で処理されますが、C++ などの他言語で実装する場合は、合計得点を保持する変数に long long 型などを使用する必要があります。

• 高速な入出力 入力データが非常に多いため、sys.stdin.read().split() を用いて入力を一括で読み込むことで、プログラムの実行時間を短縮しています。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    D = [int(x) for x in input_data[2:2+N]]
    
    intervals = []
    idx = 2 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        intervals.append((L, R))
        idx += 2
        
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    for L, R in intervals:
        if not merged:
            merged.append([L, R])
        else:
            if L <= merged[-1][1]:
                if R > merged[-1][1]:
                    merged[-1][1] = R
            else:
                merged.append([L, R])
                
    L_list = [x[0] for x in merged]
    
    total_score = 0
    for d in D:
        i = bisect_right(L_list, d) - 1
        if i >= 0 and merged[i][0] <= d <= merged[i][1]:
            total_score += d * 2
        else:
            total_score += d
            
    print(total_score)

if __name__ == '__main__':
    solve()

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