Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

SRM497 div2 第三問(1000pt) MakeSquare

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

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

簡単。


public class MakeSquare {
	public int diff(String a, String b) {
		int al = a.length();
		int bl = b.length();
		int dp[][] = new int[al + 1][bl + 1];
		for (int i = 0 ; i <= al ; i++) {
			dp[i][0] = i;
		}
		for (int i = 0 ; i <= bl ; i++) {
			dp[0][i] = i;
		}

		for (int i = 1 ; i <= al ; i++) {
			for (int j = 1 ; j <= bl ; j++) {
				int d = a.charAt(i-1) == b.charAt(j-1) ? 0 : 1;
				int call = Math.min(
					Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + d
				);
				if (dp[i][j] == 0) {
					dp[i][j] = call;
				} else {
					dp[i][j] = Math.min(dp[i][j], call);
				}
			}
		}
		return dp[al][bl];
	}
	public int minChanges(String S) {
		int min = S.length();
		for (int i = 1 ; i < S.length() ; i++) {
			min = Math.min(min, diff(S.substring(0, i), S.substring(i)));
		}
		return min;
	}
}

SRM491 div2 第三問(1000pt) BottlesOnShelf

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

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

ビットDP。頑張って自力でここまで書いた。

だがTLEする。降参


public class BottlesOnShelf {
	public long gcd(long a, long b) {
		long r = a % b;
		if (r == 0) {
			return b;
		}
		return gcd(b, r);
	}

	public long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}

	public int getNumBroken(int N, int[] left, int[] right, int[] damage) {
		int M = left.length;
		int bits = (1 << M);

		int[] dp = new int[bits];
		long[] dp_min = new long[bits];
		long[] dp_max = new long[bits];
		long[] dp_lcm = new long[bits];
		dp_min[0] = 1;
		dp_max[0] = N;
		dp_lcm[0] = 1;

		for (int i = 0 ; i < bits ; i++) {
			int count = Integer.bitCount(i);
			if (count >= 1) {
				for (int j = (i - 1) & i ; j > 0 ; j = (j - 1) & i) {
					int ct = Integer.bitCount(j);
					dp[i] += dp[j] * (((count - ct) % 2 == 1) ? 1 : -1);
				}
				int max_i_1 = (i - 1) & i;
				long lcm = dp_lcm[max_i_1];
				long min = dp_min[max_i_1];
				long max = dp_max[max_i_1];
				if (min == -1) {
					dp_min[i] = -1;
					continue;
				} else {
					for (int x = 0 ; x < M ; x++) {
						int ptn = 1 << x;
						if ((max_i_1 & ptn) != 0) {
							continue;
						}
						if ((i & ptn) >= 1) {
							if (right[x] < min || max < left[x]) {
								min = -1;
								break;
							}
							lcm = lcm(lcm, damage[x]);
							if (min < left[x]) {
								min = left[x];
							}
							if (right[x] < max) {
								max = right[x];
							}
							break;
						}
					}
					dp_lcm[i] = lcm;
					dp_min[i] = min;
					dp_max[i] = max;
					if (min != -1) {
						if (min % lcm != 0) {
							min += (lcm - min % lcm);
						}
						max -= max % lcm;
						dp[i] += ((max - min) / lcm + 1) * ((count % 2 == 1) ? 1 : -1);
					}
				}
			}
		}
		return dp[(1<<M)-1];
	}
}

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