Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/09/28

SRM 483 Bribes

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11037&cr=22851423

問題

選挙において投票者に最小限の賄賂を渡して勝つようにする.n 人の投票者がいて,それぞれ影響度 influence と抵抗度 resistance が存在する.i 番目の人に賄賂を渡すと,j 番目の人の抵抗度が influence[i]/2^|i-j| だけ減る.全員の抵抗度が 0 以下になれば賄賂は成功する.賄賂が成功する渡し方のうち,賄賂を渡す人数が最小になる人数を返す.できなければ失敗として -1 を返す.

アプローチ

一見すると O(n*2^n) な複数ナップサック問題のように見えるが,影響度の値が 500 以下,つまり 2^9 より小さいので両隣 8 人目まで考慮すればいいことが分かる.これで 2^n の部分が 2^17 の定数で押さえられるので O(n).で解くことができる(定数項はそれなりに大きいので注意).

両隣 8 人を含めた計 17 人への賄賂を 17-bit で表現することができる.DP の問題の分割は投票者の人数で行うことができる.つまり0人,1人,と増やしていく.i 人目の抵抗度を 0 にするには i-8 人目から i+8 人目までの影響度を考慮すればいい.抵抗度を 0 にできるパターンの中から最も賄賂を渡す人数が少ないパターンを記録している. i+1 人目を計算するには i 人目のビットパターンのうち上位 16-bit だけ分かればよいので,配列に保存するのは 16-bit 分で良いことが分かる. n 人目まで繰り返していき,最小の値(人数)を選ぶ.

配列のサイズが大きいので int では allocate できない.short を使う.

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

#include <cmath>

using namespace std;

#define sz(a) int((a).size())
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

short dp[51][1<<16];

int minBribes(vector <int> influence, vector <int> resistance)
{
	int n = sz(influence);
	int INF = 100;
	
	Rep(i,n+1) Rep(j,1<<16)
		dp[i][j] = i ? INF : __builtin_popcount(j);
	
	Rep(i,n) Rep(mask,1<<17)
	{
		int sum = 0;
		for(int j=i-8,k=0; j<=i+8; j++,k++)
			if((mask&(1<<k)) && 0<=j&&j<n)
				sum += influence[j]>>abs(j-i);
		if(sum>=resistance[i])
			dp[i+1][mask>>1] = min(
				(int)dp[i+1][mask>>1],
				(int)dp[i][mask%(1<<16)]+mask/(1<<16)
			);
	}
	int r = INF;
	Rep(j,1<<16)
		r = min(r,(int)dp[n][j]);
	
	return r>n ? -1 : r;
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/