【プログラミングコンテスト】AtCoder Beginner Contest 113①
土曜日のAGCは時間が合わなくて解けませんでした、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc113)にて開催されました、AtCoder Beginner Contest 113の第3問「C - ID」の問題と僕との戦闘記です。
0.はじめに
1.問題文
Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。
市 i が誕生したのは Y i 年であり、県 P i に属しています。
ただし、同じ年に誕生した市が複数存在することはないとします。
それぞれの市に 12 桁の認識番号を割り振ることとなりました。
市 i が 県 P i に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は P i 、下 6 桁は x となります。
ただし、 P i や x が 6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。
全ての市の認識番号を求めてください。
ただし、市が 1 つも属さない県がある場合に注意してください。
2.入力例
- 入力
2 3 1 32 2 63 1 12
- 出力
000001000002 000002000001 000001000001
- 市 1 は県 1 に属する市の中で 2 番目に誕生したので、認識番号は 000001000002 となります。
- 市 2 は県 2 に属する市の中で 1 番目に誕生したので、認識番号は 000002000001 となります。
- 市
3
は県
1
に属する市の中で
1
番目に誕生したので、認識番号は
000001000001
となります。
3.初見の感想
- 県番号はそのまま冒頭の番号にできる
4.学びポイント
- 市の作成年と市を対応させるために二次元配列を使用しました!
- Dictionaryなどでも解決できる気がします!
5.コードの簡単な解説
- 入力を配列に入れる
string[] str = Console.ReadLine().Split(); int N = int.Parse(str[0]); int M = int.Parse(str[1]); int[][] B = new int[M][]; for(var i=0;i<M;i++){ B[i] = new int[3]; string[] str2 = Console.ReadLine().Split(); B[i][0] = int.Parse(str2[0]); B[i][1] = int.Parse(str2[1]); B[i][2] = i; }
- 年でソートを行って成立順を計算
Array.Sort(B,(x,y)=>x[1] - y[1]); int[,] C = new int[M,2]; int[] D = new int[N]; for(var i=0;i<M;i++){ C[B[i][2],0] = B[i][0]; C[B[i][2],1] = D[B[i][0]-1]+1; D[B[i][0]-1] += 1; }
- 出力を作成
string[] E = new string[M]; for(var i=0;i<M;i++){ string a1 = "000000"+C[i,0].ToString(); a1 = a1.Substring(a1.Length-6,6); string a2 = "000000"+C[i,1].ToString(); a2 = a2.Substring(a2.Length-6,6); E[i] = a1+a2; } for(var i=0;i<M;i++){ Console.WriteLine(E[i]); }
6.全コード
using System; using System.Collections.Generic; class Program { static void Main(string[] args) { string[] str = Console.ReadLine().Split(); int N = int.Parse(str[0]); int M = int.Parse(str[1]); int[][] B = new int[M][]; for(var i=0;i<M;i++){ B[i] = new int[3]; string[] str2 = Console.ReadLine().Split(); B[i][0] = int.Parse(str2[0]); B[i][1] = int.Parse(str2[1]); B[i][2] = i; } Array.Sort(B,(x,y)=>x[1] - y[1]); int[,] C = new int[M,2]; int[] D = new int[N]; for(var i=0;i<M;i++){ C[B[i][2],0] = B[i][0]; C[B[i][2],1] = D[B[i][0]-1]+1; D[B[i][0]-1] += 1; } string[] E = new string[M]; for(var i=0;i<M;i++){ string a1 = "000000"+C[i,0].ToString(); a1 = a1.Substring(a1.Length-6,6); string a2 = "000000"+C[i,1].ToString(); a2 = a2.Substring(a2.Length-6,6); E[i] = a1+a2; } for(var i=0;i<M;i++){ Console.WriteLine(E[i]); } } }
7.最後に
とりあえず週3ブログ投稿ペースを守れているので一安心(^-^;