【AtCoder】ABC 354 C - AtCoder Magics | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 441

問題概要

各カードに強さとコストのパラメーターがあるカードが 枚ある。 番目のカードをカード とするとき、カード の強さは 、コストは である。これから以下の操作をできなくなるまで繰り返す。最終的に捨てられなかったカードの集合を求めよ。

• 操作 : 2つのカード について、 であるようなものを選び、カード を捨てる。

制約

• 入力はすべて整数。
• 
• 
• はそれぞれ相異なる。

考察

の最大値は なので、操作をすべてシミュレーションしていては間に合わない。カードを残す条件は2つあるが、まずは一方を固定して考えていこう。

枚のカードをカードの強さ順に降順ソートする。下図は横軸にカードの強さ、縦軸にカードのコストを取って一部をプロットしたものである (ただし、横軸はカードが「強い順」に並べているので、 と解釈してもらっても良い) 。

ここで、カード とカード をそれぞれ比較したとき、残すカードは「強くてコストが低いカード」なので、

• カード vs カード → カード を残す
• カード vs カード → カード を残す

となる。

つまり、カードを強い順に並べて先頭からカードを見ていったときに、「前のカードよりもコストが低ければそのカードを残し、高ければすてる」ということを繰り返していけばよい。

実装においては、管理したいカードの情報がたくさんあるので、新たにcard構造体を作成した。また、自作構造体の配列をソートするためには、sort関数の第3引数にbool型の比較関数を自分で設定する必要がある。

コード

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

struct card
{
    int strength;
    int cost;
    int index;
};

bool compare(const card &a, const card &b)
{
    return a.strength > b.strength;
}

int main()
{
    int N;
    cin >> N;
    vector<card> cards;
    rep(i, 0, N)
    {
        int A, C;
        cin >> A >> C;
        cards.push_back({A, C, i + 1});
    }

    sort(all(cards), compare);

    vector<int> ans;
    int pre_C = INF;
    for (auto &&card : cards)
    {
        if (card.cost <= pre_C)
        {
            ans.push_back(card.index);
            pre_C = card.cost;
        }
    }

    sort(all(ans));
    cout << ans.size() << endl;
    for (auto &&x : ans)
    {
        cout << x << " ";
    }
    cout << endl;
}

atcoder.jp

実装時間: 30分