kmjp's blog

競技プログラミング参加記です

TopCoder SRM 671 Div1 Hard BearDestroys

本番考え方はあってたけど、あと1時間ないと間に合わなかった。
http://community.topcoder.com/stat?c=problem_statement&pm=14069

問題

問題設定はDiv2 Hardと同じ。
TopCoder SRM 671 Div2 Hard BearDestroysDiv2 - kmjp's blog

ただしこちらはWの上限が30と大きく、Hの上限は13と小さ目。

解法

こちらWが大きいためDiv2の解法は使えない。
Hは小さいので列単位でDPすればよいのでは?と思うが、各マスが右に倒せるかどうかは右上のマスの木が下に倒れるかどうかに依存するため、列単位のDPは出来ない。
ただ、考え方を変えると各マス高々1個右上のマスの状態で右に倒せるか決められるので、斜めにDPしていけば良いことがわかる。
左上のセルの座標を(0,0)、右下を(W-1,H-1)とすると、i回目DPではr+c=(i-1)であるような座標(r,c)のマス群に対してbitDPをしていけば良い。

こうすると1回のDPで処理するマスは2^min(H,W)になり、Wが大きくてもHが小さいので安心である。
ただ、(H<Wとして)Div2 HardのDPを行単位ではなく斜めにしただけだと、まだO((W*H)^2*4^H)かかり今回のHの上限では間に合わない。
そこで4^Hかかる部分を削減することを考える。

Div2Hardでは、各マスにすでに倒れてきている木があるかどうかで2通り、かつ各マスが右下どちらに倒れやすいかで2通り考えたため、1マスあたり4通りの状態を考える必要があった。
しかし以下の2つの考え方を用いて枝刈りすると、マスの状態を平均2~3の間にすることができる。

  • マスにすでに倒れてきている木がある場合、そこのマスの木が右下どちらに倒れやすくても倒せないことに代わりがないので、まとめて考える。
    • こうするとマスの状態は「すでに倒れてきている木がある」「左記木が無く、右に倒れやすい」「左記木が無く、下に倒れやすい」の3通りと考えられる。
  • 右と下どちらか片方にしか倒せない場合、そこのマスの木が右下どちらに倒れやすくても倒せる方向は一意に決まる。

上記状態のまとめこみをすることによって、O((W*H)^2*α^H) (αは2と3の間)程度に落とし込める。
下記コードでは、各状態に置いて倒せる木の数のバリエーションは多くないことを用いてもう少し処理を削減している。
これで1.2s程度で通る。

ll mo;
ll from[200][1<<13];
ll to[200][1<<13];
vector<int> fp[1<<13];

class BearDestroys {
	int od,R,B,T;
	public:
	
	void dfs(int y,int tmask,int fmask,int pat,int fall) {
		int i;
		if(y>B) {
			FORR(r,fp[tmask]) (to[r+fall][fmask] += from[r][tmask]<<pat)%=mo;
			return;
		}
		
		// used
		dfs(y+1,tmask,fmask,pat+1,fall);
		// unused
		if((fmask&(1<<y)) && (fmask&(1<<(y+1)))) {
			dfs(y+1,tmask + (1<<y),fmask^(1<<y),pat,fall+1);
			dfs(y+1,tmask + (1<<y),fmask^(2<<y),pat,fall+1);
		}
		else if(fmask&(1<<y)) {
			dfs(y+1,tmask+ (1<<y),fmask^(1<<y),pat+1,fall+1);
		}
		else if(fmask&(2<<y)) {
			dfs(y+1,tmask+ (1<<y),fmask^(2<<y),pat+1,fall+1);
		}
		else {
			dfs(y+1,tmask+ (1<<y),fmask,pat+1,fall);
		}
		
	}
	
	int sumUp(int W, int H, int MOD) {
		mo=MOD;
		int i,j,k;
		
		ZERO(from);
		from[0][1]=1;
		
		for(od=0;od<=(W-1+H-1);od++) {
			FOR(j,1<<H) {
				FORR(r,fp[j]) to[r][j]=0;
				fp[j].clear();
				FOR(i,200) if(from[i][j]) fp[j].push_back(i);
			}
			
			R=min(od,W-1);
			B=min(od,H-1);
			T=od-R;
			int fmask=0,y;
			FOR(y,H) {
				int x=od-y+1;
				if(x>=0 && x<W) fmask |= 1<<y;
			}
			dfs(T,0,fmask,0,0);
			swap(from,to);
		}
		
		ll ret=0;
		FOR(i,200) ret+=i*from[i][0]%mo;
		return ret%mo;
	}
}

まとめ

本番通したかったな。