Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-15div2hard 三本勝負(SRM491, 493, 497)

SRM493 div2 第三問(1000pt) CrouchingAmoebas

|  SRM493 div2 第三問(1000pt) CrouchingAmoebas - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM493 div2 第三問(1000pt) CrouchingAmoebas - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11214

範囲を絞って正方形の位置を全探索。

はじめ、Amoebaの動かし方について、

x軸 or y軸に沿っていくらでも動かせる(飛車の動き)かと勘違いした。


public class CrouchingAmoebas {
	public int count(int[] x, int[] y, int A, int T) {
		int size = x.length;
		int max = 1;
		for (int fx = 0 ; fx < size ; fx++) {
			for (int fy = 0 ; fy < size ; fy++) {
				for (int dx = -T ; dx <= T ; dx++) {
					for (int dy = -T ; dy <= T ; dy++) {
						if (Math.abs(dx) + Math.abs(dy) > T) {
							continue;
						}
						int xx = x[fx] + dx;
						int yy = y[fy] + dy;
						long[] needs = new long[size];
						for (int i = 0 ; i < size ; i++) {
							long distance = 0;
							if (x[i] < xx) {
								distance += xx - x[i];
							} else if (xx + A < x[i]) {
								distance += x[i] - (xx + A);
							}
							if (y[i] < yy) {
								distance += yy - y[i];
							} else if (yy + A < y[i]) {
								distance += y[i] - (yy + A);
							}
							needs[i] = distance;
						}
						java.util.Arrays.sort(needs);
						long total = 0;
						int num = 0;
						for (int i = 0 ; i < size ; i++) {
							total += needs[i];
							if (total > T) {
								break;
							}
							num++;
						}
						max = Math.max(max, num);
					}
				}
			}
		}
		return max;
	}
}