AOJ 2633: Cellular Automaton
解説の記憶が薄れる前に解いておこうということで。*1
・2w+1ビットを一つの頂点として、右に0か1を付け足したときに0,1の総数がどうなるかを計算して辺をはる。辺のコスト(1を付け足すと1がひとつ供給される)と頂点のコスト(オートマトンが1を吐くと1がひとつ消費される)を分けないといけない。↓で'?'があり、これのせいで0か1か未定みたいなところが出てくるので、以上と以下で別々に辺を張って牛ゲーに持ち込む。
・辞書順最小は思ったより複雑。右から'?'にしていき条件を満たしたら左から0,1をきめていく。結構いろいろ考えてみる必要があり説明する気が起きないので、ソース見てください。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int n; char in[1000]; char ret[1000]; int dist[1000]; bool check(){ vector<pair<pair<int,int>,int> >edge; for(int i=0;i<(1<<(2*n+1));i++){ int L,R,to; L=0;R=0;to=i/2; if(ret[i]=='?'){ L--; }else if(ret[i]=='1'){ L--;R--; } edge.push_back(make_pair(make_pair(i*2+1,i*2),R)); edge.push_back(make_pair(make_pair(i*2,i*2+1),-L)); edge.push_back(make_pair(make_pair(i*2,to*2+1),0)); edge.push_back(make_pair(make_pair(to*2+1,i*2),0)); L=0;R=0;to=i/2+(1<<(2*n)); if(ret[i]=='?'){ L--; }else if(ret[i]=='1'){ L--;R--; } edge.push_back(make_pair(make_pair(i*2,to*2+1),1)); edge.push_back(make_pair(make_pair(to*2+1,i*2),-1)); } for(int i=0;i<(1<<(2*n+2));i++)dist[i]=999999999; dist[0]=0; for(int i=0;i<=(1<<(2*n+2));i++){ for(int j=0;j<edge.size();j++){ if(dist[edge[j].first.first]+edge[j].second<dist[edge[j].first.second]){ dist[edge[j].first.second]=dist[edge[j].first.first]+edge[j].second; if(i==(1<<(n*2+2)))return false; } } } return true; } int main(){ int a;scanf("%d",&a); n=a; scanf("%s",in); for(int i=0;i<(1<<(2*a+1));i++)ret[i]=in[i]; if(check()){ printf("%s\n",ret);return 0; } for(int i=(1<<(2*a+1))-1;i>=0;i--){ ret[i]='?'; if(in[i]=='0'){ ret[i]='1'; if(check()){ for(int j=i+1;j<(1<<(2*a+1));j++){ ret[j]='0'; // printf("%s\n",ret); if(!check())ret[j]='1'; } printf("%s\n",ret);return 0; } ret[i]='?'; } } printf("no\n"); }