概要
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; } };