東京工業大学プログラミングコンテスト2015 I - そーっとソート
典型力と地力を上げたくてなんとなく
docs.google.com
を解いていってるんだけど、ビビるくらい良い問題も何個かあったからどんどん書いていきます
問題
(1,2,...,n)の順列として数列aが与えられる
以下の操作を10^5回まで行えるとき、数列を1,2,...,nに並び替えることができるか判定し、できるときは手順を1つ示せ
操作: |i-j| = a[i]または|i-j| = a[j]であるような2要素a[i]、a[j]をswapする
1 <= n <= 50
解法
(以下インデックスは全部1-based)
右から順に埋めていくことにする
実は今a[m+1]〜a[n]がソートし終わった状態であるとき、「a[m]とa[a[m]]をswapする」という操作をたかだかm回繰り返せば、いつか必ずa[m] = mとなる
例えば
32154
42153
43152
43251
43215
こんな感じで、この操作を繰り返すたびにa[m]をm以下の数字と重複することなくシャッフルできる
int n, a[55]; vector<pair<int,int> > res; signed main() { cin >> n; for (int i=0; i<n; i++) cin >> a[i]; for (int i=n-1; i>=0; i--) while (a[i]!=i+1) { res.push_back({i+1-a[i], i+1}); swap(a[i-a[i]], a[i]); } cout << res.size() << endl; for (auto i:res) cout << i.first << ' ' << i.second << endl; }