Learning Algorithms

アルゴリズムの勉強メモ

Atcoder AGC 006 C. Rabbit Exercise

Atcoder AGC 006 C. Rabbit Exercise

C: Rabbit Exercise - AtCoder Grand Contest 006 | AtCoder

解法

まず、各ステップにおいて、期待値を決定していけることに注目する。うさぎ$\ a\ $について、そのジャンプ後の位置の期待値は、左右のジャンプが両方確率$\ \frac {1}{2}\ $であることから、$\ (x_{a - 1} - x_a) + (x_{a + 1} - x_a) + x_a = x_{a - 1} + x_{a + 1} - x_a\ $となる。

ここから先の考察は解説をみた。この式をよく見ると、$\ x_a - x_{a - 1}\ $と$\ x_{a + 1} - x_a\ $の値の交換になっていると気づくらしい。確かにそうだなという感じだった。よってあとは階差数列をswapしまくればいい。

実装
#include "bits/stdc++.h"
using namespace std;

signed main() {
        int n;
        cin >> n;
        vector<long long> x(n);
        for (int i = 0; i < n; i ++) cin >> x[i];
        vector<long long> d(n - 1);
        for (int i = 0; i < n - 1; i ++) d[i] = x[i + 1] - x[i];
        long long m, k;
        cin >> m >> k;
        vector<long long> a(m);
        for (int i = 0; i < m; i ++) { 
                cin >> a[i];
                a[i] --;
        }
        vector<long long> move(n - 1);
        for (int i = 0; i < n - 1; i ++) move[i] = i;
        for (int i = 0; i < m; i ++) swap(move[a[i]], move[a[i] - 1]);
        vector<vector<long long> > swp(n - 1, vector<long long> (61));
        for (int i = 0; i < n - 1; i ++) swp[move[i]][0] = i;
        for (int i = 1; i < 61; i ++) { 
                for (int j = 0; j < n - 1; j ++) { 
                        swp[j][i] = swp[swp[j][i - 1]][i - 1];
                }
        }
        for (int b = 0; b < 61; b ++) {
                if ((k >> b) & 1) {
                        vector<long long> next(n - 1);
                        for (int i = 0; i < n - 1; i ++) next[swp[i][b]] = d[i];
                        for (int i = 0; i < n - 1; i ++) d[i] = next[i];
                }
        }
        long long prev = x[0];
        cout << prev << endl;
        for (int i = 0; i < n - 1; i ++) { 
                prev = d[i] + prev;
                cout << prev << endl;
        }
        return 0;
}