Codeforces #715 Div1 : A. Binary Literature

ダメダメだった回。
https://codeforces.com/contest/1508/problem/A

問題

01で構成される2N文字の文字列が3つ与えられる。
これら3つのうち、2つ以上を(不連続でもよい)部分文字列として含む長さ3Nの文字列を答えよ。

解法

3つの文字列のうち、0または1の登場頻度が共通してN個以上であるような2つの文字列を選ぼう。
例えば0の登場頻度がN以上の文字列を2つ選んだとする。
その場合、両者のうち0の登場頻度の多い方をm個とすると、解としてはm個の0を置いた後、両文字列を部分文字列として含むよう1を間に挟んでいけばよい。
この時文字列長は3N以下になる。

int T;
int N;
string S[3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int C[3][2]={};
		FOR(i,3) {
			cin>>S[i];
			FORR(c,S[i]) C[i][c-'0']++;
		}
		
		
		string R;
		FOR(y,3) FOR(x,y) FOR(j,2) if(R=="" && C[x][j]>=N&&C[y][j]>=N) {
			vector<int> A,B;
			A.push_back(0);
			B.push_back(0);
			FORR(c,S[x]) {
				if(c=='0'+j) A.push_back(0);
				else A.back()++;
			}
			FORR(c,S[y]) {
				if(c=='0'+j) B.push_back(0);
				else B.back()++;
			}
			i=max(A.size(),B.size());
			A.resize(i);
			B.resize(i);
			R="";
			FOR(i,A.size()) {
				A[i]=max(A[i],B[i]);
				R+=string(A[i],'1'^j);
				if(i!=A.size()-1) R+='0'^j;
			}
		}
		
		cout<<R<<endl;
		
		
		
		
	}
}

まとめ

以前似たようなAGCの1問目で躓いたの思い出しちゃったな…。