torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #170, Division 2, B : New Problem

概要

英小文字からなる n 個の文字列が与えられる。
これらの文字列の部分文字列でないような最短の文字列を求めよ。
答えが複数存在する場合は辞書式順序で最小となるものを出力せよ。

解法

制約より、与えられる文字列の長さは高々 600 文字です。
これに対し、英小文字二文字からなる文字列は 26 \times 26 = 676 通りあります。
つまり、与えられた文字列では二文字の列を網羅できません。
従って、答えは高々二文字となるので全探索が可能です。

コード

typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

string solve1( VS titles )
{
	set<char> chars;
	FOR( t, titles )
	{
		chars.insert( ALL( t ) );
	}
	
	for ( char c = 'a'; c <= 'z'; c++ )
	{
		if ( !EXIST( chars, c ) )
		{
			return string() + c;
		}
	}

	return "";
}

string solve2( VS titles )
{
	set<string> substrs;
	FOR( t, titles )
	{
		REP( i, 0, t.size() - 1 )
		{
			substrs.insert( t.substr( i, 2 ) );
		}
	}

	for ( char c1 = 'a'; c1 <= 'z'; c1++ )
	{
		for ( char c2 = 'a'; c2 <= 'z'; c2++ )
		{
			if ( !EXIST( substrs, string() + c1 + c2 ) )
			{
				return string() + c1 + c2;
			}
		}
	}

	return "";
}

string solve( VS titles )
{
	string res = solve1( titles );
	
	if ( res != "" )
	{
		return res;
	}

	return solve2( titles );
}

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

	int n;
	cin >> n;

	VS titles( n );
	FOR( t, titles )
	{
		cin >> t;
	}

	cout << solve( titles ) << endl;

	return 0;
}