Google Code Jam 2008 Round 1B : C. Mousetrap

R1BのBで止まっていたので、Cも回答。
http://code.google.com/codejam/contest/32017/dashboard#s=p2

1～NのN枚のカードが並んでいるとき、M番目にMが来ていたらそれを取り除く。
M+1番目が先頭に来るように1～(M-1)番目を後ろに持って行って、また同じ処理を繰りかえす。
ということを繰り返し、N枚までが1,2,…,Nの順ですべて取り除けるように並べる問題。

基本はこの処理を逆に行えばよい。
1枚目に1を、(1+2)=3枚目に2を、(1+2+3)=6枚目に3を…と繰り返していく。
最後から来たらまた最初に繰り返し、またすでにカードを置いた位置はスキップする。

ただ、データ構造にもよるが単純にN個の配列で行うとこの処理はO(N^2)位かかる。
空き位置を求めるのに、配列を辿る必要があるから。
なので、N<=5000であるsmallだけならこれでシミュレートするだけで良い。
largeはN<=1,000,000なのでこれだとダメ。

Analysisによると解法はいくつかあるが、ここでは平方分割を行う。
空き領域を求める配列探索を１つの配列で行うとO(N)だが、1000個分の1000配列を作ればO(√N)で探せる。
作ったコードはこんな感じ。

int K;
int n,d[100];
int deck[1000001];
int np[1000];
int pos[1000][1000];

void solve(int _loop) {
	int i,j,k,m,result,cp,l,y,x,c;
	
	K=GETi();
	ZERO(deck);
	ZERO(np);
	FOR(i,K){ pos[i/1000][i%1000]=i; np[i/1000]++;}

	cp=0;
	y=x=c=0;
	FOR(i,K) {
		c = i%(K-i);
		while(1) {
			if(x+c < np[y]) {
				x +=c ;
				break;
			}
			c -= np[y]-x;
			x = 0;
			y = (y+1)%1000;
			if(y > (K+999)/1000){
				y=0;
			}
		}
		deck[pos[y][x]]=i+1;
		np[y]--;
		memmove(&pos[y][x],&pos[y][x+1],(np[y]-x)*4);
	}
	
	_PE("Case #%d:",_loop);
	n = GETi();
	FOR(i,n){ _P(" %d",deck[GETi()-1]);}
	_PE("\n");
	
	
}

まとめ

配列探索でO(N)かかる場合は、平方分割でO(√N)にすることを考えよう。