SRM 483 500pt: Bribes
問題概要
N(<50)人が一列に並んでいる。各人は影響力inflと抵抗力resiを持つ(数値は500以下)。何人かを選ぶ。人iを選んだ場合、各jについてresiをinfl[i]>>abs(i-j)だけ減少させる。全ての人についてresi[i]を非正になるようにしたい。最小何人を選ぶ必要があるか求める問題。無理なら指摘する。
解法
影響力は500以下なので、左右8までの部分にだけ影響を受けるので2^17のビットDPで解ける。というのが基本アイデアなのだけど正確に実装するのがとても難しい。
前処理として、各iについてそこを中心としたどのような集合でresi[i]を非正にできるか計算しておく。この情報を元に適宜ビットをシフトしながらdpテーブルを更新していく。
自分の組み方の場合、dp[i][iを中心とした幅17のビット] = {[0..i]が既にresiが非正になっているときのそこまでの最適値}とした。
計算量は全体でO(N*2^17*17)となりちょっと重いけど間に合う。実装に時間かかりすぎたのでまたいつか解きなおそうと思う。今まで見たビットDPの中で一番難しかった。
practiceで通ったコード
#include <vector> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 50; const int LOG = 8; const int WIDTH = 2 * LOG + 1; const int MASK = (1<<WIDTH) - 1; const int INF = int(1.05e9); int opt[MAX_N + 1][1<<WIDTH]; bool isEnough[MAX_N][1<<WIDTH]; struct Bribes { int minBribes(vector <int> influence, vector <int> resistance) { const int n = influence.size(); for (int i = 0; i < n; ++i) { for (int bit = 0; bit < 1<<WIDTH; ++bit) { int total = 0; for (int j = 0; j < WIDTH; ++j) if (i - LOG + j >= 0 && i - LOG + j < n && ((bit>>j)&1)) { total += influence[i-LOG+j] >> abs(LOG - j); } isEnough[i][bit] = total >= resistance[i]; } } if (n <= WIDTH) { int ans = INF; for (int bit = 0; bit < 1<<WIDTH; ++bit) { bool ok = true; for (int i = 0; i < n; ++i) { int submask = (i <= LOG ? bit<<(LOG - i) : bit>>(i - LOG)); ok &= isEnough[i][submask&MASK]; } if (ok) { updateMin(ans, countPopulation(bit)); } } return ans == INF ? -1 : ans; } for (int i = 0; i <= n; ++i) { fill(opt[i], opt[i] + (1<<WIDTH), INF); } for (int bit = 0; bit < 1<<WIDTH; ++bit) { bool ok = true; for (int i = 0; i <= LOG; ++i) { ok &= isEnough[i][(bit<<(LOG - i))&MASK]; } if (ok) { opt[LOG][bit] = countPopulation(bit); } } for (int k = LOG; k < n - LOG; ++k) { for (int bit = 0; bit < 1<<WIDTH; ++bit) { if (isEnough[k+1][bit>>1]) { updateMin(opt[k+1][bit>>1], opt[k][bit]); } if (isEnough[k+1][(bit>>1)|(1<<(WIDTH-1))]) { updateMin(opt[k+1][(bit>>1)|(1<<(WIDTH-1))], opt[k][bit] + 1); } } } int ans = INF; for (int bit = 0; bit < 1<<WIDTH; ++bit) { bool ok = true; for (int i = 0; i < LOG; ++i) { ok &= isEnough[n - LOG + i][bit>>i]; } if (ok) { updateMin(ans, opt[n - LOG][bit]); } } return ans == INF ? -1 : ans; } };