読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Codeforces #386 Div2 D. Green and Black Tea

Codeforces

2回連続CF Div2回だけ妙に調子がいいのなんで。
http://codeforces.com/contest/746/problem/C

問題

"B","G"の文字をそれぞれa,b個含む文字列のうち、同じ文字がK回以上連続しないものが存在すれば構築せよ。

解法

a≦bとすると、"B"をa個並べてその隙間に"G"を挟み込んでいくことになる。
"G"を入れられる領域は(a+1)なので、b≦(a+1)*Kなら条件を満たせる。

ll N,K,A,B;
string R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>A>>B;
	
	if(A==B) {
		FOR(i,N/2) R+="GB";
	}
	else if(A<B) {
		if(B>(A+1)*K) return _P("NO\n");
		FOR(i,A+1) {
			FOR(x,B/(A+1)+(i<B%(A+1))) R+="B";
			if(i<A) R+="G";
		}
		
	}
	else if(B<A) {
		if(A>(B+1)*K) return _P("NO\n");
		FOR(i,B+1) {
			FOR(x,A/(B+1)+(i<A%(B+1))) R+="G";
			if(i<B) R+="B";
		}
	}
	cout<<R<<endl;
}

まとめ

今回点数がいつもより大きめ?

広告を非表示にする