けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 006 C - Rabbit Exercise (赤色, 800 点)

操作を  K 回行った結果を求める系、苦手意識あるけど克服したい!

問題へのリンク

問題概要

 1, 2, \dots, N と番号の振られた  N 個のボールがあって、初期状態ではそれぞれ  x_{1}, x_{2}, \dots, x_{N} の位置にある。以下の操作を  K 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。

  • 各操作は  M 個の数値  a_{1}, \dots, a_{M} で与えられる。各数値はボールの index を表す。
  • 数値  a に関する操作では、ボール  a-1, a, a+1 の座標がそれぞれ  x_{a-1}, x_{a}, x_{a+1} であるとき、 x_{a} 2x_{a-1} - x_{a} 2x_{a+1} - x_{a} かのいずれかに置き換える (一様ランダム)

制約

  •  N, M \le 10^{5}
  •  K \le 10^{18}

考えたこと

 K 回繰り返すと言っているけど、まずは  K = 1 の場合が解けないことにはどうにもならない。そしてそれが解ければ、きっと何かしら「繰り返し二乗法」が使える状況になるんじゃないかという気がする。

さて、 K = 1 の場合を考えようと思うのだけど、それだけでも確率的な挙動をして訳がわからないことになりそう。でも、どうせ期待値で考えれば単純になるに決まってる!!!

まず、1 回目の操作では

  •  x_{a} なボールの次の座標の期待値は  x_{a-1} + x_{a+1} - x_{a} となる

ということがわかる。そして多分、期待値だけ覚えておけば操作をシミュレートできるのではなかろうか。たとえば、ボール  a+1 の座標が  p, q のいずれかであることがわかっている状況でボール  a について操作をするとき、ボール  a-1 の位置を  r として期待値は、

 \frac{(p + r - x) + (q + r - x)}{2} = \frac{p + q}{2} + r - x = (ボール a の位置の期待値) + r - x

となっている。つまり問題は次のように言い換えられるだろう (ちゃんとした証明は editorial に)


ボール  a に関する操作では、 x_{a} x_{a-1} + x_{a+1} - x_{a} に置き換える


こうして、純粋なシミュレーション問題に落ち着いた。少なくとも  K = 1 の場合についてはこれで解けた。

ある種の行列累乗っぽい

ここまで来てさらに思ったことは、初期状態の各ボールの座標はそれほど重要ではないということ。最終結果において各ボールの座標は、初期状態の各ボールの座標の線形結合で書けるだろう。そしてその係数は、初期状態の座標に依らずに決まるだろう。というわけでそれを頑張って求めたい。

 N \le 1000 とかだったら、行列累乗で求められる。 x_{a} x_{a-1} + x_{a+1} - x_{a} にするのは一次変換なので行列で表現できる。でも行列累乗だと  N^{3}M\log{K} かかってしまうのでとても間に合わない。

何かしらいい感じの構造になっているはずだ。具体的なケースで手を動かしてみる。たとえばボール 1, 2, 3, 4 に対して、2, 3, 2 の順で操作をすると、

(1, 0, 0, 0)
(0, 1, 0, 0)
(0, 0, 1, 0)
(0, 0, 0, 1)

(1, 0, 0, 0)
(1, -1, 1, 0)
(0, 0, 1, 0)
(0, 0, 0, 1)

となって、

(1, 0, 0, 0)
(1, -1, 1, 0)
(1, -1, 0, 1)
(0, 0, 0, 1)

となって最後に

(1, 0, 0, 0)
(1, 0, -1, 1)
(1, -1, 0, 1)
(0, 0, 0, 1)

となる。これだけだとなんとも言えないけど、色々試してみると

  • 結局 1 と -1 しか出てこない
  • 同じ操作を 2 回連続でやると必ず元に戻る
  • なんかごちゃごちゃやると元に戻るパターンがある

という雰囲気が読み取れた。こういうの少し見覚えがある...そう、隣接 swap 操作だ!!!

今回の線形変換は、なんらかの意味で隣接 swap 操作っぽくなっているのではなかろうか。そう考えながら、元の操作を振り返ってみる。

  •  (x, y, z) (x, x-y+z, z) にする操作

なのだが、階差数列をとった世界で考えてみると、

  •  (x, y-x, z-y) (x, z-y, y-x) にする操作

ということになっている!!!!!これはまさしく swap 操作だ!!!

順列を写像と見て繰り返し二乗法

 N 個の座標に対して、いもす法的変換 (階差をとる変換) を行うと、なんと 1 回 1 回の操作は隣接 swap 操作に対応することがわかった!!!

よって、 M 回の操作は順列操作ということになる。そこまでわかったならば、それを  K 回適用したものは繰り返し二乗法によって求めることができる。

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

vector<int> operator * (const vector<int> &a, const vector<int> &b) {
    vector<int> res(a.size());
    for (int i = 0; i < res.size(); ++i) res[i] = a[b[i]];
    return res;
}

vector<int> power(const vector<int> &a, long long N) {
    vector<int> res(a.size());
    iota(res.begin(), res.end(), 0);
    if (N == 0) return res;
    res = power(a, N/2);
    res = res * res;
    if (N & 1) res = res * a;
    return res;
}

int N, M;
long long K;
vector<long long> x, a;

int main() {
    cin >> N;
    x.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i];
    for (int i = N-1; i >= 1; --i) x[i] -= x[i-1];
    cin >> M >> K;

    vector<int> p(N);
    iota(p.begin(), p.end(), 0);
    a.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> a[i], --a[i];
        swap(p[a[i]], p[a[i]+1]);
    }
    p = power(p, K);
    vector<long long> res(N);
    for (int i = 0; i < N; ++i) res[i] = x[p[i]];
    for (int i = 1; i < N; ++i) res[i] += res[i-1];
    for (int i = 0; i < N; ++i) {
        cout << fixed << setprecision(10) << (double)(res[i]) << endl;
    }
}