概要

\(N\) 個の花の種を順に植えていくが、雨の期間中は作業ができない。すべての種を植え終えるのは何日目かを求める問題。

考察

この問題では、\(N\) 個の種を毎日 1 個ずつ植えていくが、雨の期間中は作業ができません。したがって、第 \(d\) 日までに植えられる種の数は、「\(d\) 日までの総日数」から「雨の日数」を引いたものになります。

素朴な方法として、1 日ずつシミュレーションしていけば答えは求められますが、制約が \(N \leq 10^9\)、\(R_i \leq 10^{18}\) と非常に大きいため、現実的ではありません（TLE）。

そこで、以下の2つの工夫を行います：

1. 雨の期間をマージする：重なっている・隣接している区間をまとめて、効率的に扱う。
2. 二分探索で答えを求める：最終的な日付を二分探索で絞り込み、その日までに植えられる種の数を高速に計算する。

具体的には、ある日 \(d\) までに植えられる種の数は \(d - (\text{雨の日数})\) で求められます。雨の日数は、マージ済みの区間に対して累積的に計算可能です。

アルゴリズム

1. 雨の区間 \((L_i, R_i)\) を開始日 \(L_i\) の順にソートします。
2. 隣接・重複している区間をマージして、互いに離れた雨の期間を得ます。
3. 各区間ごとに「それまでの非雨日数」を計算してリストに保存しておきます。
4. 全体の非雨日数が \(N\) 以上であれば、二分探索で「\(N\) 個の種を植えられる最小の日」を求めます。
   • 各候補日について、その日までの「雨の日数」を区間に沿って計算し、植えられる種の数を評価します。
5. 非雨日数が足りなければ、最後の雨の日以降に必要な日数を加えて答えを求めます。

計算量

• 時間計算量: \(O(M \log M + M \log D)\)
  （\(D\) は探索範囲の最大値。大体 \(10^{18}\) 程度）
• 空間計算量: \(O(M)\)

※ 区間のソートに \(O(M \log M)\)、二分探索部で \(O(M)\) の計算を \(\log D\) 回繰り返す。

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用。
• 区間のマージはソート後に一度だけ行えば十分。
• 二分探索時には、mid 日までの雨の日数を正確にカウントする必要がある。
• 制約が大きいので、int や二分探索の範囲に注意。

ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    if M == 0:
        print(N)
        return
    
    intervals = []
    idx = 2
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        intervals.append((L, R))
        idx += 2
    
    # 区間を開始日でソート
    intervals.sort()
    
    # 区間のマージ
    merged = []
    for L, R in intervals:
        if not merged or merged[-1][1] < L - 1:
            merged.append((L, R))
        else:
            merged[-1] = (merged[-1][0], max(merged[-1][1], R))
    
    # 各区間までの非雨日数を計算
    total_rainy_days = 0
    prev_end = 0
    non_rainy_count = 0
    cumulative_non_rainy = []  # (day, non_rainy_count)
    
    for L, R in merged:
        # 前の区間の次の日から現在の区間の前日までの日数
        gap = L - 1 - prev_end
        if gap > 0:
            non_rainy_count += gap
        total_rainy_days += R - L + 1
        cumulative_non_rainy.append((R, non_rainy_count))
        prev_end = R
    
    # N個の種を植える必要がある
    if non_rainy_count >= N:
        # 二分探索でN個目に種を植える日を探す
        left = 1
        right = merged[-1][1]
        while left < right:
            mid = (left + right) // 2
            # mid日までに植えられる種の数を計算
            count = mid
            # mid日までの雨の日数を引く
            rainy = 0
            for L, R in merged:
                if R < mid:
                    rainy += R - L + 1
                elif L <= mid:
                    rainy += mid - L + 1
                else:
                    break
            count -= rainy
            if count >= N:
                right = mid
            else:
                left = mid + 1
        print(left)
    else:
        # 最後の区間の後ろにまだ日が必要
        remaining = N - non_rainy_count
        last_day = merged[-1][1]
        result = last_day + remaining
        print(result)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。