【AtCoder】ABC 298 C - Count Order | 茶コーダーが解くAtCoder

atcoder.jp

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

問題

から までの番号が付いた 個の箱と、何も書かれていない無数のカードがある。以下に示す3種類のクエリが計 個与えられるので、順番に処理せよ。

• 1 i j : カードを1枚選んで数 を書き込み、そのカードを箱 に入れる。
• 2 i : 箱 に入っているカードに書かれた数を昇順で全て出力する(同じ数が書かれたカードが複数枚あるときは、入っている枚数と同じ回数だけその数を出力する)。
• 3 i : 数 が書かれたカードが入っている箱の番号を昇順で全て出力する(同じ箱に複数枚入っている場合でも、その箱の番号は1度だけ出力する)。

制約

• 入力はすべて整数
• 
• 出力すべき数は合計 個以下
• クエリ1について、
  • 
  • 
• クエリ2について、
  • 
  • このクエリが与えられる時点で箱 にカードが入っている
• クエリ3について、
  • 
  • このクエリが与えられる時点で数 が書かれたカードが入っている箱が存在する

考察

各クエリについて処理を考えていく。最大で 回のクエリが飛んでくるので、なるべく高速に処理を行う必要があることを念頭に置いておく。

クエリ1について

とりあえず「各カードをどの箱に入れたのか」を記録する配列は必要だろう。box[箱の番号][その箱に入っているカードの番号]という二次元配列を考えてみる。

このとき、数 を書いたカードを箱 に入れる操作は、

box[j].push_back(i)

と書ける。これは で行うことができる。

クエリ2について

前項で考えた二次元配列box[][]について、box[i]の中身を昇順ソートして順番に出力してしまえばよい。これは対数時間で行えそう。

クエリ3について

数 が書かれたカードがどの箱に入っているのかを、box[][]からいちいち検索していたのでは間に合わない。そこで、「各数はどの箱に入っているのか」を記録する二次元配列を新たに用意することを考える。ただし、クエリ2とは違って、出力時に重複した数は1つの要素にまとめて昇順にする必要があるので、C++ではsetを利用してみるのがよさそう。ここではvector<set<int>> card[数][その数が入っている箱の番号の集合]とした。

このとき、クエリ1において、数 を書いたカードを箱 に入れる操作をするとき、

card[i].insert(j)

と書ける。これも で行うことができる。また、出力時にはcard[i]の要素を順番に出力すればよい。

以上を丁寧に実装していく。なお、出力時、各行最後の空白の処理についてはサボってそのままにしている。

コード

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

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

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

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> box(202020, vector<int>());
    vector<set<int>> card(202020, set<int>());
    rep(i, 0, Q)
    {
        int q;
        cin >> q;

        if (q == 1)
        {
            int i, j;
            cin >> i >> j;
            box[j].push_back(i);
            card[i].insert(j);
        }
        else if (q == 2)
        {
            int i;
            cin >> i;

            sort(all(box[i]));
            for (auto &&x : box[i])
            {
                cout << x << " ";
            }

            cout << endl;
        }
        else if (q == 3)
        {
            int i;
            cin >> i;

            for (auto &&x : card[i])
            {
                cout << x << " ";
            }
            cout << endl;
        }
    }
}

atcoder.jp

補足

• 解説を見たところ、わざわざsetを使わずとも普通の二次元配列で出来るみたい。
• 出力時の各行最後の空白をなくすには、解説にあるようにすればよいらしい。

実装時間: 40分

こういったクエリ処理系の問題は個人的に好きな部類。