GoogleCodeJam2012 1A B "Kingdom Rush"

問題: https://code.google.com/codejam/contest/1645485/dashboard#s=p1&a=1

レベルごとにレート１とレート２のふたつ段階があって，それぞれのレベルにおけるレートに挑戦するのに必要な星の数な数が決まっている．それぞれのレベルのレートによって手に入る星は１つか２つであるが，すべてのレベルのレート２をクリアするために必要な最小挑戦回数を求める．

本番では「大きい順番で見ていけばいいんじゃね？」と思ってたけどサンプル４がさっぱりわからなかった． yak_ex さんに教えてもらってアハ体験．

2-1star > 2-2star > 3-2star > 1-1star > 1-2star > 5-2star > 4-2star

の7だと思ってたけど実際には

1-1star > 2-2star > 3-2star > 1-2star > 5-2star > 4-2star

で大丈夫だったらしい．うーむ．

import java.util.*;
import java.io.*;

public class B {
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(new File("B-large-practice.in"));
		for (int t = 1, T = s.nextInt(); t <= T; ++t) {
			int n = s.nextInt();
			int[][] a = new int[n][];
			for (int i = 0; i < n; ++i) {
				a[i] = new int[] { s.nextInt(), s.nextInt() };
			}
			Arrays.sort(a, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[1] - o1[1];
				}
			});
			int star = 0, r = 0, bc = 0;
			boolean[][] b = new boolean[n][2];
			l: for (; bc < n; ++r) {
				for (int i = 0; i < n; ++i) {
					if (!b[i][1]) {
						if (a[i][1] <= star) {
							b[i][1] = true;
							++bc;
							star += b[i][0] ? 1 : 2;
							continue l;
						}
					}
				}
				for(int i = 0; i < n; ++i){
					if(!b[i][1] && !b[i][0]){
						if(a[i][0] <= star){
							b[i][0] = true;
							star += 1;
							continue l;
						}
					}
				}
				r = -1;
				break;
			}
			System.out.printf("Case #%d: %s\n",  t, r < 0 ? "Too Bad" : r);
		}
	}
}