Codeforces #1075 : Div2. D2. Little String (Hard Version)

途中で抜けてしまった回。
https://codeforces.com/contest/2189/problem/D2

問題

0/1/?で構成されたN文字の文字列Sが与えられる。
0～N-1のPermutation Pに対し、

• S[i]=0なら、Pの連続部分列のうちmexがiとなるものは存在しない
• S[i]=1なら、Pの連続部分列のうちmexがiとなるものは存在する

Sの"?"には0/1を任意で入れられる場合、条件を満たすPを最小化しそのうえでCで割れない最小値を求めよ。

解法

P中で0～(K-1)までの位置が決まっているとき、Kをどこに入れるか考えると

• S[K]=1となるのは、Kが両端のどちらかにあるとき
• S[K]=0となるのは、それ以外(K-1)通り

よって、Sが定まると対応するPはS[K]の値により2または(K-1)を掛けたものになる。
あとはこれがCの倍数とならないようにする。
極力結果を小さくしたいので2を選ぶが、2を選びすぎてCの倍数になってしまうなら、(K-1)のうち小さい奇数を残す。

int T,N,C;
string S;
const ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C>>S;
		if(S[0]=='0'||S[N-1]=='0') {
			cout<<-1<<endl;
			continue;
		}
		S[0]='1';
		S[N-1]='1';
		//小さい方がいい
		if(S[1]=='?') S[1]='0';
		int lef=0;
		vector<int> odd;
		for(i=1;i<N;i++) {
			if(S[i]=='0') {
				C/=__gcd(i,C);
			}
			else if(S[i]=='1') {
				C/=__gcd(2,C);
			}
			else {
				lef++;
				if(i%2) odd.push_back(i);
				
			}
		}
		
		
		if((C&(C-1))==0) {
			//2の累乗の場合、奇数を取るようにする
			x=0;
			while(1<<x<C) x++;
			FORR(a,odd) if(lef>=x) {
				lef--;
				S[a]='0';
			}
			if(lef>=x) {
				cout<<-1<<endl;
				continue;
			}
		}
		
		ll ret=1;
		for(i=1;i<N;i++) {
			if(S[i]=='0') ret=ret*i%mo;
			else ret=ret*2%mo;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

C周りの設定、なんか無理やり付けた感じがするな…。