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

kmjp's blog

競技プログラミング参加記です

Codeforces #176 Div1. B. Shifting

Codeforces

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

問題

大きさnの数列P=p_1, p_2, ... , p_nと整数値kに対し、関数fを次の様に定義する。
f(p,k)=\overbrace{p_2,p_3,...p_k,p_1}, \overbrace{p_{k+2},p_{k+3},...,p_{2k},p_{k+1}}, ...,\overbrace{p_{rk+2},p_{rk+3},...,p_{n},p{rk+1}}
つまり、先頭のk要素を一つシフトし、次のk要素を一つシフトし…と処理していく。
最後kで割りきれない数の要素分は、その要素でシフトする。

ここでnが与えられたとき、
f(...f(f([ 1,2,...,n],2),3)...,n)
を答える。

解法

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

2n個の配列を用意し、fを適用するたびに開始位置を1個ずつずらすだけで左シフトを実現できる。
後はi%k==1番目の要素だけ右に動かせばよい。
すると処理量は\sum_{i=2}^n \lceil \frac{n}{i} \rceilで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;
}

まとめ

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

広告を非表示にする