kmjp's blog

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

TopCoder SRM 534 Div2 Hard EllysFiveFriends

あれ、これはさほど難しくないけど本番正答率0%だ。
http://community.topcoder.com/stat?c=problem_statement&pm=11522

問題

5つの自然数がリング状に並んでいる。

隣接する0でない2つの数値を選び、以下のいずれかを処理を行うことができる。

  • 両方を2で割る。小数点以下は切りすてる。
  • 両方が奇数なら両方から1を引く。

5つの数値が与えられたとき、全部の数値を0にするまでに行う処理の組み合わせを求めよ。

解法

1つの数値は、2進数表記したときの最大桁数回2で割ることができ、また1のbit回数分だけ1を引くことができる。
各数値の上限は10000であり、そのうち最大でも8191の時に25回までしか処理ができない。

よって、各数値の状態は26通りにしか遷移しない。
後は26^5通りの状態に対しDPで遷移の数を数え上げるだけ。
26^5は12M位なので何とか終わる。ただし、数は32bitにしておかないとメモリがあふれるので注意。

int mo=1000000007;
const int NN=27;
int dp[NN][NN][NN][NN][NN];

class EllysFiveFriends {
	public:
	vector<int> V[5];
	vector<int> Podd[5];
	vector<int> Pdiv[5];
	
	void enumnum(int ind,int val) {
		int vis[10001],i;
		ZERO(vis);
		vis[val]=1;
		V[ind].clear();
		
		for(int i=val;i>=0;i--) {
			if(!vis[i]) continue;
			V[ind].push_back(i);
			if(i%2) vis[i-1]=1;
			vis[i/2]=1;
		}
		sort(V[ind].begin(),V[ind].end());
		
		Podd[ind].clear();
		Pdiv[ind].clear();
		map<int,int> rev;
		FOR(i,V[ind].size()) {
			rev[V[ind][i]]=i;
			if((V[ind][i]%2)==0) Podd[ind].push_back(-1);
			else Podd[ind].push_back(rev[V[ind][i]-1]);
			Pdiv[ind].push_back(rev[V[ind][i]/2]);
		}
		
	}
	
	int getZero(vector <int> numbers) {
		int i,a,b,c,d,e,I[5];
		FOR(i,5) enumnum(i,numbers[i]);
		
		ZERO(dp);
		dp[V[0].size()-1][V[1].size()-1][V[2].size()-1][V[3].size()-1][V[4].size()-1]=1;
		for(I[0]=V[0].size()-1;I[0]>=0;I[0]--) for(I[1]=V[1].size()-1;I[1]>=0;I[1]--)
		for(I[2]=V[2].size()-1;I[2]>=0;I[2]--) for(I[3]=V[3].size()-1;I[3]>=0;I[3]--) {
			for(I[4]=V[4].size()-1;I[4]>=0;I[4]--) {
				int hoge=dp[I[0]][I[1]][I[2]][I[3]][I[4]];
				if(hoge==0) continue;
				if(I[0]&&I[1]) dp[Pdiv[0][I[0]]][Pdiv[1][I[1]]][I[2]][I[3]][I[4]] += hoge, dp[Pdiv[0][I[0]]][Pdiv[1][I[1]]][I[2]][I[3]][I[4]] %= mo;
				if(I[1]&&I[2]) dp[I[0]][Pdiv[1][I[1]]][Pdiv[2][I[2]]][I[3]][I[4]] += hoge, dp[I[0]][Pdiv[1][I[1]]][Pdiv[2][I[2]]][I[3]][I[4]] %= mo;
				if(I[2]&&I[3]) dp[I[0]][I[1]][Pdiv[2][I[2]]][Pdiv[3][I[3]]][I[4]] += hoge, dp[I[0]][I[1]][Pdiv[2][I[2]]][Pdiv[3][I[3]]][I[4]] %= mo;
				if(I[3]&&I[4]) dp[I[0]][I[1]][I[2]][Pdiv[3][I[3]]][Pdiv[4][I[4]]] += hoge, dp[I[0]][I[1]][I[2]][Pdiv[3][I[3]]][Pdiv[4][I[4]]] %= mo;
				if(I[4]&&I[0]) dp[Pdiv[0][I[0]]][I[1]][I[2]][I[3]][Pdiv[4][I[4]]] += hoge, dp[Pdiv[0][I[0]]][I[1]][I[2]][I[3]][Pdiv[4][I[4]]] %= mo;
				if(Podd[0][I[0]]!=-1 && Podd[1][I[1]]!=-1) dp[Podd[0][I[0]]][Podd[1][I[1]]][I[2]][I[3]][I[4]] += hoge, dp[Podd[0][I[0]]][Podd[1][I[1]]][I[2]][I[3]][I[4]] %= mo;
				if(Podd[1][I[1]]!=-1 && Podd[2][I[2]]!=-1) dp[I[0]][Podd[1][I[1]]][Podd[2][I[2]]][I[3]][I[4]] += hoge, dp[I[0]][Podd[1][I[1]]][Podd[2][I[2]]][I[3]][I[4]] %= mo;
				if(Podd[2][I[2]]!=-1 && Podd[3][I[3]]!=-1) dp[I[0]][I[1]][Podd[2][I[2]]][Podd[3][I[3]]][I[4]] += hoge, dp[I[0]][I[1]][Podd[2][I[2]]][Podd[3][I[3]]][I[4]] %= mo;
				if(Podd[3][I[3]]!=-1 && Podd[4][I[4]]!=-1) dp[I[0]][I[1]][I[2]][Podd[3][I[3]]][Podd[4][I[4]]] += hoge, dp[I[0]][I[1]][I[2]][Podd[3][I[3]]][Podd[4][I[4]]] %= mo;
				if(Podd[4][I[4]]!=-1 && Podd[0][I[0]]!=-1) dp[Podd[0][I[0]]][I[1]][I[2]][I[3]][Podd[4][I[4]]] += hoge, dp[Podd[0][I[0]]][I[1]][I[2]][I[3]][Podd[4][I[4]]] %= mo;
			}
		}
		
		return dp[0][0][0][0][0];
	}
};

まとめ

コピペだらけであまり美しくないな…。