Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-01-10SRM483(DIV1)

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