Codeforces #1014 : Div2 D. Mishkin Energizer

遅参したので全完できずともやむなしか。
https://codeforces.com/contest/2092/problem/D

問題

T,L,Iで構成される文字列Sが与えられる。
この時、S[i]!=S[i+1]となる箇所があった場合、S[i]とS[i+1]の間に、S[i]ともS[i+1]とも異なる文字を入れられる。

S中のT,L,Iの頻度が同じになるようにできるか。できるならその位置を順に示せ。

解法

初期状態で1種類の文字しかない場合、条件を満たすことができない。
それ以外の場合、まず頻度が最大でない文字を挿入できそうなところがある限りはそれを追加しよう。
そうでない場合、しょうがないので頻度が最大の文字をどこか１箇所追加する。

int T,N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		int C[3]={};
		FORR(c,S) {
			if(c=='T') c=0;
			if(c=='L') c=1;
			if(c=='I') c=2;
			C[c]++;
		}
		if(C[0]==N||C[1]==N||C[2]==N) {
			cout<<-1<<endl;
			continue;
		}
		
		vector<int> V;
		while(1) {
			int C[3]={};
			FOR(i,N) C[S[i]]++;
			if(C[0]==C[1]&&C[1]==C[2]) break;
			int ma=max({C[0],C[1],C[2]});
			FOR(i,N-1) if(S[i]!=S[i+1]&&C[3-S[i]-S[i+1]]<ma) {
				V.push_back(i+1);
				S.insert(i+1,1,3-S[i]-S[i+1]);
				N++;
				break;
			}
			if(i==N-1) {
				FOR(i,N-1) if(S[i]!=S[i+1]) {
					V.push_back(i+1);
					S.insert(i+1,1,3-S[i]-S[i+1]);
					N++;
					break;
				}
			}
		}
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<endl;
	}
}

まとめ

適当にどん欲しても割と通る気がする。