TopCoder SRM 586, Division 2, Level 1 : TeamsSelection

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12696&rd=15698

概要

N + 2 人の人がいて、内二人はキャプテンである。
二人のキャプテンは残りの N 人を二つのチームに割り振りたい。
各キャプテンは自チームに欲しい順に N 人の人をリストアップしている。
キャプテン達は交互に、最も優先度が高く、かつ未だチームに割り振られていない人を自チームに割り振る。
N 人の人について、どちらのチームに割り振らるかを求めよ。

解法

問題文の通りにシミュレーションをして解きました。

コード

typedef vector<int> VI;

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

class TeamsSelection
{
public:
	string simulate( vector <int> preference1, vector <int> preference2 )
	{
		const int N = preference1.size();

		VI picked( N, -1 );
		int pos1 = 0, pos2 = 0;
		while ( true )
		{
			while ( pos1 < N && picked[ preference1[ pos1 ] - 1 ] != -1 ) pos1++;
			if ( pos1 == N )
			{
				break;
			}
			picked[ preference1[ pos1 ] - 1 ] = 1;

			while ( pos2 < N && picked[ preference2[ pos2 ] - 1 ] != -1 ) pos2++;
			if ( pos2 == N )
			{
				break;
			}
			picked[ preference2[ pos2 ] - 1 ] = 2;
		}

		string res;
		transform( ALL( picked ), back_inserter( res ), bind1st( plus<char>(), '0' ) );
		return res;
	}
};