torus711 のアレ

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

Codeforces #270, C : Design Tutorial: Make It Nondeterministic

問題概要

 n 要素の文字列配列 f, s と、サイズ n の順列 p が与えられる。
 各 i について f_{p_i} または s_{p_i} のいずれかを選んで h_i としたとき、h を辞書式順序に於いて単調増加にすることができるか否か、求めよ。
 なお、与えられる文字列は相異なる。

解法

 可能な選択の内、できるだけ小さい文字列を選び続けるのが最適な戦略です。そのように選択したとき、途中で選択することができなくなってしまった場合は不可能であると分かります。

コード

using VI = vector<int>;
using VS = vector<string>;

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

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

	int n;
	cin >> n;

	VS fs( n ), ls( n );
	REP( i, 0, n )
	{
		cin >> fs[i] >> ls[i];
		if ( fs[i] > ls[i] )
		{
			swap( fs[i], ls[i] );
		}
	}

	VI ps( n );
	copy_n( istream_iterator<int>( cin ), n, ps.begin() );
	transform( ALL( ps ), ps.begin(), bind( minus<int>(), _1, 1 ) );

	string now = "";
	FOR( p, ps )
	{
		if ( now < fs[p] )
		{
			now = fs[p];
		}
		else if ( now < ls[p] )
		{
			now = ls[p];
		}
		else
		{
			cout << "NO" << endl;
			return 0;
		}
	}

	cout << "YES" << endl;

	return 0;
}