概要

会議室の初期利用可能時間帯に対して、順次適用される利用制限の共通部分を求め、各制限適用後の利用可能時刻数を求める問題です。

考察

問題の本質は、初期区間 \([L, R]\) に対して、順次適用される区間 \([l_i, r_i]\) との共通部分を効率的に計算することです。各制限適用後の利用可能区間は、直前の区間と新規制限区間の共通部分として計算できます。

素朴なアプローチとして、毎回すべての制限区間との共通部分を計算すると、\(i\)番目の制限までに\(O(i)\)の時間がかかり、全体で\(O(N^2)\)の時間計算量となります。\(N\)が最大\(10^5\)であるため、これは実行時間制限に間に合いません。

しかし、共通部分の計算は結合則を満たすため、直前の状態だけを保持すれば十分です。つまり、各ステップで直前の区間と新規制限区間の共通部分だけを計算すれば、全体を\(O(N)\)で処理できます。

アルゴリズム

1. 初期区間 \([current\_l, current\_r] = [L, R]\) を設定
2. 各制限 \([l_i, r_i]\) に対して以下を実行：
   • 新しい左端：\(new\_l = \max(current\_l, l_i)\)
   • 新しい右端：\(new\_r = \min(current\_r, r_i)\)
   • \(new\_l > new\_r\) なら共通部分は空集合（区間 \([1, 0]\) として表現）
   • そうでなければ区間 \([new\_l, new\_r]\) を新しい現在区間とする
3. 各ステップで現在区間の要素数 \(max(0, new\_r - new\_l + 1)\) を出力

この手法では、各制限処理が定数時間で実行され、全体として\(O(N)\)の効率性を達成できます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)（入力データの保存に必要な分）

実装のポイント

• 区間が空になった場合（\(new\_l > new\_r\)）は、以降すべての共通部分も空になるため、区間を \([1, 0]\) に設定して以降の計算を省略可能

• 入力値が大きい（最大\(10^9\)）ため、整数演算で正確に処理

• 空区間の要素数が0になるように、\(max(0, count)\) で調整

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    L = int(data[0])
    R = int(data[1])
    N = int(data[2])
    intervals = []
    index = 3
    for i in range(N):
        l = int(data[index])
        r = int(data[index+1])
        index += 2
        intervals.append((l, r))
    
    current_l = L
    current_r = R
    
    for i in range(N):
        l_i, r_i = intervals[i]
        new_l = max(current_l, l_i)
        new_r = min(current_r, r_i)
        if new_l > new_r:
            current_l = 1
            current_r = 0
        else:
            current_l = new_l
            current_r = new_r
        
        count = current_r - current_l + 1
        if count < 0:
            count = 0
        print(count)

if __name__ == "__main__":
    main()

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