AtCoder Beginner Contest 113 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
ABC113のC問題。
何をすればいいかは分かったけど、 やっぱり実装方法でかなり悩んでしまった。
自分なりに解き方をまとめてみる（といいつつ何もまとめていない）。
緑の人がこの辺の問題を解けてないのを見ると、「こいつら実装力あるって言って大丈夫か」って思っちゃう部分もある。数学的な思考力があれば、実装力が全然なくても到達できちゃうのが緑、という側面はあるのよね。https://t.co/MryU1zLy6Q
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 19, 2019
C - ID
N個の県があり、これらの県には合計でM個の市が属している。
市i は Yi 年に誕生し、 県Pi に属している。
ここでそれぞれの市に12桁の識別番号を割り振ることにした。
市i が県 Pi の中で x 番目に誕生した市であるとき、 識別番号の上6桁を Pi、下6桁を x とする。
すべての市の認識番号を求めよ（入力順に出力する）。
解き方
まず、県Piについてソートすると同じ県同士がまとめられる。
そして、同じ県の中で誕生年順にソートする。
あとは県毎に市の順番をカウントして整理して出力するだけ。
なのに実装するときに、 公式の解説に載っているコードと同じようなことを思いついたんだけど、 勘違いでTLEする気がして他の方法を考えようとなってしまった。
それでいろいろいじってmapとか使って解いた。
公式の解説 : https://img.atcoder.jp/abc113/editorial.pdf
公式の解説のコードはだいぶスマート。
あと、こちらの解説記事も分かりやすかった。
特にpairの使い方でこんなことができるのかと思った。
pairを二つ使って三つの値をひとまとめにしてソートする。
こんな感じ
pair<pair<P, Y>, i> ： <<県, 年>, i番目>
pairのデータについてソートを行うと、 まず first のについてソートを行い、 first の値が同じもの同士は second の値についてソートが行われるらしい。
実際に確認してみる。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
// <<P,Y>,i>のように三つのデータを一つの配列で扱う
vector<pair<pair<int, int>, int>> data(10);
// データを入力
data[0] = make_pair(make_pair(1, 1), 0);
data[1] = make_pair(make_pair(2, 2), 1);
data[2] = make_pair(make_pair(3, 3), 2);
data[3] = make_pair(make_pair(1, 7), 3);
data[4] = make_pair(make_pair(5, 6), 4);
data[5] = make_pair(make_pair(1, 5), 5);
data[6] = make_pair(make_pair(2, 1), 6);
data[7] = make_pair(make_pair(1, 9), 7);
data[8] = make_pair(make_pair(3, 4), 8);
data[9] = make_pair(make_pair(1, 8), 9);
// Xについてソート、Xが同値の中でYについてもソート
sort(data.begin(), data.end());
// ソートされているか確認
for(auto d: data)
{
cout << d.first.first << " ";
cout << d.first.second << " ";
cout << d.second << endl;
}
return 0;
}
出力結果
P Y i ------ 1 1 0 1 5 5 1 7 3 1 8 9 1 9 7 2 1 6 2 2 1 3 3 2 3 4 8 5 6 4
このようにしてpairを使っても解くことができる。
もちろん、配列で十分ではあるけども。
おわりに
勉強になった
