Beta Round #85 Div1-C Div2-E: Petya and Spiders

Codeforces

問題概要

W*H(W*H<40)のボードがあって、各マスに蜘蛛がいる。蜘蛛に命令して、蜘蛛を上下左右に移動させることができる。蜘蛛の居ないマスの最大値を求める問題。

考えたこと

  • サイズがやたら小さい。
  • 最小支配集合か。
  • H>=Wを仮定するとWの最大値は6。ビットDPが見える。
  • ライツアウトに似た匂いがするけどもう少し面倒そう。
  • 上の列の状態が決まれば今の列をどうすべきかも決まるのでビットDP的なものが見えるけど2状態じゃ足りないので3状態にすれば上手くいきそう？
  • dp[i行目][j列目の状態は(1.そこが中心になる、2.どこかに移動済み、3.まだ移動してない)]として今の列のどこを中心にするか2^W通りしらべればよさそう。
  • これだと全体の計算量がO(H*W*3^W*2^W) = O(H*W*6^W)で間に合いそう。
  • でも3進数扱うの面倒なので別の方法をちょっと考えよう。
  • dp[i行目][どこが中心になっているか][どこがまだ移動していないか]とすれば計算量はO(H*W*2^W*2^W*2^W) = O(H*W*8^W)となる。これでもまだ間に合う。こっちで実装しよう。
  • それに、その状態の組み合わせはinvalidなものが多いので、簡単な枝刈りで多分実際に計算量がおちると思う(真面目に解析したわけじゃないのでただの勘だけど)。まあ、枝刈りしなくても間に合うだろうから枝刈りしないけど。

practiceで通ったコード

計算量O(H*W*8^W)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_H = 40;
const int MAX_W = 6;
const int INF = 1<<29;

int dp[MAX_H+1][1<<MAX_W][1<<MAX_W]; //(row, is_center, still_live)

int solve(int H, int W){

	//DPテーブルの初期化
	for(int i=0; i<H; i++){
		for(int bit=0; bit<(1<<W); bit++){
			fill(dp[i][bit], dp[i][bit]+(1<<W), INF);
		}
	}

	//ビットDP基底計算
	for(int bit=0; bit<(1<<W); bit++){
		int live = (1<<W)-1;
		for(int i=0; i<W; i++)if( (bit>>i)&1 ){
			if(i>0){
				live &= ~(1<<(i-1));
			}
			live &= ~(1<<i);
			live &= ~(1<<(i+1));
		}
		dp[0][bit][live] = __builtin_popcount(bit);
	}

	//ビットDP
	for(int i=1; i<H; i++){
		for(int bit1=0; bit1<(1<<W); bit1++){ //prev row: is_center
			for(int bit2=0; bit2<(1<<W); bit2++){ //prev row: still_live
				for(int bit3=0; bit3<(1<<W); bit3++)if( bit3 == (bit3 | bit2) ){ //cur row: is_center
					int bit4 = (1<<W)-1; //cur row: still_live

					//結果誰が生き残る？
					for(int j=0; j<W; j++)if( (bit1>>j)&1 ){
						bit4 &= ~(1<<j);
					}

					for(int j=0; j<W; j++)if( (bit3>>j)&1 ){
						if(j>0){
							bit4 &= ~(1<<(j-1));
						}
						bit4 &= ~(1<<j);
						bit4 &= ~(1<<(j+1));
					}

					dp[i][bit3][bit4] = min(dp[i][bit3][bit4] , dp[i-1][bit1][bit2] + __builtin_popcount(bit3));
				}
			}
		}
	}

	int ans = INF;
	for(int bit=0; bit<(1<<W); bit++){
		ans = min(ans, dp[H-1][bit][0]);
	}

	return H*W - ans;
}

int main(){
	int W, H;

	//入力
	scanf("%d%d",&H,&W);
	if(H < W){
		swap(H, W);
	}

	//出力
	printf("%d\n", solve(H, W));

	return 0;
}

改善案

  • ソースコード中の「ビットDP基底計算」の部分が特別扱いしてるのに書いてる途中ずっと違和感があった。
  • こういう特別扱いはなるべく一般化した方がよい気がする。無理やりやろうとして間違えてしまっては本末転倒だけど。

修正判

int solve(int H, int W){

	//DPテーブルの初期化
	for(int i=0; i<=H; i++){
		for(int bit=0; bit<(1<<W); bit++){
			fill(dp[i][bit], dp[i][bit]+(1<<W), INF);
		}
	}

	//基底
	dp[0][0][0] = 0;

	//ビットDP
	for(int i=0; i<H; i++){
		for(int bit1=0; bit1<(1<<W); bit1++){ //prev row: is_center
			for(int bit2=0; bit2<(1<<W); bit2++){ //prev row: still_live
				for(int bit3=0; bit3<(1<<W); bit3++)if( bit3 == (bit3 | bit2) ){ //cur row: is_center
					int bit4 = (1<<W)-1; //cur row: still_live

					//結果誰が生き残る？
					for(int j=0; j<W; j++)if( (bit1>>j)&1 ){
						bit4 &= ~(1<<j);
					}

					for(int j=0; j<W; j++)if( (bit3>>j)&1 ){
						if(j>0){
							bit4 &= ~(1<<(j-1));
						}
						bit4 &= ~(1<<j);
						bit4 &= ~(1<<(j+1));
					}

					dp[i+1][bit3][bit4] = min(dp[i+1][bit3][bit4] , dp[i][bit1][bit2] + __builtin_popcount(bit3));
				}
			}
		}
	}

	int ans = INF;
	for(int bit=0; bit<(1<<W); bit++){
		ans = min(ans, dp[H][bit][0]);
	}

	return H*W - ans;
}