TopCoder SRM 619 Div2 Medium ChooseTheBestOne

Div2とはいえMediumにしては安易？
http://community.topcoder.com/stat?c=problem_statement&pm=13146

問題

初期状態で1～N番の人が円形に進んでいる。
ここで代表者が(N-1)人を取り除いて優勝者1名を残す。
そのアルゴリズムは以下の通りである。

代表者の初期位置は1番の人である。
そこからkターン目にはそこからk^3番目にいる人を取り除く、ということを繰り返す。
最終的な優勝者は誰か。

解法

そのままシミュレートすれば問題ない。
vectorのデータの取り除きにO(N)かかり、(N-1)回取り除くので全体のオーダーはO(N^2)だが、N ≤ 5000なので問題ない。
k^3でオーバーフローしないように注意。

class ChooseTheBestOne {
	public:
	int countNumber(int N) {
		vector<int> V;
		ll i;
		
		FOR(i,N) V.push_back(i+1);
		ll j=0;
		FOR(i,N-1) {
			j+=((i+1)*(i+1)*(i+1)-1);
			j%=V.size();
			V.erase(V.begin()+j);
			j%=V.size();
		}
		return V[0];
	}
}

まとめ

なんかあまりヒネリを感じない問題…。