ABC024_C問題

なんとか解けたので、久しぶりに更新。

AtCoder社のAtCoder Beginner Contest（ABC)のC問題。
http://abc024.contest.atcoder.jp/

良かった点
・２次元配列を使わなかったので計算量が指数爆発せずに済んだ。

悪かった点
・ホワイトボード上での机上設計では別の考えで実装しようと考え、
コーディング中に方針を転換したところ。

以下、メインの部分

	class MainClass
	{
		public static void Main (string[] args)
		{
			Scanner cin = new Scanner ();

			int N = cin.nextInt (); //街の数
			int D = cin.nextInt (); //移動にかかる日数
			int K = cin.nextInt (); //民族の個数
			int[] L = new int[D];
			int[] R = new int[D];
			for (int i = 0; i < D; i++) {
				L[i] = cin.nextInt (); //制約L
				R[i] = cin.nextInt (); //制約R
			}
			int[] S = new int[K]; //最初の街
			int[] T = new int[K]; //目的の街

			int[] ans = new int[K];
			for (int i = 0; i < K; i++) {
				S[i] = cin.nextInt ();
				T[i] = cin.nextInt ();
			}

			for (int i = 0; i < K; i++) { //移民の数
				int min = S [i];
				int max = S [i];

				for (int k = 0; k < D; k++) {
					if ((R [k] < min) || (L [k] > max)) { //今までの渡航可能場所と被っていない場合
						;
					} else {
						min = Math.Min (min, L [k]);
						max = Math.Max (max, R [k]);

						if (min <= T [i] && max >= T [i]) {
							ans [i] = k + 1; //0日目から開始しているため+1
							break;
						}
					}
				}
			}
			for (int i = 0; i < K; i++) {
				Console.WriteLine (ans [i]);
			}
		}
	}

久しぶりにすっきりした回答ができた。

追記：解説を見ていたら進める場合はできるだけ近づく（貪欲法）で良かったらしい。。。
さらに追記：自分の方法はRangeと呼ばれるらしい。