Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-01-10SRM483(DIV1)

SRM483 第一問(250pt) BestApproximationDiv1

|  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道

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

1000(a) * 1000(b) で全探索余裕でした

何か引っ掛けがあるかと思いきや、特になし。

public class BestApproximationDiv1 {
	public int eq(double x, String number) {
		String enumber = String.valueOf(x);
		int size = enumber.length();
		if (size < 8) {
			for (int i = size ; i < 8 ; i++) {
				enumber += "0";
			}
		}
		int match = 0;
		for (int i = 0 ; i < 8 ; i++) {
			if (i == 1) continue;
			if (enumber.charAt(i) != number.charAt(i)) {
				break;
			}
			match++;
		}
		return match;
	}

	public String findFraction(int maxDen, String number) {
		int maxeq = 0;
		int maxa = 0;
		int maxb = 0;
		for (int a = 0 ; a <= maxDen ; a++) {
			for (int b = 0 ; b < a ; b++) {
				double d = b * 1.0 / a;
				int eq = eq(d, number);
				if (eq > maxeq) {
					maxeq = eq;
					maxa = a;
					maxb = b;
				}
			}
		}
		return maxb+"/"+maxa+" has "+maxeq+" exact digits";
	}
}

SRM483 第二問(500pt) Bribes

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

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

ポイントは賄賂の影響が前後8人までしか伝わらないこと。

そこで、ある人を堕とすことができる、17人(前8人、後8人、本人で17名)の賄賂パターンを17bitで表してやるといいようです。

「0」を賄賂しない、「1」を賄賂するに対応させると、例えば本人と前後1人ずつに対して賄賂する場合は

← 並び順
00000001 1 10000000(2)

と表せます。

そして、ある人に対して上記パターンで賄賂に成功した場合は、

次の人に対する賄賂は1bitずつ右にずらして、次のように表せます。

← 並び順
?0000000 1 11000000(2)

? の部分には「0」と「1」を入れ、次の人に対する賄賂の探索候補とします。


public class Bribes {
	public int minBribes(int[] influence, int[] resistance) {
		int len = influence.length;
		int[] inf = new int[len + 17];
		for (int i = 8 ; i < len + 8 ; i++) {
			inf[i] = influence[i-8];
		}

		int[][] dp = new int[len+1][1<<17];
		for (int n = 1 ; n <= len ; n++) {
			java.util.Arrays.fill(dp[n], -1);
		}

		for (int i = 0 ; i < len ; i++) {
			for (int pattern = 0 ; pattern < 1<<17 ; pattern++) {
				if (dp[i][pattern] == -1) {
					continue;
				}

				int bib = 0;
				for (int j = 0 ; j < 17 ; j++) {
					if (((1 << j) & pattern) > 0) {
						bib += inf[i+j] >> Math.abs(8 - j);
					}
				}
				if (bib >= resistance[i]) {
					int next = pattern >> 1;
					int val = (pattern & 1) + dp[i][pattern];

					if (dp[i+1][next] == -1) {
						dp[i+1][next] = val;
					} else {
						dp[i+1][next] = Math.min(dp[i+1][next], val);
					}

					next |= 0x10000;
					if (dp[i+1][next] == -1) {
						dp[i+1][next] = val;
					} else {
						dp[i+1][next] = Math.min(dp[i+1][next], val);
					}

				}
			}
		}

		int minnum = -1;
		for (int i = 0 ; i < 1<<17 ; i++) {
			if (dp[len][i] >= 0) {
				int bribenum = Integer.bitCount(i) + dp[len][i];
				if (bribenum < minnum || minnum == -1) {
					minnum = bribenum;
				}
			}
		}
		return minnum;
	}
}