概要

雨で作業できない日（区間）が複数与えられるとき、種を植えられる日だけを数え上げて、\(N\) 個植え終わる最終日を求める問題です。

考察

重要な気づき

• 高橋君は「雨でない日」にしか種を植えられず、植えるのは 1日につき最大1個 です。
• したがって、「植えられる日数」を日付順に数えていき、合計が \(N\) に達した日が答えになります。
• ただし日数や雨区間の端点は最大 \(10^{18}\) なので、1日ずつシミュレーションすると到底間に合いません（TLE）。

素朴解がダメな理由

• 例えば雨が第 \(10^{18}\) 日付近まで続くような入力でも、愚直に day = 1 から増やすと \(10^{18}\) 回ループになり不可能です。

解決方針

• 雨の日は「区間」として与えられるので、雨区間をまとめて処理します。
• 特に雨区間が重なっていたり隣接していたりする場合、まとめて1つの区間に マージ しておくと処理が簡単になります。
  • 例：\([2,5]\) と \([4,7]\) は重なるので \([2,7]\)
  • 例：\([2,5]\) と \([6,8]\) は隣接（\(5+1=6\)）しており、間に植えられる日がないので \([2,8]\) としてまとめてよい

その後は「雨区間の手前の晴れの連続日数（ギャップ）」だけをまとめて数えればよく、日付を飛ばしながら進められます。

アルゴリズム

1. 雨区間 \([L_i, R_i]\) をすべて読み取り、\(L_i\) 昇順にソートする。
2. ソートした区間を順に見て、重なり・隣接（\(l \leq cur\_r + 1\)）するものをマージし、互いに交わらない区間列 merged を作る。
3. day = 1（現在日）、planted = 0（植えた個数）で開始し、merged を左から順に処理する。
   • いま見ている雨区間が \([l, r]\) のとき：
     • もし day < l なら、day から \(l-1\) までは晴れなので、その長さ gap = l - day だけ植えられる。
     • planted + gap >= N なら、この晴れ区間の途中で植え終わる。
       • 残り必要個数は \(N - planted\) 個なので、答えは \(day + (N - planted) - 1\)
     • そうでなければ planted += gap、day = l に更新
     • 次に雨区間内に入るので、day を雨明けの翌日 r + 1 に飛ばす（day <= r のとき）。
4. すべての雨区間を処理し終えたら、残り remaining = N - planted 個は連続した晴れで植えられるため、答えは \(day + remaining - 1\)

具体例

• \(N=5\)、雨区間が \([2,3]\), \([5,5]\) の場合：
  • 晴れ：1日目（1個）
  • 2〜3日目は雨（飛ばす）
  • 4日目は晴れ（2個目）
  • 5日目は雨（飛ばす）
  • 6,7,8日目…で残り3個を植える → 8日目に完了
    このように「晴れの連続部分」だけ数えればよいことが分かります。

計算量

• 時間計算量: \(O(M \log M)\)（ソートが支配的、マージと走査は \(O(M)\)）
• 空間計算量: \(O(M)\)（区間配列・マージ結果を保持）

実装のポイント

• 雨区間は 両端含む ので、雨明けは r+1 日目から作業可能です。
• 区間のマージ条件は「重なり」だけでなく「隣接」も含めて l <= cur_r + 1 とするのが重要です（間に晴れが存在しないため）。
• 端点は最大 \(10^{18}\) なので、Python なら整数オーバーフローはありませんが、計算は常にこの範囲を想定して実装します。
• M=0 のときは雨がないので、単純に \(N\) 日目が答えになります。

ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    if M == 0:
        print(N)
        return

    intervals = [(next(it), next(it)) for _ in range(M)]
    intervals.sort()

    merged = []
    cur_l, cur_r = intervals[0]
    for l, r in intervals[1:]:
        if l <= cur_r + 1:
            if r > cur_r:
                cur_r = r
        else:
            merged.append((cur_l, cur_r))
            cur_l, cur_r = l, r
    merged.append((cur_l, cur_r))

    day = 1
    planted = 0

    for l, r in merged:
        if day < l:
            gap = l - day
            if planted + gap >= N:
                ans = day + (N - planted) - 1
                print(ans)
                return
            planted += gap
            day = l
        if day <= r:
            day = r + 1

    remaining = N - planted
    ans = day + remaining - 1
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。