概要

\(H \times W\) のグリッド上で \(N\) 個の流れ星が左上に向かって移動する。それぞれの流れ星は一定時間後に消える。すべての流れ星を撮影するために必要なカメラの最小台数を求めよ。

考察

各流れ星は初期位置 \((R_k, C_k)\) から、時刻 \(t\) ごとに \((R_k - t, C_k - t)\) へと移動し、最終的にはグリッド外に出て消える。この動きは、主対角線（\(x - y =\) 一定）に沿った移動であることに気づくことが重要である。

つまり、流れ星 \(k\) は対角線 \(d = R_k - C_k\) 上の区間 \([R_k - (\min(R_k, C_k) - 1),\ R_k]\) を通過するだけである。そのため、同じ対角線上に存在する流れ星同士はまとめて考えることができ、カメラは対角線ごとに独立に配置すればよい。

さらに、同じ対角線上の流れ星の区間をすべてカバーするためには、区間スケジューリング的な考え方が使える。つまり、区間の始点でソートし、必要に応じて最も右にカメラを設置することで、多くの区間をカバーすることができる。

素朴にグリッド全体を見渡したり、全組み合わせを試すと、\(H, W\) が最大 \(10^9\) なので当然TLEする。また、流れ星の本数も最大 \(2 \times 10^5\) あり、効率的に処理する必要がある。

アルゴリズム

1. 各流れ星の初期位置 \((R_k, C_k)\) から、対角線ID \(d = R_k - C_k\) を求め、その流れ星が通過する区間 \([low,\ high]\) を計算する：

   • \(low = R_k - (\min(R_k, C_k) - 1)\)
   • \(high = R_k\)

2. 対角線ごとに区間をグループ分けする。

3. 各対角線ごとに、区間を始点順にソートし、貪欲法で最小のカメラ設置数（＝区間をカバーする最小の点の数）を求める：

   • 前回カメラを置いた位置よりも新しい区間が始まったら、その区間の終端にカメラを設置。
   • これにより、できるだけ多くの後続区間をカバーできる。

4. 全対角線でのカメラ数の合計が答え。

具体例

例えば、以下のような流れ星があったとする：

流れ星	初期位置 \((R, C)\)	対角線 \(d = R - C\)	区間 \([low, high]\)
1	(3, 2)	1	[2, 3]
2	(4, 3)	1	[2, 4]
3	(2, 4)	-2	[1, 2]

• 対角線 \(d = 1\)：区間 [2,3], [2,4] → 1台でカバー可能（位置3にカメラ）
• 対角線 \(d = -2\)：区間 [1,2] → 1台でカバー可能

→ 合計2台

計算量

• 時間計算量: \(O(N \log N)\)
  （各区間を対角線ごとにソートする操作が支配的）
• 空間計算量: \(O(N)\)
  （流れ星の情報および対角線ごとの区間リストを保持）

実装のポイント

• 各流れ星の区間を正しく計算すること（特に端の処理）

• 対角線ごとに区間を分類し、ソートして貪欲に処理する部分が肝心

• last_selected を「最後にカメラを置いた地点」として管理し、次区間がカバーされているか判定する

• Pythonでは sys.stdin.read() を使うことで高速入力処理ができる

  ソースコード

import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    H = int(data[0])
    W = int(data[1])
    N = int(data[2])
    
    meteors = []
    for i in range(N):
        r = int(data[3 + 2*i])
        c = int(data[4 + 2*i])
        # 各流れ星の初期位置 (r, c)
        # この流れ星のパスは (r-t, c-t) for t=0 to min(r,c)-1
        # これは対角線に沿ったパスで、全ての点は同じ (r-c) の値を持つ
        diag = r - c  # diagonal identifier
        start_t = 0
        end_t = min(r, c) - 1
        # 実際の座標範囲: (r - t, c - t) で t = 0 to end_t
        # つまり、行は r から r - end_t まで、列は c から c - end_t まで
        # 座標範囲は [r - end_t, r] x [c - end_t, c]
        # しかし、これは同じ対角線上の連続した区間
        
        # より正確には、(x, y) が対角線 d 上にあるとは x - y = d
        # 各流れ星のパスは対角線 (r - c) 上の区間 [(r - end_t, c - end_t), (r, c)]
        # すなわち (r - end_t) から r までの行について (row, row - d) を通る
        
        # したがって、各流れ星は対角線 d = r - c 上のある区間に対応する
        # この区間は [r - end_t, r] = [r - (min(r,c) - 1), r]
        low = r - (min(r, c) - 1)
        high = r
        meteors.append((diag, low, high))
        
    # 対角線ごとにグループ分け
    from collections import defaultdict
    diag_to_intervals = defaultdict(list)
    for d, low, high in meteors:
        diag_to_intervals[d].append((low, high))
        
    count = 0
    # 各対角線について、区間スケジューリング問題を解く
    # 最小区間被覆ではなく、区間を選んで全区間をカバーする最小選択 -> これは区間スケジューリング
    # すべての区間をカバーする最小の点の数 = 最小ヒットセット = 区間グラフの最大独立集合の補集合？
    # 実際には、各区間をカバーする点（カメラの設置位置）の最小数を求める問題
    # これは区間グラフにおける最小クリーク被覆 = 最大独立集合（一般にはNP-hardだが区間グラフでは多項式）
    # 正確には、最小の点の集合Sで、各区間Iに対して s in S かつ s in I なるものが存在するようなSの最小サイズ
    # => 区間の始点でソートして貪欲法
    
    for intervals in diag_to_intervals.values():
        # intervals: list of (low, high)
        intervals.sort()  # low順にソート
        if not intervals:
            continue
        res = 0
        last_selected = -float('inf')
        for low, high in intervals:
            if last_selected < low:
                # 新しいカメラが必要
                res += 1
                last_selected = high  # 最も右にカメラを設置することで、今後来る区間もカバーしやすい
            else:
                # すでにカバーされているが、より右にカメラを設置することで今後をカバーできるようにする？
                # 貪欲に最後尾に配置するのが最適
                last_selected = min(last_selected, high)
        count += res
        
    print(count)

if __name__ == "__main__":
    main()

---

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