TopCoder SRM 672 Div1 Easy Procrastination

結構苦戦した。
http://community.topcoder.com/stat?c=problem_statement&pm=14072

問題

1から順に番号の振られた無限の人数の社員がいる。
初期状態でi番の社員は作業iを行っている。

時刻h(h≧2)において、社員番号xがhより大きくかつhの倍数である場合、社員番号x+1の人と手持ちの作業を交換する。
社員番号xの人の作業は、時刻x以降には交換が生じない安定状態に入るのは明らかであろう。

ここで、社員番号nの社員が安定状態で持っている作業の番号を求めよ。

解法

問題の条件より、社員番号xが素数の人はx+1の人と交換することはない。
よって、社員番号nの人が持つ作業は、n未満の最大の素数から、n以上の最小の素数の間であることが明らかである。
そこでその範囲だけに対し、問題分の処理をそのままシミュレートすればよい。
以下では、厳密にnの前後の素数を求めず、大ざっぱに[L,R]=[n-400,n+400]の範囲だけを探索している。
10^10以下の数値では、素数の間隔は400未満なのでこれで十分である。

hが小さい範囲、具体的には√n程度まではhを順にインクリメントしていけば良い。
hが800を超えだすと、hに対して[L,R]内で１回も作業の交換が生じないケースが生じる。
その際は[L,R]内で作業が生じるようなhを選んでいこう。

具体的には次のようにすると良い。

• 今あるhを処理したので、次に[L,R]内で作業が生じるようなhを求めたい。
  • floor(L/(h+1))!=floor(R/(h+1))なら、hをインクリメントしたもので良い。
  • そうでない場合、h=floor(L/floor(L/(h+1))でhを増やすと、次にfloor(L/(h+1))!=floor(R/(h+1))となる可能性のあるhまでジャンプできる。

別解法として、[L,R]の範囲の数値における約数を列挙し、小さい順にhの候補として処理をしていっても良い。

class Procrastination {
	public:
	
	long long findFinalAssignee(long long n) {
		ll dp[1000]={};
		ll L=n-400, R=n+400;
		int i;
		
		FOR(i,805) dp[i]=L+i;
		
		for(ll h=2;2*h<=n;) {
			for(ll v=max(2*h,(L+(h-1))/h*h);v<=R;v+=h) swap(dp[v-L],dp[v-L+1]);
			if(h<1000000 || L/(h+1) != R/(h+1)) h++;
			else h=L/(L/(h+1));
		}
		
		return dp[n-L];
	}
}

まとめ

何気にこの問題で難しいの、問題名の日本語訳だよなぁ。こんな単語初めて見た。