概要

雨の降っていない日（晴れの日）に毎日1つずつ、合計 \(N\) 個の種を植えるとき、最後の種を植え終えるのが第何日目になるかを求める問題です。

考察

1. シミュレーションの限界

植える種の数 \(N\) は最大 \(10^9\)、雨の期間の終点 \(R_i\) は最大 \(10^{18}\) と非常に大きな値です。そのため、「1日ずつ進めて晴れなら種を植える」というシミュレーションを行うと、実行時間制限（TLE）に間に合いません。

2. 雨の期間の整理

雨の期間は \(M\) 回（最大 \(10^5\)）与えられますが、これらは互いに重なっている場合があります。 例えば、第 3 日〜第 5 日と第 4 日〜第 7 日が雨の場合、これらをまとめて「第 3 日〜第 7 日」という1つの区間として扱うことができます。

3. 晴れの日のブロックで考える

整理された雨の期間と雨の期間の間は、すべて「晴れの日」が続くブロックです。

1. 現在の日付を \(1\) 日目とします。
2. 次の雨が始まるまでの晴れの日数を計算します。
3. その日数で \(N\) 個の種を植えきれるなら、そのブロックの中で答えが決まります。
4. 植えきれないなら、\(N\) からその日数を引き、日付を雨の期間が終わった翌日まで進めます。

このように、日付を1日ずつではなく「期間（ブロック）」単位でジャンプさせることで、高速に解くことができます。

アルゴリズム

1. 雨の期間の結合（マージ）:
   • 与えられた \(M\) 個の雨の期間 \([L_i, R_i]\) を、開始日 \(L_i\) が早い順にソートします。
   • 前の区間の終点と次の区間の始点が重なっている（あるいは連続している）場合、それらを結合して1つの区間にまとめます。
2. 晴れ期間の走査:
   • current_day（次に種を植える候補日）を \(1\) に設定します。
   • マージされた雨の期間を順番に見ていきます。
   • 晴れの日数 sunny_len = (雨の開始日 \(L\)) - current_day を計算します。
   • もし \(N \le \text{sunny\_len}\) なら、答えは current_day + N - 1 です。
   • そうでなければ、\(N\) を sunny_len だけ減らし、current_day を (雨の終了日 \(R\)) + \(1\) に更新します。
3. 残りの処理:
   • すべての雨の期間を通り過ぎても種が残っている場合、最後にまとめて植えます。答えは current_day + N - 1 です。

計算量

• 時間計算量: \(O(M \log M)\)
  • 雨の期間のソートに \(O(M \log M)\) かかります。
  • 区間のマージと走査は \(O(M)\) で行えます。
• 空間計算量: \(O(M)\)
  • 入力された区間およびマージ後の区間を保持するために \(O(M)\) のメモリを使用します。

実装のポイント

• 区間のマージ: intervals.sort() をした後、現在の終点 curr_r と次の始点 next_l を比較して next_l <= curr_r であれば結合するという処理は、区間を扱う問題での典型的な手法です。
• 大きな数値の扱い: \(10^{18}\) などの大きな値を扱うため、Pythonのような多倍長整数をサポートする言語や、C++であれば long long 型を使用する必要があります。
• 雨が降らない場合: \(M=0\) の場合や、雨の期間が始まる前に種を植え終える場合などのコーナーケースにも対応できるように実装します。

ソースコード

import sys

# 問題文の要件に従い、N個の種を植え終える最後の日を求めます。
# 毎日1個ずつ種を植えますが、雨の期間[L_i, R_i]には作業ができません。
# 作業ができる日（晴れの日）を1日目から数えて、N番目の晴れの日を特定します。

def solve():
    # 全ての入力を一度に読み込み、効率的に処理するためにイテレータを使用します。
    # Nは非常に大きい(最大10^9)ため、シミュレーションではなく計算で求めます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # 雨の期間がない場合、N番目の種は第N日に植えられます。
    if M == 0:
        print(N)
        return
        
    # 雨の期間を取得します。
    intervals = []
    for _ in range(M):
        try:
            l = int(next(it))
            r = int(next(it))
            intervals.append((l, r))
        except StopIteration:
            break
            
    # 雨の期間を結合するために、開始日でソートします。
    intervals.sort()
    
    # 重なり合っている、あるいは連続している雨の期間を1つの区間に結合します。
    merged = []
    it_intervals = iter(intervals)
    try:
        curr_l, curr_r = next(it_intervals)
    except StopIteration:
        print(N)
        return

    for next_l, next_r in it_intervals:
        # 現在の区間の終わりと次の区間の始まりが重なっていれば結合します。
        if next_l <= curr_r:
            if next_r > curr_r:
                curr_r = next_r
        else:
            # 重なりがなければ、現在の区間を確定させて次の区間に移ります。
            merged.append((curr_l, curr_r))
            curr_l, curr_r = next_l, next_r
    # 最後の区間を追加します。
    merged.append((curr_l, curr_r))
    
    # current_day は次に種を植える候補となる日（最初は1日目）です。
    current_day = 1
    for l, r in merged:
        # 現在の日から次の雨が始まる前日までの「晴れの日」の数を計算します。
        # 晴れの期間は [current_day, l - 1] です。
        sunny_len = l - current_day
        if sunny_len > 0:
            if N <= sunny_len:
                # 残りの種 N 個をすべてこの晴れの期間中に植えられる場合、
                # その日は current_day から数えて N 日目になります。
                print(current_day + N - 1)
                return
            else:
                # この期間だけでは足りない場合、植えられるだけ植えて N を更新します。
                N -= sunny_len
        
        # 次に種を植えられる可能性があるのは、この雨の期間が終わった翌日です。
        current_day = r + 1
    
    # すべての雨の期間が終わった後、残りの種を順番に植えていきます。
    # N個目の種は current_day から N-1 日経過した日に植えられます。
    print(current_day + N - 1)

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。