Twist the Permutation-Codeforces

投稿日：2022/04/09 更新日:2022/04/09

問題

$1$ から $n$ の整数で構成された整数があります。 $a_i = i$ です。

数列に対し以下の操作を行います。

$i$ 番目の操作では $1$ から $i$ 番目までの要素を選び、右に任意の回数シフトする。
$a = [a_1, a_2, ..., a_n]$ の配列を1回シフトすると
$a = [a_i, a_1, ..., a_{i-1}, a_{i+2}, ..., a_n]$ となる

操作後の配列が与えられます。それぞれの操作で何回シフトするのかをスペース区切りで出力してください。答えが存在しなければ $-1$ を出力してください。

解法

後ろから見ていきます。

一番後ろの要素 $a_n$ に注目します。
$a_n$ が動くのは $n$ 番目の操作のみです。したがって、与えられた数列の位置との差から操作の回数が決まります。 $n$ 番目の操作回数が決まれば、次は $n-1$ の操作回数が決まります。再帰的に繰り返すことにより答えが求まります。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int,int> mp;
    for(int i = 0;i < n; ++i){
        cin >> a[i];
        a[i]--;
        mp[a[i]] = i;
    }

    vector<int> ans;
    for(int i = n-1; i >= 0; --i){
        int index = mp[i];
        int ope = index - i;
        if(ope < 0){
            ope = (i+1) + ope;
        }

        ans.push_back(ope);

        vector<int> shift = a;
        for(int j = 0;j <= i; ++j){
            int p = (j - ope + i+1) %(i+1);
            shift[p] = a[j];
            mp[a[j]] = p;
        }


        swap(shift, a);
    }

    cout << ans[n-1];
    for(int i = n-2;i >= 0; --i){
        cout << " " << ans[i];
    }
    cout << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}