SRM 619 DIV2 Middle - ChooseTheBestOne (×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13146
・N人が円になって並んでいる。
・そこから各ターンｔごとにｔ＾３番目にいる人を消し、その次の人へ移動する。
・このとき、最後に残る人の番号を求める。
解き方
・各ターンごとに移動する数は、そのターンで残っている人でMODを取れば計算量が間に合うので、あとはメモ化すれば解くことができる。
・MOD関連でシステムで一度落ちてしまったので、できるだけ実装はシンプルに。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ChooseTheBestOne {
public: int countNumber(int N) {
int dp[N];
memset(dp,0,sizeof(dp));
int s=0;
for(long long t=1;t<N;t++){
while(dp[s])s=(s+1)%N;
long long num=N-t+1;
int move=(((t*t*t)%num)+num-1)%num;
FORE(i,0,move){
s=(s+1)%N;
while(dp[s])s=(s+1)%N;
}
dp[s]=t;
}
FORE(i,0,N)if(dp[i]==0)return i+1;
return -1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ChooseTheBestOne {
public: int countNumber(int N) {
int dp[N];
memset(dp,0,sizeof(dp));
int s=0;
for(long long t=1;t<N;t++){
while(dp[s])s=(s+1)%N;
long long num=N-t+1;
int move=(((t*t*t)%num)+num-1)%num;
FORE(i,0,move){
s=(s+1)%N;
while(dp[s])s=(s+1)%N;
}
dp[s]=t;
}
FORE(i,0,N)if(dp[i]==0)return i+1;
return -1;
}
};
