概要

この問題は、グリッド上を斜め（左上方向）に移動する流れ星の軌跡の性質を利用し、すべての流れ星を撮影するために必要なカメラの最小台数を求める問題です。一見すると複雑なグリッド上の探索問題に見えますが、数式で整理することで「値の種類数を数える」という非常にシンプルな問題に帰着できます。

考察

流れ星の軌跡の性質

\(k\) 番目の流れ星は初期位置 \((R_k, C_k)\) から出発し、時刻 \(t\)（\(t \geq 0\)）に区画 \((R_k - t, C_k - t)\) に移動します。 このとき、流れ星が位置する区画の「列番号から行番号を引いた値」に注目してみましょう。

\[(C_k - t) - (R_k - t) = C_k - R_k\]

となり、時刻 \(t\) に依存せず常に一定の値 \(C_k - R_k\) を取ることが分かります。 これは、各流れ星が「左上から右下へ向かう特定の対角線上」を、左上方向に向かって移動していることを意味します。

異なる対角線との関係

列番号と行番号の差 \(C_k - R_k\) が異なる流れ星同士は、異なる対角線上を移動します。 これらの対角線は平行であり、グリッド上で交わることはありません。したがって、1台のカメラで異なる対角線上を移動する流れ星を同時に撮影することは不可能です。 よって、必要なカメラの台数は、流れ星が存在する対角線の数（\(C_k - R_k\) のユニークな値の数）以上になることが分かります。

同じ対角線上でのカバー

では、同じ対角線上にある流れ星同士は、常に1台のカメラで同時に撮影できるでしょうか？

例えば、同じ対角線上にある2つの流れ星 \(A, B\) の初期位置がそれぞれ \((R_A, C_A), (R_B, C_B)\) であり、\(R_A < R_B\)（\(A\) の方が左上、\(B\) の方が右下）であるとします。 このとき、流れ星 \(B\) は左上に向かって移動するため、時刻 \(t = R_B - R_A\) において、ちょうど \(A\) の初期位置である \((R_A, C_A)\) を通過します。 したがって、区画 \((R_A, C_A)\) にカメラを1台設置しておけば、流れ星 \(A\)（時刻 \(0\)）と流れ星 \(B\)（時刻 \(R_B - R_A\)）の両方を撮影することができます。

これを一般化すると、同じ対角線上にある流れ星たちのうち、最も「右下」にある（すなわち \(R_k\) が最大である）流れ星の初期位置にカメラを1台設置すれば、その対角線上のすべての流れ星を撮影することができます。

結論

以上の考察から、各対角線につきちょうど1台のカメラを設置すれば、その対角線上のすべての流れ星をカバーできます。 したがって、必要なカメラの最小台数は、すべての流れ星における \(C_k - R_k\) の値の種類数（ユニークな値の個数）と完全に一致します。

アルゴリズム

1. 各流れ星 \(k = 1, 2, \ldots, N\) について、値 \(D_k = C_k - R_k\) を計算し、配列に格納します。
2. 格納した配列を昇順にソートします。
3. ソートした配列から重複する要素を削除（ユニーク化）します。
4. ユニーク化された配列の要素数（サイズ）を出力します。

計算量

• 時間計算量: \(O(N \log N)\) \(N\) 個の要素のソートが全体のボトルネックとなります。\(N \le 2 \times 10^5\) であるため、実行時間制限に対して十分に高速です。
• 空間計算量: \(O(N)\) 各流れ星の \(C_k - R_k\) の値を保持する配列のために \(O(N)\) のメモリを使用します。

実装のポイント

• グリッドのサイズ \(H, W\) は最大で \(10^9\) と非常に大きいですが、流れ星の個数 \(N\) は \(2 \times 10^5\) と小さいため、グリッド全体をメモリ上に保持するのではなく、流れ星の座標情報のみを処理します。

• \(C_k - R_k\) の値は負になることがありますが、符号付き整数型（C++の long long 型など）を使用すれば問題なく処理できます。

• C++において重複排除を行う際は、std::sort を行った後に std::unique と erase を組み合わせる手法が定石であり、簡潔かつ高速に実装できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long H, W;
    int N;
    if (!(cin >> H >> W >> N)) return 0;
    
    vector<long long> diffs(N);
    for (int i = 0; i < N; ++i) {
        long long r, c;
        cin >> r >> c;
        diffs[i] = c - r;
    }
    
    sort(diffs.begin(), diffs.end());
    diffs.erase(unique(diffs.begin(), diffs.end()), diffs.end());
    
    cout << diffs.size() << "\n";
    
    return 0;
}

---

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