あれ、これはさほど難しくないけど本番正答率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]; } };
まとめ
コピペだらけであまり美しくないな…。