kmjp's blog

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

TopCoder SRM 789 : Div1 Medium BasePlacement

こちらもしょうもなさすぎるミスした。
https://community.topcoder.com/stat?c=problem_statement&pm=16399&rd=18188

問題

R*Cのグリッドのうち、いくつかを選択したい。
その際、以下の状態は不可である。

  • 選択したセルが隣接する
  • あるセルが、2個以上の選択したセルが隣接する

条件を満たす選択の仕方で、B個以上のセルを選択しているのは何通りか。

解法

まず横幅が縦より短くなるように回転させておく。そうするとCは13以下となる。
あとは上の行から、各セルが

  • 未選択かつ隣接セルに選択マスなし
  • 未選択かつ隣接セルに選択マスが1つ
  • 選択済み

で最大(3^C)通りと、さらに選択済みのマスの数からなる各状態に対し、次の行の状態を(2^C)通り総当たりしよう。
実際には選択済みのマスは連続できないので、もう少し総当たりの総数は減る。

以下のコードでは、事前に(3^C)通りのうちあり得る状態と、次の行で取れる(2^C)通りのうち有効なものに対して、次の行の状態を列挙して高速化している。

ll from[4063][70];
ll to[4063][70];
map<int,int> T;
const ll mo=1000000007;
class BasePlacement {
	public:
	int count(int R, int C, int B) {
		if(C>R) swap(R,C);
		
		vector<int> cand;
		vector<int> state;
		int i;
		int mask;
		FOR(mask,1<<C) {
			if(mask&(mask<<1)) continue;
			if(mask&(mask<<2)) continue;
			cand.push_back(mask);
		}
		FORR(a,cand) FORR(b,cand) {
			if(a&b) continue;
			if((a<<1)&b) continue;
			if(a&(b<<1)) continue;
			int i;
			int mask2=0;
			int c=1;
			FOR(i,C) {
				if(b&(1<<i)) {
					mask2+=2*c;
				}
				else {
					int num=0;
					if(b&(2<<i)) num++;
					if(i&&(b&(1<<(i-1)))) num++;
					if(a&(1<<i)) num++;
					assert(num<=1);
					mask2+=num*c;
				}
				c*=3;
			}
			state.push_back(mask2);
		}
		
		cout<<cand.size()<<endl;
		cout<<state.size()<<endl;
		sort(ALL(state));
		state.erase(unique(ALL(state)),state.end());
		
		vector<vector<pair<int,int>>> nex;
		nex.resize(state.size());
		int j;
		T.clear();
		FOR(j,state.size()) T[state[j]]=j;
		FOR(j,state.size()) {
			int s=state[j];
			FORR(c,cand) {
				int p=1;
				int t=0,add=0;
				FOR(i,C) {
					int cur=s/p%3;
					
					if(cur==2) {
						if(c&(1<<i)) break;
						if(c&(2<<i)) break;
						if(i&&(c&(1<<(i-1)))) break;
						add+=p;
					}
					else if(cur==1) {
						if(c&(1<<i)) break;
						int num=0;
						if(c&(2<<i)) num++;
						if(i&&(c&(1<<(i-1)))) num++;
						add+=p*num;
					}
					else {
						if(c&(1<<i)) {
							add+=2*p;
							t++;
						}
						else {
							int num=0;
							if(c&(2<<i)) num++;
							if(i&&(c&(1<<(i-1)))) num++;
							add+=p*num;
						}
					}
					p=p*3;
				}
				
				if(i==C) {
					nex[j].push_back({T[add],t});
				}
			}
		}
		
		ZERO(from);
		from[T[0]][0]=1;
		int x,y;
		FOR(y,R) {
			FOR(i,state.size()) FOR(x,R*C/3+3) to[i][x]=0;
			FOR(i,state.size()) FOR(x,R*C/3+3) if(from[i][x]) {
				FORR(n,nex[i]) {
					(to[n.first][x+n.second]+=from[i][x])%=mo;
				}
			}
			swap(from,to);
		}
		
		ll ret=0;
		FOR(i,state.size()) for(j=B;j<=69;j++) ret+=from[i][j];
		return ret%mo;
		
		
	}
}

まとめ

いろいろ前処理やったおかげで1s以下で余裕で通るが、オーバースペックだったかも。