kmjp's blog

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

Codeforces #276 Div1 C. Strange Sorting

CのはずがDよりずっと正答者が少ない。
http://codeforces.com/contest/484/problem/C

問題

文字列Sのd-sortingとは以下のようなソートである。
文字列Sの(0-indexで数えた)各文字位置のうち、dで割った余りが0になる位置の文字群を先頭に持ってくる。
同様に、その後ろに余りが1,2,...,(d-1)となる文字群を後ろに連結していく。

長さNの文字列Sに対し、M回分のシャッフルのパラメータk[i],d[i]が与えられるので、順次シャッフル後のSを答えよ。

パラメータk,dに対するシャッフルとは、

  • Sの部分文字列S[0...k-1]に対しd-sortingする
  • Sの部分文字列S[1...k]に対しd-sortingする
  • Sの部分文字列S[2...k+1]に対しd-sortingする

  • Sの部分文字列S[N-k...N-1]に対しd-sortingする

を順次行うことを示す。

解法

個々のシャッフルを順次行っていけば良い。
シャッフル過程では、1ずつ位置をずらした部分文字列に対しd-sortingを行っている。
これを以下のように考えればよい。

Pを先頭K文字のd-sorting、Lを1文字左回転とすると、求めるシャッフルはSに変換P*L*P*L*...*P*L*(L^(k-1))を適用したものと言える。
(最後の(L^(k-1))は、そこまで(L-k+1)回左回転したのをもとに戻す効果がある。)

ここでP*L*P*L*...*P*L=(P*L)^(L-k-1)なので、これはダブリングを使えば(L-k-1)回変換を適用することなくlog(L-k-1)回で済み計算量が落とせる。

string S;
int L,M;
int LS[1<<20];
int P[2][1<<20],Q[1<<20],R[1<<20];

void makeQ(int v) {
	int i,j,k;
	FOR(i,L) Q[i]=i;
	FOR(j,20) {
		int cur=j%2,tar=cur^1;
		if(v&(1<<j)) {
			FOR(i,L) R[i]=Q[P[cur][i]];
			FOR(i,L) Q[i]=R[i];
			v ^= (1<<j);
			if(v==0) return;
		}
		FOR(i,L) P[tar][i]=P[cur][P[cur][i]];
	}
}

void solve() {
	int i,j,k,d,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	FOR(i,L) LS[i]=(i+(L-1))%L;
	
	cin>>M;
	while(M--) {
		cin>>k>>d;
		
		x=0;
		FOR(i,d) for(j=i;j<k;j+=d) P[0][j]=((x++)+(L-1))%L;
		for(i=k;i<L;i++) P[0][i]=(i+(L-1))%L;
		
		makeQ(L-k+1);
		
		s=S;
		FOR(i,L) s[Q[i]]=S[i];
		FOR(i,L) S[i]=s[(i+(k-1))%L];
		_P("%s\n",S.c_str());
	}
}

まとめ

処理する位置を1ずつずらすのではなく、全体をローテートするのか…。
以前リングバッファを使う問題やってたのに、これはすんなり出てこなかったので反省。