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);
        }
    }
}