AtCoderテンプレに感じた違和感の正体 EX18 - 2.03

https://atcoder.jp/contests/apg4b/tasks/APG4b_ce
正答はしたが、サンプルコードをそのまま使用したケースについて考える。

以下、回答のテンプレとして用意されていたコード。
直感的にこれを使うと処理が煩雑になると判断して使わなかったが、実際はどうか。

int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
    cin >> A.at(i) >> B.at(i);
}

処理が煩雑になると感じた原因

このコードでは、M試合目の値をA(勝者), B(敗者)それぞれの配列に格納している。

// Aの場合
{ 1回目の試合の勝者番号, 2回目の試合の勝者番号, ... }

となる。ここで違和感が出る。
このコードの最終ゴールは試合結果をテーブルで出力すること。
つまり二重ループで 1からN番目の人まで順番に出力 することを繰り返す。

テンプレコードのデータ処理がマズいと感じたのは、配列の データの順序が試合順で入れられるが、これは出力で利用できない からだ。

また、出力では人の番号順に結果を書き出す必要があるのに 人番号順にデータがソートされていない のも要因である。

違和感の結論

違和感の正体は、以下の通り。

1. 出力から逆算し、人番号でソートされたデータが必要と判断していた
1. テンプレのデータ構造は試合順だが、これは出力で不要な情報だった
2. 出力に必要な人数順のデータを得るのに、ソートやデータ構造の加工など重い処理が必要だった