Codeforces #177, Division 2, C : Polo the Penguin and Strings

問題文

http://codeforces.com/contest/289/problem/C

概要

次の条件を満たす文字列のうち、辞書順最小のものを出力せよ。

• 文字列は、n 文字の英小文字からなる
• ちょうど k 種類の文字を含む
• 隣り合う文字同士は全て相異なる

そのような文字列が存在しない場合は -1 で示せ。

解法

n < k のとき、長さが足りないので解はありません。
それ以外の場合は解が存在します。

解を求めるには、辞書順最小のセオリー通り先頭から Greedy に決めていきます。
できるだけ小さい文字を先に使いたいので、ab の繰り返しで文字数を調整したあと、残りの文字を埋めればできます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	if ( n < k || 2 <= n && k == 1 )
	{
		cout << -1 << endl;
		return 0;
	}

	if ( n == 1 && k == 1 )
	{
		cout << 'a' << endl;
		return 0;
	}

	string ab( "ab" ), res;
	REP( i, 0, n - ( k - 2 ) )
	{
		res += ab[ i % 2 ];
	}
	REP( i, 2, k )
	{
		res += 'a' + i;
	}
	cout << res << endl;

	return 0;
}