概要

雨の日を避けながら \(N\) 個の種を1日1個ずつ植えるとき、すべて植え終わる日を求める問題です。雨の期間が重複する可能性があるため、区間をマージしたうえで二分探索を用います。

考察

問題の言い換え

「第 \(D\) 日目までに植えられる種の数」は、\(D\) から「第 \(1\) 日〜第 \(D\) 日のうち雨の日の数」を引いたものです。つまり：

\[\text{sunny}(D) = D - \text{rainy}(D)\]

この \(\text{sunny}(D)\) がちょうど \(N\) 以上になる最小の \(D\) を求めればよいです。

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

\(D\) を1日目から順にシミュレーションする方法では、\(N\) が最大 \(10^9\)、雨の期間の端点が最大 \(10^{18}\) なので到底間に合いません。

重要な気づき

\(\text{sunny}(D)\) は \(D\) が増えると（減ることはなく）単調非減少です。このため、\(\text{sunny}(D) \geq N\) を満たす最小の \(D\) を二分探索で見つけることができます。

また、雨の期間は重なりうるので、事前に区間マージ（重複・隣接する区間を1つにまとめる処理）を行い、正確な雨日数を高速に計算できるようにします。

具体例

\(N = 5\), 雨の期間が \([2, 4]\) と \([3, 6]\) の場合：

• マージ後：\([2, 6]\)（5日間の雨）
• 第1日目：晴れ → 1個植える
• 第2〜6日目：雨 → 植えられない
• 第7〜10日目：晴れ → 4個植える
• 合計5個植え終わるのは第10日目

アルゴリズム

1. 区間マージ: 雨の期間を開始日でソートし、重複・隣接する区間を統合する。
2. 早期判定: マージ後の最後の雨の期間の終了日までに晴れの日が \(N\) 日以上あるかを確認する。
   • もし足りなければ、最後の雨の後は毎日晴れなので、不足分をそのまま加算して答えを出す。
3. 二分探索: 晴れの日が \(N\) 日以上ある場合、\([1, \text{last\_rain\_end}]\) の範囲で二分探索する。
   • 各候補日 \(D\) に対して、マージ済み区間を走査して \(\text{rainy}(D)\) を計算する。
   • \(D - \text{rainy}(D) \geq N\) なら答えは \(D\) 以下、そうでなければ \(D\) より大きい。

rainy_days_up_to(D) の計算

マージ済み区間 \([L_i, R_i]\) それぞれについて： - \(L_i > D\) ならスキップ（以降の区間も \(D\) より後） - そうでなければ \(\min(R_i, D) - L_i + 1\) を加算

計算量

• 時間計算量: \(O(M \log M + M \log V)\)
  • \(M \log M\)：区間のソート
  • \(M \log V\)：二分探索（\(\log V\) 回、\(V\) は探索範囲で最大約 \(10^{18}\)）の各ステップでマージ済み区間を走査（最大 \(M\) 個）
• 空間計算量: \(O(M)\)

実装のポイント

• 区間マージ時の条件: \(L \leq \text{prev\_R} + 1\) とすることで、隣接する区間（例：\([2,3]\) と \([4,5]\)）も正しく統合できる。
• 二分探索の上界: 最後の雨の終了後は毎日晴れなので、残り必要な種の数を加算するだけで答えが出る。二分探索が必要なのは答えが雨の期間内に収まる場合のみ。
• オーバーフロー対策: \(R_i\) が最大 \(10^{18}\) と非常に大きいが、Python は多倍長整数を扱えるため問題ない。

ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    intervals = []
    for i in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        intervals.append((L, R))
    
    if M == 0:
        print(N)
        return
    
    # Merge overlapping intervals
    intervals.sort()
    merged = []
    for L, R in intervals:
        if merged and L <= merged[-1][1] + 1:
            merged[-1] = (merged[-1][0], max(merged[-1][1], R))
        else:
            merged.append((L, R))
    
    # For each merged interval, we know rainy days in [L, R].
    # We need to find the day D such that the number of non-rainy days in [1, D] = N.
    
    # Number of rainy days in [1, D] can be computed using merged intervals.
    # non_rainy(D) = D - rainy_days(D)
    # We need non_rainy(D) = N, i.e., D - rainy_days(D) = N.
    
    # Binary search on D.
    def rainy_days_up_to(D):
        """Count total rainy days in [1, D] using merged intervals."""
        total = 0
        for L, R in merged:
            if L > D:
                break
            total += min(R, D) - L + 1
        return total
    
    # Lower bound: N (if no rain), Upper bound: N + total_rainy_days (but rain might extend beyond)
    # We need to be careful with upper bound.
    # The answer D satisfies D - rainy_days(D) = N.
    # D = N + rainy_days(D) >= N.
    # Also, total rainy days is at most sum of all interval lengths.
    # But intervals can go up to 10^18, so we need a smarter upper bound.
    
    # Actually, after the last merged interval ends, every day is sunny.
    # So the answer is at most max(merged[-1][1], 0) + N (very loose but safe... actually not if intervals are huge)
    # Better: after all rain periods, remaining seeds can be planted consecutively.
    # Let's compute how many sunny days exist up to the end of the last rain interval.
    
    last_rain_end = merged[-1][1]
    total_rain = sum(R - L + 1 for L, R in merged)
    sunny_before_end = last_rain_end - total_rain
    
    if sunny_before_end >= N:
        # Answer is within [1, last_rain_end], binary search
        lo, hi = 1, last_rain_end
    else:
        # Need more days after last rain period
        remaining = N - sunny_before_end
        print(last_rain_end + remaining)
        return
    
    while lo < hi:
        mid = (lo + hi) // 2
        sunny = mid - rainy_days_up_to(mid)
        if sunny >= N:
            hi = mid
        else:
            lo = mid + 1
    
    print(lo)

solve()

---

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