概要

二つの道路の街灯の明るさの差を時刻ごとに比較し、時刻 \(1\) から \(T\) の中で高橋君の道路のほうが明るい時刻の数を数える問題です。イベントベースのいもす法（差分配列）と座標圧縮を組み合わせて効率的に解きます。

考察

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

各時刻 \(t = 1, 2, \ldots, T\) について明るさを愚直に計算すると \(O(T \times (N + M))\) となります。\(T\) が最大 \(10^9\) なので、全時刻を1つずつ調べることは到底間に合いません。

重要な気づき

時刻 \(A_i\) に点灯された街灯は、時刻 \(A_i, A_i+1, \ldots, A_i+D-1\) の間だけ明るさに \(+1\) を寄与します。

差分 \(\text{diff}(t) = \text{brightness\_A}(t) - \text{brightness\_B}(t)\) を考えると： - 各 \(A_i\) は区間 \([A_i,\ A_i + D - 1]\) で diff に \(+1\) - 各 \(B_j\) は区間 \([B_j,\ B_j + D - 1]\) で diff に \(-1\)

この diff の値が変化するのは、各区間の開始点と終了点の次の時刻だけです。つまり、変化点（イベント）は高々 \(2(N+M)\) 個しかありません。連続するイベント間では diff は一定値 なので、その区間の長さをまとめて計算できます。

アルゴリズム

1. イベントの生成：いもす法の考え方を使います。

   • 各 \(A_i\) について、時刻 \(A_i\) に \(+1\)、時刻 \(A_i + D\) に \(-1\)（diff が増加→元に戻る）
   • 各 \(B_j\) について、時刻 \(B_j\) に \(-1\)、時刻 \(B_j + D\) に \(+1\)（diff が減少→元に戻る）
   • ただし、時刻 \(T\) を超えるイベントは不要

2. イベントの時刻順ソート

3. スイープライン処理：時刻 \(1\) から \(T\) まで走査

   • 現在の diff 値 current_diff を管理
   • 連続する2つのイベント時刻の間の区間 \([\text{prev\_t},\ \text{et} - 1]\) では diff は一定
   • current_diff > 0 なら、その区間の長さ分だけ答えに加算
   • イベント時刻でイベント値を current_diff に加算して更新

4. 最後のイベント以降 \([\text{prev\_t},\ T]\) も同様に処理

具体例

\(N=1, M=1, D=3, T=10, A=[2], B=[4]\) のとき： - \(A_1=2\): 時刻2で \(+1\)、時刻5で \(-1\) - \(B_1=4\): 時刻4で \(-1\)、時刻7で \(+1\)

区間	diff	高橋のほうが明るい？
\([1, 1]\)	0	No
\([2, 3]\)	1	Yes（2時刻）
\([4, 4]\)	0	No
\([5, 6]\)	-1	No
\([7, 10]\)	0	No

答え：2

計算量

• 時間計算量: \(O((N + M) \log(N + M))\)（イベントのソートが支配的）
• 空間計算量: \(O(N + M)\)（イベントの格納）

実装のポイント

• イベント時刻が \(T\) を超える場合は登録しない（区間 \([1, T]\) のみ考慮するため）

• 区間 \([\text{prev\_t},\ \text{et} - 1]\) の長さは \(\text{et} - \text{prev\_t}\) であることに注意（整数時刻の個数）

• 同じ時刻に複数のイベントがある場合は加算してまとめる（辞書で管理）

• 最初のイベントが時刻1より後の場合、\([1, \text{最初のイベント時刻}-1]\) の区間では diff = 0 なので自動的にカウントされない

  ソースコード

import sys
from itertools import accumulate

def solve():
    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]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    # For each street light activated at time t, it is on during [t, t+D-1].
    # We need brightness_A(t) > brightness_B(t) for integer t in [1, T].
    
    # brightness_A(t) = number of A_i such that A_i <= t <= A_i + D - 1
    #                  = number of A_i such that t - D + 1 <= A_i <= t
    
    # diff(t) = brightness_A(t) - brightness_B(t)
    # We need to count integer t in [1, T] where diff(t) > 0.
    
    # Each A_i contributes +1 to diff for t in [A_i, min(A_i + D - 1, T)]
    # Each B_j contributes -1 to diff for t in [B_j, min(B_j + D - 1, T)]
    
    # We use coordinate compression with events.
    # Event: at time t, diff changes. We track intervals where diff is constant.
    
    # For A_i: +1 at t=A_i, -1 at t=A_i+D (if A_i+D <= T, otherwise no end event within [1,T])
    # For B_j: -1 at t=B_j, +1 at t=B_j+D
    
    events = {}
    
    def add_event(t, val):
        if t in events:
            events[t] += val
        else:
            events[t] = val
    
    for a in A:
        start = a
        end = a + D  # diff decreases by 1 at this time
        if start <= T:
            add_event(start, 1)
            if end <= T:
                add_event(end, -1)
    
    for b in B:
        start = b
        end = b + D
        if start <= T:
            add_event(start, -1)
            if end <= T:
                add_event(end, 1)
    
    if not events:
        print(0)
        return
    
    # Sort events by time
    sorted_times = sorted(events.keys())
    
    # We need to process intervals [1, T] of integer times.
    # Between consecutive event times, diff is constant.
    # Event times are where diff changes (prefix sum of events).
    
    # We process segments: [prev_time, next_event_time - 1] with current diff value,
    # then at next_event_time, diff changes.
    
    ans = 0
    current_diff = 0
    prev_t = 1  # start of current segment
    
    for et in sorted_times:
        if et > T:
            break
        # Segment [prev_t, et - 1] has current_diff
        if et > prev_t:
            seg_len = et - prev_t  # number of integer times in [prev_t, et-1]
            if current_diff > 0:
                ans += seg_len
        # Apply event at et
        current_diff += events[et]
        prev_t = et
    
    # Remaining segment [prev_t, T]
    if prev_t <= T:
        seg_len = T - prev_t + 1
        if current_diff > 0:
            ans += seg_len
    
    print(ans)

solve()

---

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