Codeforces Round #324 (Div. 2) E. Anton and Ira

こういう地頭みたいな問題全く解けないの本当に悲しい。

問題

codeforces.com

解法

わからなかったので解説を参考にしました。codeforces.com

とりあえず目標となる順列 s が 1 2 3 4 ... n となるように p を調整しておきます(下のコードでは間違えて p を目標になるようにしてしまったので最後に反転させました)。

右端から揃えていくことを考えます。今 n 個の数字を動かすことを考えているとすると, 右端の数は n になるはずです。なので, 右端を n にしようとかんばります。

p[pos] = n であるとします(n が右端にあったら n-1 個の数字を動かす段階に移行すれば良いのでここでは pos < n を仮定しています)。この時, 以下を満たす pos2 が必ず存在します。
pos > pos2
p[pos2] <= pos
証明をざっくり書くと, もしこのような pos2 が存在しないとすると p[1], p[2], ..., p[pos-1] までに 1, 2, ..., pos までの数字があることになります。しかし, p[1], ..., p[pos-1] は pos-1 個で, 1, 2, ..., pos は pos 個あるのでおかしい, という感じです。

ということでこのような pos2 が存在するわけですが, この p[pos] と p[pos2] を swap します。すると, p[pos] は右側に行くので, 当然目標位置に近づきます(右端が目標地点ですから)。また, p[pos2] <= pos であるので, p[pos2] はやはり目標地点に近づきます。

実は, このように数字を swap していけば swap のコストを最小に抑えることが出来ます。なぜかというと, そもそも swap の最低限必要なコストは, abs(p[i]-i) の 1 <= i <= n の和です。つまり, i から p[i] に向かって(行ったり来たりせず)まっすぐ向かうことができれば(例えば p[2] = 3 の場合, 3 の座標が 2 -> 1 -> 3 とかなったりせず 2 -> 3 と一発で行ってくれる, ということ), コストの浪費は無いわけです。
ここで, 先ほどの swap の仕方を考えてみます。上の方法では, それぞれの数字は行ったり来たりせず一直線に目標地点に動こうとすることがわかります。よって, コスト的には最適なのです。

const int MAXN = 2010;
int pos[MAXN], p[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        pos[x] = i;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        p[i] = pos[x];
    }
    vector<pii> ans;
    ll sum = 0;
    for (int i = n; i >= 1; i--) {
        int cur;
        for (cur = 1; cur <= n; cur++) {
            if (p[cur] == i) break;
        }
        while (cur < i) {
            for (int j = cur+1; j <= n; j++) {
                if (p[j] <= cur) {
                    swap(p[j], p[cur]);
                    ans.emplace_back(cur, j);
                    sum += abs(cur-j);
                    cur = j;
                    break;
                }
            }
        }
    }
    cout << sum << endl;
    cout << ans.size() << endl;
    reverse(ans.begin(), ans.end());
    for (pii p : ans) {
        printf("%d %d\n", p.first, p.second);
    }
    return 0;
}