読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

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

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

問題概要

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

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

 最後に残る人の番号を求めよ。
 N \leq 5000

解法

 操作一回について考えます。移動後の位置(基準位置から何番目の人間の前にいるか)の計算は剰余をとることで O( 1 ) で可能で、人間のリスト(非データ構造的な意味で)を配列で保持していたとすれば、配列からの削除は O( N ) でできます。操作の回数は O( N ) なので、全体のシミュレートは O( N^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];
	}
};