この解法は面白いな。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef2/00000000002d5b64
問題
正整数R,Sが与えられる。
1~Rを順にS回繰り返した長さR*Sの数列が与えられる。
先頭A個と、続くB個を選択し、それらを入れ替える(prefix (A+B)個をA個手前にrotateする)ことができるとする。
この操作を最小回数行い、数列をソートせよ。
解法
異なる値が並んでいるところを、できるだけ同じ値が並ぶようにする。
処理1回で2か所そうできる。
数列が[X....Y....XY....]の構成を取るとする。先頭要素Xと同じ値を持つ最も後ろの要素を求めよう。
次に、最後のXの次と同じ値Yのうち、最後のXの手前にあるものを求めよう。
この時、[X...Y][...X][Y....]と数列を分け、前2つを入れ変えると[...X][X....Y][Y....]と2か所同じ値が並ぶ場所が増える。
R,Sの値によっては、あと1か所だけそろえればよい状態になるので注意。
その場合、prefixがソート後の配列をrotateしたものになっている。
int R,S; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>R>>S; vector<int> V; FOR(i,S) for(j=1;j<=R;j++) V.push_back(j); vector<pair<int,int>> ret; int len=R*S; while(len) { int ma=0; FOR(i,len) if(V[i]>=V[ma]) ma=i; if(ma==len-1) { len--; } else { //FORR(v,V) cout<<v<<" "; //cout<<endl; int cnt=0; FOR(i,len-1) if(V[i]>V[i+1]) cnt++,x=i; if(cnt==1 && V[0]>=V[len-1]) { ret.push_back({x+1,len-(x+1)}); } else { y=0; FOR(x,len) if(V[y]==V[x]) y=x; FOR(x,y+1) if(V[x]==V[y+1]) break; if(x==y+1) { ret.push_back({y+1,len-(y+1)}); } else { ret.push_back({x+1,y-x}); } } rotate(V.begin(),V.begin()+ret.back().first,V.begin()+ret.back().first+ret.back().second); } } //FORR(v,V) cout<<v<<" "; //cout<<endl; _P("Case #%d: %d\n",_loop,(int)ret.size()); FORR(r,ret) _P("%d %d\n",r.first,r.second); }
まとめ
いろいろな解法がありそう。