Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM459 div2 第二問(500点)

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

http://topcoder.g.hatena.ne.jp/hama_DU/20100121/1264055520

http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145

Xの値は負でも小数でも良いので、結局-0.5から0.5ずつ増やす方針で実装。


import java.util.HashMap;

public class Inequalities {
	public int maximumSubset(String[] inequalities) {
		int size = inequalities.length;
		String[] eq = new String[size];
		int[] values = new int[size];

		int i = 0;
		for (String inequality : inequalities) {
			String[] elements = inequality.split(" ");
			eq[i] = elements[1];
			values[i] = Integer.valueOf(elements[2]);
			i++;
		}

		int max = 0;
		for (double x = -0.5 ; x <= 1000.5 ; x += 0.5 ) {
			int forthis = 0;
			for (i = 0 ; i < size ; i++) {
				if ("=".equals(eq[i]) && x == values[i]) {
					forthis++;
				} else if (">=".equals(eq[i]) && x >= values[i]) {
					forthis++;
				} else if (">".equals(eq[i]) && x > values[i]) {
					forthis++;
				} else if ("<".equals(eq[i]) && x < values[i]) {
					forthis++;
				} else if ("<=".equals(eq[i]) && x <= values[i]) {
					forthis++;
				}
			}

			if (max < forthis) {
				max = forthis;
			}
		}

		return max;
	}
}

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

}