kmjp's blog

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

TopCoder SRM 755 Div1 Easy Div2 Medium OneHandSort

良い順位でレートは上がっていいんだけど、何なんだ今回の問題。
https://community.topcoder.com/stat?c=problem_statement&pm=15416

問題

(N+1)個のスロットのうち、頭N個が埋まっており、0~(N-1)の値が1個ずつ入っている。
これらを昇順に並べ替えたい。

その際、内容が埋まったスロットの内容を空きスロットに移動する、という作業を最大3N回行い、並べ替えを達成せよ。

解法

3手あれば最後末尾のスロットを空き状態に保ったまま2値をswapできるので、あとはそれを最大Nセット行えばよい。

class OneHandSort {
	public:
	vector <int> sortShelf(vector <int> target) {
		vector<int> R;
		int i,N=target.size(),j;
		FOR(i,N) if(target[i]!=i) {
			FOR(j,N) if(target[j]==i) break;
			R.push_back(i);
			R.push_back(j);
			R.push_back(N);
			swap(target[i],target[j]);
		}
		return R;
	}
}

まとめ

これ解いた速度2位だったんだけど、1位とかなりの差があった…。