Edited at

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#】2次元配列(ジャグ配列・多次元配列)のソート

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