ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです!

【プログラミングコンテスト】AtCoder Beginner Contest 113①

土曜日のAGCは時間が合わなくて解けませんでした、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc113)にて開催されました、AtCoder Beginner Contest 113の第3問「C - ID」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語C#を使用しています。

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ブログ投稿ペースを守れているので一安心(^-^;