ABC113 - C: ID

二次元 vector で各要素を可変長にして使えることを知らなかった，ということに尽きる問題． std::vector は，二次元 vector を宣言することにより各要素を push_back で個別に伸ばすことができます（日本語下手ですみません、本文見てください）．

問題

• ABC113 - C: ID

思考過程

初め 30 分は思考停止．どのように違う位置にある誕生年をソートするかで悩んだ．入力の順序は必ず保存しとかないといけないので，誕生年をソートするためのコンテナをもう一つ用意する必要があるなとか考えていた．あと，誕生年が制約上重複しないからそれを std::map で利用すれば良いなとか思っていた．結局言葉で説明するのがめんどくさいくらい複雑なことをしてしまって上手く解法を考えることができなかった．

解説

• editorial

以下公式解答の引用．

県ごとに、その県に属する市を誕生した順にソートして、認識番号を割り振るとよいです。

それはそうという印象... 県ごとに誕生年を取り出し，それを保持する方法（データ構造）が分からなかったのが敗因（それっぽい図は書けていたので）．それが出来ればあとは誕生年の一意性を利用して連想配列 std::map にその県で何番目に生まれたかを保存し，それを取り出すようなコードを書けば良い．以下解説 AC したコード．

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;

#define REP(i, n) for (ll i=0; i < n; i++)  // 0 ~ n-1
#define REPN(i, n) for (ll i=1; i <= n; i++)  // 1 ~ n
#define zero_pad(num) setfill('0') << std::right << setw(num)
#define space_pad(num) setfill(' ') << std::right << setw(num)

typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, M;
    cin >> N >> M;
    vector<ll> Pref(M), Year(M);
    vector<vector<int>> pref_year(N+1);  // 県ごとの誕生年を管理する
    REP(i, M) {
        cin >> Pref[i] >> Year[i];
        pref_year[Pref[i]].push_back(Year[i]);
    }

    // calculation
    // 各県の誕生年をソート
    map<ll, ll> year_rank;
    REPN(i, N) {
        sort(pref_year[i].begin(), pref_year[i].end());
        for (ll j = 0; j < pref_year[i].size(); ++j) {
            year_rank[pref_year[i][j]] = j + 1;
        }
    }

    REP(i, M) {
        cout << zero_pad(6) << Pref[i] << zero_pad(6) << year_rank[Year[i]] << "\n";
    }

    return 0;
}

パティングのやり方は私の過去記事で紹介している．

pyteyon.hatenablog.com

ちなみに，std::map を std::unordered_map で宣言すると，127ms から 72ms になったので，これは TLE になってしまった時用に覚えておきたい．

ポイント：std::vector を使って各要素が可変長なデータ構造を作る

この問題のポイントは，バラバラに入力，保持された各県の情報をどのように整理するか，だと思う．例えば以下のように，県の番号がバラバラに与えられるのでそれらを上手く整理しないといけない．

# 入力例
# 県番号 誕生年
2 77
1 32
2 55
1 12
2 63
1 99

以上のような入力を，下図のようなデータ構造で保持できればこの問題は楽に解ける．

C++ では，これを実装する方法の一つとして std::vector がある． 詳しくは解説 AC したコードを読み解いて欲しいが， 二次元 vector を，二次元目の要素数を指定せずに宣言すれば，vector の各要素が，要素数 0 の vector で初期化される． あとは， i 番目に入力された県の番号，誕生年を vec[Pref[i]].push_back(Year[i])で継ぎ足していけば，上図のようなデータ構造を実現できる．

ll N, M;
cin >> N >> M;
vector<ll> Pref(M), Year(M);
vector<vector<int>> pref_year(N+1);  // 県ごとの誕生年を管理する
// 解答によると vector<int> vec[N]; でもいけるらしい．

REP(i, M) {
    cin >> Pref[i] >> Year[i];
    pref_year[Pref[i]].push_back(Year[i]);
}

反省

様々なデータの保持の仕方，データ構造を覚えていきましょうという話でした．