kmjp's blog

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

Google Code Jam 2020 Round 1B : C. Join the Ranks

この解法は面白いな。
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);
}

まとめ

いろいろな解法がありそう。