AtCoder Grand Contest 006 C - Rabbit Exercise

この類、すｇｇｇｇｇｇｇっごい苦手だぴょん。

問題

C - Rabbit Exercise

ぴょん

ダブリングを始めて書いた気がするうさー。

問題の解説を読んでると思うさが、

「〇〇という操作をするして△△というアルゴリズムを使うと解けます。」

と言われると解けない気がするうさが

「△△というアルゴリズムを適用したいのですが、このままだとできないので〇〇という操作を行います。」

と考えると解ける気がしませんぴょん？語尾やめて？はい。

つまり、今回だと

「yi ← yi−1 + yi+1 − yi という操作をよく観察すると，yi − yi−1 の値と yi+1 − yi の値が交換されていることに気づきます．その操作を累積すると解けます」

ではなくで

「操作を累積させて解きたいけれどyi ← yi−1 + yi+1 − yiだとできないからyi − yi−1 の値と yi+1 − yi の値が交換されているという風にみる。」

みたいな感じ。この問題に対していえば操作を10^18回行うなんて、累積させないと厳しそうだもんね。最初っから累積を頭に入れて考えておくのがよさげ。

すごい個人的な感覚だけれど、解説を理解するときはこの感覚を持っていた方がいい気がしたりしなかったり。

期待値って出た瞬間に身構えませんか？私は身構えます、苦手なので。

確定的な操作に変えたいという動機は分かるけれど本当にそれで確定的な操作にしていいの？ってかなり悩みそう(少し考えればわかる話だけれど)。

ここら辺は数学力ですね。数学難しい。

ソースコード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int x[80][111111];
ll diff[111111];

int main(){
	
	ll n;cin >> n;
	vector<ll> v(n);
	REP(i,n)cin >> v[i];
	ll m,k;cin >> m >> k;
	vector<ll> a(m);
	REP(i,m){
		cin >> a[i];
	}
	
	REP(i,n)x[0][i] = i;
	REP(i,m)swap(x[0][a[i]],x[0][a[i]-1]);
	
	for(int i = 0;i < 69;i++){
		REP(j,n){
			x[i+1][j] = x[i][x[i][j]];
		}
	}
	
	for(int i = 1;i < n;i++){
		int tmp = i;
		for(ll j = 0;j < 60;j++){
			if(k & (1LL << j)){
				tmp = x[j][tmp];
			}
		}
		diff[i] = v[tmp] - v[tmp-1];
	}

	diff[0] = v[0];
	cout << v[0] << endl;
		
	for(int i = 1;i < n;i++){
		diff[i] += diff[i-1];
		cout << diff[i] << endl;
	}
	
	return 0;
}

ちょっと書き方汚い気もしますが。

そういえば誤差が～とかいうけれど整数値しか出ませんね。65(OIOI)。