TopCoder, SRM 619, Division 2, Level 2 : ChooseTheBestOne

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13146&rd=15852

問題概要

　N 人の人がいて、1 から N に番号付けられている。N 人の人を円周上に並べ、Shiny が 1 番の人の前に立つ。その後、次の操作を N - 1 回適用する。

1. t 回目の操作では、t^3 - 1 人分だけ時計回りに移動する
2. 目の前にいる人間を除外し、時計回りで次の人の前に立つ

　最後に残る人の番号を求めよ。
　

解法

　操作一回について考えます。移動後の位置（基準位置から何番目の人間の前にいるか）の計算は剰余をとることで で可能で、人間のリスト（非データ構造的な意味で）を配列で保持していたとすれば、配列からの削除は でできます。操作の回数は なので、全体のシミュレートは で走ります。N の制約があまり大きくないので、この方法で問題を解くことができます。

コード

using LL = long long;
using VI = vector<int>;

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

class ChooseTheBestOne
{
public:
	int countNumber( int N )
	{
		VI employees( N );
		iota( ALL( employees ), 1 );

		LL pos = 0;
		REP( t, 1, N )
		{
			( pos += (LL)t * t * t - 1 ) %= employees.size();
			employees.erase( employees.begin() + pos );
		}
		return employees[0];
	}
};