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; }