良い順位でレートは上がっていいんだけど、何なんだ今回の問題。
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位とかなりの差があった…。