2021-07-05

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。

問題へのリンク

問題概要

二次元平面上に、赤い点と青い点が $N$ 個ずつあります。 $i$ 個目の赤い点の座標は $(a_{i}, b_{i})$ であり、 $i$ 個目の青い点の座標は $(c_{i}, d_{i})$ です。

赤い点と青い点は、 $x$ 座標と $y$ 座標がともに赤い点よりも青い点の方が大きいとき、仲良しペアになれます。ただし，1 つの点が複数のペアに所属することはできません。

あなたは最大で何個の仲良しペアを作ることができますか？

制約

$1 \le N \le 100$
$0 \le a_{i}, b_{j} \lt 2N$
$a_{0}, \dots, a_{N-1}, c_{0}, \dots, c_{N-1}$ はそれぞれ互いに相異なる
$b_{0}, \dots, b_{N-1}, d_{0}, \dots, d_{N-1}$ はそれぞれ互いに相異なる

順序を定めて考える

このような問題を考察するときには、 $x$ 座標の小さい順に考えるなど、なんらかの順序を定めて考えることが重要だと思います。

さて、ここでは、青い点たちを $x$ 座標が小さい順に並べてあげて、それぞれの青い点に対して順番に、どの赤い点をペアにしていくかを考えることにしましょう¹。このときポイントとなるのは、 $x$ 座標を大きくしていくたびに、青い点とマッチングされうる赤い点の選択肢が徐々に広がっていくことです。

直感的な議論

さて、基本的には「赤い点のうち、 $y$ 座標が大きいものは売れ残りやすい」という構造になっていることに注意しましょう。 $y$ 座標が大きい赤い点は、それよりも $y$ 座標が大きい青い点しか手に負えないのです。

このことを踏まえた上で、 $x$ 座標が小さい順に青い点を見ていきましょう。結論から述べると、

まだ残っている赤い点のうち、
その青い点の左側 ( $x$ 座標が小さい側) にあって、
$y$ 座標が最大の点

を選ぶようにしておくとよいです。その理由を考えてみましょう。とりあえず、今考えている青い点を $B$ として、その $y$ 座標を $b$ としておきます。

さて、その青い点 $B$ の左側にあるまだ残っている赤い点たちの中に、 $y$ 座標が $b$ よりも小さいものが複数あったとします。これらの赤い点たちの集合を $S$ としましょう。 $S$ に含まれる赤い点たちのうち、将来的に最も売れ残るリスクが高いものは「 $y$ 座標が最大である赤い点」です。よって、最も売れ残るリスクの高い哀れな赤い点を拾ってあげるのが良いということになります²。

まとめると、次のように解けます。

青い点たちを $x$ 座標が小さい順にソートして、その順に処理していく
各青い点に対して、以下の条件を満たす赤い点が存在しないときはスキップして、存在するときは座標が最大のものとペアにしていく
- まだどの青い点ともペアにされずに残っている
- その青い点よりも $x$ 座標も $y$ 座標も小さい

計算量は、「各青い点に対して条件を満たす赤い点を探索する」という単純な実装で $O(N^{2})$ となります。今回の制約は $N \le 100$ であるため、十分間に合います。

「交換しても悪化しない」による証明

上記の直感的な説明は、貪欲法の証明でよくある「交換しても悪化しないことを示す」という論法で示せます。

まず青い点を $x$ 座標が小さい順に並べたとします。そのうちの最初の点 $B(b_{x}, b_{y})$ ( $x$ 座標が最小の点) について考えます。

点 $B$ よりも $x, y$ 座標がともに小さい赤い点が存在しないならば $B$ がペアを組むことはできませんし、1 個しかないならばそれと $B$ がペアを組んで損することは絶対にありません (その 1 個の点が他の青い点と組んだとしても、点 B に組み直して解が悪化することはありません)。

そのような赤い点が複数あったとして、そのうちの $y$ 座標が最大の点を $R(r_{x}, r_{y})$ とします。このとき、他の赤い点 $R'(r_{x}', r_{y}')$ と点 $B$ とがペアを組むような解があったとしましょう。

このとき、その解を悪化させることなく、 $B, R$ がペアになる解へと変形できることを示します。まずその解において点 $R$ が他のどの青い点ともペアを組んでいない場合は、 $B$ の相方を $R'$ から $R$ へと組み替えれば良いです。

点 $R'$ が他の点 $B'(b_{x}', b_{y}')$ とペアを組んでいるとします。このとき実はペア $(B, R'), (B', R)$ を解消してペア $(B, R), (B', R')$ に組み替えることができます。なぜなら、まず

$b_{x} \gt r_{x}$ , $b_{x}' \gt b_{x} \gt r_{x}'$

が成り立っていますし、

$b_{y} \gt r_{y}$ , $b_{y}' \gt r_{y} \gt r_{y}'$ ( $r_{y}$ の最大性より)

が成り立つからです。

以上から、点 $B$ に対して $y$ 座標が最大な点 $R$ をペアにするような最適解が存在することが言えました。よって二次元平面上から 2 点 $B, R$ を除去してよく、残った点に対して同様の手続きを進めていくことができます。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 二次元座標を定義
using Point = pair<int,int>;

int main() {
    // 入力
    int N;
    cin >> N;
    vector<Point> red(N), blue(N);
    for (int i = 0; i < N; ++i) cin >> red[i].first >> red[i].second;
    for (int i = 0; i < N; ++i) cin >> blue[i].first >> blue[i].second;

    // 青い点を x 座標が小さい順にソートする (デフォルトで第一引数の辞書順比較)
    sort(blue.begin(), blue.end());

    // 各赤い点が使用済みかどうか
    vector<bool> used(N, false);

    // 青い点を順番に見ていく
    int res = 0;
    for (int i = 0; i < N; ++i) {
        // 使用済みでなく、y 座標最大の赤い点を探す
        int maxy = -1, maxid = -1;
        for (int j = 0; j < N; ++j) {
            // 使用済みの赤い点は不可
            if (used[j]) continue;

            // x 座標, y 座標がより大きい赤い点は不可
            if (red[j].first >= blue[i].first) continue;
            if (red[j].second >= blue[i].second) continue;

            // 最大値を更新
            if (maxy < red[j].second) {
                maxy = red[j].second;
                maxid = j;
            }
        }

        // 存在しない場合はスキップ
        if (maxid == -1) continue;

        // ペアリングする
        ++res;
        used[maxid] = true;
    }
    cout << res << endl;
}

なおこのとき、逆に赤い点たちを $x$ 座標が小さい順に並べてあげて、それぞれの赤い点に対して順番に、どの青い点をペアにしていくかを考えたくなる人も多いでしょう。しかしこの方針だとおそらく上手く解けないです。↩
ここで、 $x$ 座標については実は考慮する必要がないことに注意しましょう。なぜなら、今後登場してくる青い点たちは、すべて点 $B$ よりも $x$ 座標が大きいからです。よって、集合 $S$ に含まれる赤い点たちは、 $x$ 座標のことが理由で今後売れ残る心配はありません。 $y$ 座標のことだけを考えれば良いです。↩