読者です 読者をやめる 読者になる 読者になる

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");
}

*1:本当は修行で引いたからです……。みんなもやろう。