AtCoder ABC113 C - ID(300点)

問題概要

$N$ 個の県と $M$ 個の都市がある。
市 $i$ は $Y_i$ 年の誕生し、 $P_i$ 県に属している。なお同じ年に生まれた市は存在しない。

市 $i$ が 県 $P_i$ に属する市の中で $x$ 番目に誕生した市のとき、市 $i$ の認識番号の上 $6$ 桁は $P_i$、下 $6$ 桁は $x$ となるような認識番号をそれぞれの市 $i$ に振り分ける。

全ての市の認識番号を求めよ。

制約条件

• $1≤N≤10^5$
• $1≤M≤10^5$
• $1≤P_i≤N$
• $1≤Y_i≤10^9$
• $Y_i$ は全て異なる
• 入力は全て整数

考えたこと

問題文をパット見でいいかんじにソートしたらよさそうと思った。

ではどうソートするかなのだが、認識番号は「所属する県」と「生まれた年」で構成される。所属する県はすでにわかっているが、その県の中でどれだけ古い県かは明らかになっていない。
よって年でソートして古い順に所属する県を数え上げていく。

あとは初めの市 $i$ の順番にソートしなおして出力。

考察よりも実装がめんどくさいなという問題。

多次元配列のソートのやり方は以下の記事を参照したらよい。
【C#】２次元配列（ジャグ配列・多次元配列）のソート

Array.Sort(array, (a, b) => a[1] - b[1]);  //昇順(index=1)

文字列を左詰めで出力する方法も忘れていたので調べた。以下の記事に詳しく書いてある。
- 書式指定文字列 (Format Strings)
- C#のstring.Formatで桁数や書式を指定する

String.Format("{0:D6}", i) //iは数字

解答

c.cs

using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = s[0];
        int m = s[1];
        int[][] l = new int[m][];
        for (int i = 0; i < m; i ++) {
            l[i] = new int[4];
            int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            l[i][0] = i;
            l[i][1] = a[0];
            l[i][2] = a[1];
        }
        Array.Sort(l, (a, b) => a[2] - b[2]);
        int[] c = new int[n];
        for(int i = 0; i < m; i ++) {
            c[l[i][1]-1] ++;
            l[i][3] = c[l[i][1]-1];
        }
        Array.Sort(l, (a, b) => a[0] - b[0]);
        for(int i = 0; i < m; i ++) {
            Console.WriteLine(String.Format("{0:D6}", l[i][1]) + String.Format("{0:D6}", l[i][3]));
        }
    }
}