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

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

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

いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。

問題概要

 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;
}