C - ID
はじめに
競技プログラミング、AtCoder Beginner Contest 113
C - ID
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
Atcoder国にはN個の県があり、これらの県には合計でM個の市が属しています。 市iが誕生したのはYi年であり、県Piに属しています。 ただし、同じ年に誕生した市が複数存在することはないとします。 それぞれの市に12桁の認識番号を割り振ることとなりました。 市iが県Piに属する市の中でx番目に誕生した市のとき、 市iの認識番号の上6桁は Pi下6桁は xとなります。 ただし、Piやxが6桁に満たない場合は 6桁になるまで0を左に追加するものとします。 全ての市の認識番号を求めてください。 ただし、市が1つも属さない県がある場合に注意してください。
制約
1≤N≤10^5 1≤M≤10^5 1≤Pi≤N 1≤Yi≤10^9 Yiは全て異なる 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。 N M P1 Y1 : PM YM
出力
全ての市の認識番号を市の番号の昇順に出力せよ。
解き方
入力された市のデータをもとに、市の番号を入力された順番で出力する。
問題文から、
出力する番号は「県の番号+市の番号」であり、
県の番号はそのまま出力すればいいので
問題は市の番号をどのように変換するかである。
市の番号を並び替えつつ、入力のindexを保存する
市の番号は県の中での生まれた順番に依るが
初めから県ごとに分けて考えていくことは面倒なので、
県関係なく
市の生まれた年を全て
配列に格納して並び替え、
それをもとに県ごとの市の番号を考える。
市を並び替えるときに、
入力された状態のインデックスも一緒に並び替えてしまえば
後で出力するときに、もとの順番を作ることができる。
city[]:市の生まれた年を格納した配列 index[]:入力された順番 Array.Sort(city,index);
以上のもので、
市の年を若い順に並びかえつつ
indexを並び替えることができる。
例えば、例題1であれば以下のようになる。
入力
2 3 1 32 2 63 1 12
city[3]:市の生まれた年を格納する配列
index[3]:indexを保存する配列
とすると、
まず以下のように入力を格納することができる。
city={32,63,12}; index={0,1,2};
これを市が生まれた順に並び替える
Array.Sort(city,index);
すると各配列の中身は以下のようになる。
city={12,32,63}; index={2,0,1}
こうしておけば、
元のindexが分かるので
最後にもとの順番で出力させることができる。
出力させる順番に、配列に値を格納する
以下のものを作成した。
前提として
出力は問題文より
「県の番号6桁+市の番号6桁」で出力する
(配列名は任意)
県の番号
pri[N]という配列を用意し、入力を保存しておく
indexに沿ってそのまま県の番号を出力する
市の番号
priCount[N+1]という配列を用意し、
市が出てくるたびに
該当する県の中の、市の数のカウントを1進める
例:priCount[1]→県1の中で、市が今いくつ出てきたかのカウント→市の番号
Array.Sort()で並び替えた市の順番を基準として、
ループを回しながら、
答えを格納する配列(ans[M])の中に
そのまま出力する順番となるように
値を入れていく。
//入力された市の数ぶんループを回す for(int i=0;i<M;++i){ //並び替えた市の順番を基準として考える //ループの中で今見ている市の県のカウントを1進める priCount[pri[index[i]]]++; //最後の出力はansのindexを0から回して、できるようにする ans[index[i]]=string.Format("{0:D6}",pri[index[i]])+stringFormat("{0:D6}",priCount[pri[index[i]]]); }
全体のコード
using System; using System.Linq; using System.Collections.Generic; class MondaiC { static void Main() { var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray(); //県の数 var N = line[0]; //市の数 var M = line[1]; //入力のindex保存用 var index = new int[M]; //市の生まれた年を格納する配列 var city = new long[M]; //県の生まれた年を格納する配列 var pri=new int[M]; //値をそれぞれの配列に入れる for (int i=0;i<M;++i) { var l = Console.ReadLine().Split(' ').Select(x=>Int32.Parse(x)).ToArray(); //県 pri[i] = l[0]; //市 city[i] = l[1]; //index index[i] = i; } //市の生まれた年順に並び替える Array.Sort(city,index); //答えを格納する配列を準備 var ans = new string[M]; //今の市が何番目かをカウントする配列 var priCount = new int[line[0] + 1]; //市の数ぶんループを回す for (int i = 0; i < M; ++i) { //県の中の、市の番号カウントを1進める priCount[pri[index[i]]]++; //答えを格納する配列に「県の番号+市の番号」を格納する ans[index[i]]= string.Format("{0:D6}", pri[index[i]])+ string.Format("{0:D6}", priCount[pri[index[i]]]); } //答えを出力する foreach (var a in ans) { Console.WriteLine(a); } } }