kmjp's blog

競技プログラミング参加記です

AIM Tech Round 3 : Div1 B. Recover the String

このミスは痛い。
http://codeforces.com/contest/708/problem/B

問題

01で構成された文字列Sがある。
このSの2文字を取ったとき、i,jの順で2文字が登場する数A[i][j]が与えられる。

ここから可能なら元のSを復元せよ。

解法

最初に0,1の数B[0],B[1]を求めよう。
0と1の対応関係はおいておいて、 {}_{B_0} C_2 = A_{00}, {}_{B_1} C_2 = A_{11}からB[0],B[1]がわかる。

また、B[0]*B[1]==A[0][1]+A[1][0]であることを確認しよう・
ここで注意点として、A[0][0]やA[1][1]が0の時、B[0]やB[1]は0の場合と1の場合がある点に注意。
そこはB[0]*B[1]==A[0][1]+A[1][0]を満たすようそれぞれ選択しよう。

あとは0をB[0]個並べた後、1のあと0が出てくる数がA[1][0]回になるように1をB[1]個並べていくだけ。

ll A[2][2];
ll n0,n1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0][0]>>A[0][1]>>A[1][0]>>A[1][1];
	while(n0*(n0-1)/2<A[0][0]) n0++;
	while(n1*(n1-1)/2<A[1][1]) n1++;
	if(n0*(n0-1)/2!=A[0][0]) return _P("Impossible\n");
	if(n1*(n1-1)/2!=A[1][1]) return _P("Impossible\n");
	if(n0==0 && A[0][1]+A[1][0]) n0=1;
	if(n1==0 && A[0][1]+A[1][0]) n1=1;
	
	if(n0*n1 != A[0][1]+A[1][0]) return _P("Impossible\n");
	if(n0==0 && n1==0) return _P("0\n");
	if(n0==0 || n1==0) {
		FOR(i,max(n0,n1)) _P("%d",n0==0);
		_P("\n");
		return;
	}
	int post=A[0][1]/n0;
	int pre=n1-post;
	A[0][1] -= post*n0;
	string S=string(pre,'1')+string(n0,'0')+string(post,'1');
	FOR(i,S.size()) {
		if(S[i]=='0') {
			while(A[0][1]) {
				A[0][1]--;
				swap(S[i-1],S[i]);
				i++;
			}
			break;
		}
	}
	
	cout<<S<<endl;
	
}

まとめ

まぁ自分はその注意点を見落としてWAしたんだけどね…。

広告を非表示にする