操作を 回行った結果を求める系、苦手意識あるけど克服したい!
問題概要
と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。
- 各操作は 個の数値 で与えられる。各数値はボールの index を表す。
- 数値 に関する操作では、ボール の座標がそれぞれ であるとき、 を か かのいずれかに置き換える (一様ランダム)
制約
考えたこと
回繰り返すと言っているけど、まずは の場合が解けないことにはどうにもならない。そしてそれが解ければ、きっと何かしら「繰り返し二乗法」が使える状況になるんじゃないかという気がする。
さて、 の場合を考えようと思うのだけど、それだけでも確率的な挙動をして訳がわからないことになりそう。でも、どうせ期待値で考えれば単純になるに決まってる!!!
まず、1 回目の操作では
- なボールの次の座標の期待値は となる
ということがわかる。そして多分、期待値だけ覚えておけば操作をシミュレートできるのではなかろうか。たとえば、ボール の座標が のいずれかであることがわかっている状況でボール について操作をするとき、ボール の位置を として期待値は、
となっている。つまり問題は次のように言い換えられるだろう (ちゃんとした証明は editorial に)
ボール に関する操作では、 を に置き換える
こうして、純粋なシミュレーション問題に落ち着いた。少なくとも の場合についてはこれで解けた。
ある種の行列累乗っぽい
ここまで来てさらに思ったことは、初期状態の各ボールの座標はそれほど重要ではないということ。最終結果において各ボールの座標は、初期状態の各ボールの座標の線形結合で書けるだろう。そしてその係数は、初期状態の座標に依らずに決まるだろう。というわけでそれを頑張って求めたい。
とかだったら、行列累乗で求められる。 を にするのは一次変換なので行列で表現できる。でも行列累乗だと かかってしまうのでとても間に合わない。
何かしらいい感じの構造になっているはずだ。具体的なケースで手を動かしてみる。たとえばボール 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 操作っぽくなっているのではなかろうか。そう考えながら、元の操作を振り返ってみる。
- を にする操作
なのだが、階差数列をとった世界で考えてみると、
- を にする操作
ということになっている!!!!!これはまさしく swap 操作だ!!!
順列を写像と見て繰り返し二乗法
個の座標に対して、いもす法的変換 (階差をとる変換) を行うと、なんと 1 回 1 回の操作は隣接 swap 操作に対応することがわかった!!!
よって、 回の操作は順列操作ということになる。そこまでわかったならば、それを 回適用したものは繰り返し二乗法によって求めることができる。
#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; } }