ID [AtCoder Beginner Contest 113 C]

atcoder.jp

Map の中に List を入れるという構造に慣れていないので、難しかったです。実装も難しかったんですが、この問題、制限時間がかなり厳しくなっていて、TLEに苦しみました。制限時間は2000ms。私が提出したACコードの実行時間は約1400msでした。C++なんかだともっと楽に通せるんでしょうか。

説明が難しいので、最初に、ACしたコードを載せてしまいます。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	static int nextInt () {return Integer.parseInt(sc.next());}
	public static void main(String[] args) {
		
		int n = nextInt(), m = nextInt();
		
		
		//出力順を記録しておくための配列
		int[] shi = new int[m], num = new int[m];
		
		
		//１：県P毎にArrayListを作成し、市iの番号Yを詰め込んでいく
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
		for (int i=0; i<m; i++) {
			int a = nextInt(), b = nextInt();
			shi[i] = a;
			num[i] = b;
			if (map.containsKey(a) == false) {
				map.put(a, new ArrayList<>());
			}
			map.get(a).add(b);
		}
		
		
		//２：県P毎に、市の番号をソート
		for (Map.Entry<Integer, ArrayList<Integer>> e: map.entrySet()) {
			Collections.sort(e.getValue());
		}
		
		
		//３：市の番号が県P内で何番目か、Mapに記録する
		HashMap<Integer, Integer> map2 = new HashMap<>();
		for (Map.Entry<Integer, ArrayList<Integer>> e: map.entrySet()) {
			for (int i=0; i<e.getValue().size(); i++) {
				map2.put(e.getValue().get(i), i+1);
			}
		}
		
		
		//４：StringBuilderで圧縮してから出力
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<m; i++) {
			sb.append(String.format("%06d%06d", shi[i], map2.get(num[i])));
			sb.append(System.getProperty("line.separator"));
		}
		System.out.println(sb);
		
	}
}

4ステップに分けて記述しました。入力の受け取りには、Scanner だと間に合わないかもしれないと考えて Integer.parseInt(sc.next()) を使っています。このほうが、sc.nextInt() で受け取るより処理速度が速いみたいです。

１、県P毎にArrayListを作成し、市iの番号Yを詰め込んでいく

Map[Integer, ArrayList[Integer]] に、与えられたデータを詰めていきます。配列の配列のような構造ですね。あとで出力するときのために入力の並び順を記録しておかないといけないので、配列も二つ用意しておきます。

２、県P毎に、市の番号をソート

この部分、最大で10万個（N<=10^6）の ArrayList をソートしているので、すさまじく処理が重そうです。

３、市の番号が県P内で何番目か、Mapに記録する

ソート済みの ArrayList から indexOf() で何番目にあるかを調べることもできますが、それで提出したらTLEしてしまったので、いったん Map に移すことで O(1) で調べられるようにしています。

４、StringBuilderで圧縮してから出力

以前も記事にしましたが、ただでさえ時間が足りないのに、出力の数が膨大（M<=10^6）なので、StringBuilder で圧縮してから出力します。String.format のところの "%06d%06d" という記述は他の方の解答を参考にしたもので、なるほどこんな書き方もあるんだなあと勉強になりました。