Codeforces #176 Div1. B. Shifting

さてB。幸い本番中に解法が思いつけた問題。
http://codeforces.com/contest/286/problem/B

問題

大きさnの数列と整数値kに対し、関数fを次の様に定義する。

つまり、先頭のk要素を一つシフトし、次のk要素を一つシフトし…と処理していく。
最後kで割りきれない数の要素分は、その要素でシフトする。

ここでnが与えられたとき、

を答える。

解法

シフト処理は、全体を左にシフトしつつ、i % k == 1となる要素だけは(k-1)個右に動かさないといけない。
nは最長10^6なので、関数fを律儀に実装するとO(n^2)で時間切れする。
ここでほとんどの要素は左シフトなことを使う。

2n個の配列を用意し、fを適用するたびに開始位置を1個ずつずらすだけで左シフトを実現できる。
後はi%k==1番目の要素だけ右に動かせばよい。
すると処理量はでO(n^2)よりは小さいので何とか間に合う。

以下のコードは、2n個の配列ではなくn個のリングバッファを作って開始位置をずらしている。

int N;
int PP[1000001];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N) PP[i]=i+1;
	
	int cur=0;
	for(i=2;i<=N;i++) {
		j=0;
		k=PP[cur];
		while(j<N) {
			l=PP[(cur+j)%N];
			PP[(cur+j)%N]=k;
			k=l;
			j+=i;
		}
		PP[cur]=l;
		cur++;
	}
	FOR(j,N) {
		if(j!=N-1) _P("%d ",PP[(cur+j)%N]);
		else _P("%d\n",PP[(cur+j)%N]);
	}
	return;
}

まとめ

開始位置をずらせばいいんじゃない？というのが本番に思いつけて良かった。