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

kmjp's blog

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

Codeforces #177 Div1. A. Polo the Penguin and Strings

あまりここに書いてないけど、Codeforcesもちょくちょく出てます。
この回は珍しくBとCを解いたけど、全体の難易度が低かったのかイマイチな順位だった。
http://codeforces.com/contest/288/problem/A

問題

文字列長Nと文字種別数Kが与えられるとき、以下の条件を満たす文字列を答えよ。

  • K種類アルファベットの小文字のみで構成されるN文字の文字列
  • 隣同士の文字が一致しない
  • 上記条件を満たす中で辞書順で最初の文字

条件を満たす文字列が存在しない場合は-1を返せ。

解法

K>Nならそんな文字列は存在しない。
K=1の時は、N=1なら"a"が答えで、N>1なら存在しない。
K>=2の時、最後のK-2文字はcdefg...となり、その手前はababab...とabを繰り返せばよい。

int N,K;
void solve() {
	int f,r,i,j,k,l,x,y;
	
	GET2(&N,&K);
	
	if(K>N) {
		_P("-1\n");
		return;
	}
	
	if(K==1) {
		if(N>1) _P("-1\n");
		else _P("a\n");
		return;
	}
	else if(K==2) {
		FOR(i,N) _P("%c",'a'+(i%2));
		_P("\n");
		return;
	}
	
	if((N-K)%2==0) {
		FOR(i,(N-K)/2) _P("ab");
		FOR(i,K) _P("%c",'a'+i);
		_P("\n");
	}
	else {
		FOR(i,(N-K+2)/2) _P("ab");
		_P("a");
		FOR(i,K-2) _P("%c",'c'+i);
		_P("\n");
	}
	
	return;
}

まとめ

地味に場合分けが多くて、本番はPretest通ったのにHackされた…。

広告を非表示にする