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ずつずらすのではなく、全体をローテートするのか…。
以前リングバッファを使う問題やってたのに、これはすんなり出てこなかったので反省。