Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-20[復習] SRM459、SRM461

SRM461 div2 第二問(550点)

| SRM461 div2 第二問(550点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM461 div2 第二問(550点) - hama_DU@TopCoderへの道

http://topcoder.g.hatena.ne.jp/hama_DU/20100214/p2

http://www.topcoder.com/stat?c=problem_statement&pm=10731&rd=14181

イミフな英語に定評のある問題。細かい条件のお話がありますが使わなくてもいいようです。

Math.sqrtの値がNANになってしまう問題を解決。

あと配列を降順に並び替えたり、関数を使って一般化してみた。


public class ColoringRectangle {
	public void reverseArray(int[] array) {
		int length = array.length;
		int length2 = length / 2;
		int temp;
		for (int i = 0 ; i < length2 ; i++) {
			temp = array[i];
			array[i] = array[length - i - 1];
			array[length - i - 1] = temp;
		}
	}


	public int placeDisks(int width, int height, int[] first, int[] next) {
		int all_length = Math.min(first.length, next.length) * 2;
		if (first.length > next.length) {
			all_length++;
		}

		double length = 0;
		int i;
		double h4 = height * height;
		for (i = 0 ; i < all_length ; i++) {
			int d = (i % 2 == 0) ? first[i / 2] : next[i / 2];

			if (d < height) {
				return -1;
			}

			length += (double) Math.sqrt((double)(d * d - h4));
			if (length >= width) {
				return i + 1;
			}
		}

		if (length >= width) {
			return i;
		}
		return -1;
	}


	public int chooseDisks(int width, int height, int[] red, int[] blue) {
		java.util.Arrays.sort(red);
		java.util.Arrays.sort(blue);
		reverseArray(red);
		reverseArray(blue);

		int usedDisksRed = placeDisks(width, height, red, blue);
		int usedDisksBlue = placeDisks(width, height, blue, red);

		if (usedDisksRed == -1 && usedDisksBlue == -1) {
			return -1;
		} else if (usedDisksRed == -1) {
			return usedDisksBlue;
		} else if (usedDisksBlue == -1) {
			return usedDisksRed;
		} else {
			return Math.min(usedDisksBlue, usedDisksRed);
		}
	}

}