Codeforces 135 C. Zero-One

問題

0と1からなる文字列に対して二人が次のようなゲームをする。

• 手番を交互にもつ
• 手番のプレイヤーは1つ文字を消す
• 残りが2文字になったら終了
• 先手は、残る文字列を最小化し、後手は残る文字列を最大化する

ただし、与えられる文字列には'?'があり、
そこには0または1の好きな文字を当てはめてよい。

結果として残る文字列としてありうるものを全て出力せよ。

制約条件

文字列の長さ≦10^5

方針

先手は1があれば1を消すのが最善。
後手は0があれば0を消すのが最善。
0,1が複数ある場合、最も左にあるものを消すのが最善。

そして、1が0より多かったら11が、0が1より多かったら00が残る。
同数だったら、最も右に何があるかで01が残るか10が残るかが決まる。

文字列の長さが奇数の場合は、先手の手番で終了するので、
カウントが1ずれる。

ソースコード

string in;
int n,zero,one,wild;

void run()
{
	cin>>in;
	n=in.size();
	zero=one=wild=0;
	rep(i,n)if(in[i]=='0')zero++;
	else if(in[i]=='1')one++;
	else wild++;
	
	if(n%2){
		if(zero+wild>one)cout<<"00"<<endl;
		int w=(wild+one-zero-1)/2;
		if(zero+w+1==one+wild-w&&0<=w&&w<=wild){
			int p=n-1;
			bool ok=1;
			for(;p>=0;p--)if(in[p]=='1'||in[p]=='?'&&wild-w>0)break;
			else ok=0;
			if(ok)cout<<"01"<<endl;
			p=n-1;
			ok=1;
			for(;p>=0;p--)if(in[p]=='0'||in[p]=='?'&&w>0)break;
			else ok=0;
			if(ok)cout<<"10"<<endl;
		}
		if(one+wild>zero+2)cout<<"11"<<endl;
	}
	else{
		if(zero+wild>one)cout<<"00"<<endl;
		int w=(wild+one-zero)/2;
		if(zero+w==one+wild-w&&0<=w&&w<=wild){
			int p=n-1;
			bool ok=1;
			for(;p>=0;p--)if(in[p]=='1'||in[p]=='?'&&wild-w>0)break;
			else ok=0;
			if(ok)cout<<"01"<<endl;
			p=n-1;
			ok=1;
			for(;p>=0;p--)if(in[p]=='0'||in[p]=='?'&&w>0)break;
			else ok=0;
			if(ok)cout<<"10"<<endl;
		}
		if(one+wild>zero)cout<<"11"<<endl;
	}
}