問題概要

$N$ 個のペア値 $(A_{1}, C_{1}), \dots, (A_{N}, C_{N})$ が与えられる。

ある $x, y$ について $A_{x} \gt A_{y}$ かつ $C_{x} \lt C_{y}$ を満たすとき、ペア値 $y$ を削除する操作を繰り返す。

最後に残るカードの集合を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

座標平面上にプロットしてみよう ( $A$ を x 座標、 $C$ を y 座標とする)。このとき、この問題は「自分の右下方向には点がないような点」を抽出せよ、と解釈できる。そうすると、下図のように、右下のラインを求める問題となる。

ここからは、いろんな方法が考えられる。僕は

「これまでの y 座標の最小記録」を表す変数 prev を用意しておいて、

x 座標の後ろから見ていって、
新たな最小記録が生まれたとき、その点を答えに加え、prev をその値に書き換える

というようにした。これで計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

struct Card {
    int A, C, id;
    Card() {}
    Card(int a, int c, int i) : A(a), C(c), id(i) {}
};

int main() {
    int N;
    cin >> N;
    vector<Card> v;
    for (int i = 0; i < N; ++i) {
        int A, C;
        cin >> A >> C;
        v.push_back(Card(A, C, i));
    }
    
    // A が大きい順 (右から考えるため) に並び替える
    sort(v.begin(), v.end(), [&](Card a, Card b){return a.A > b.A;});
    
    // y 座標の新記録 (最小側) が生まれたら res に push_back していく
    vector<int> res;
    int prev = 1<<30;
    for (auto card : v) {
        if (card.C < prev) {
            prev = card.C;
            res.push_back(card.id);
        }
    }
    
    // 出力
    sort(res.begin(), res.end());
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 354 C - AtCoder Magics (2Q, 茶色, 350 点)

問題概要

制約

考えたこと

コード