ABC013 D - 阿弥陀

D - 阿弥陀

概要

N本の縦棒、M本の横棒をもつあみだくじがある。
1からNまでの各整数iについて、i番目の縦棒からスタートしてこのあみだくじをD回通った後に、何番目の縦棒に到達するかを出力せよ。

制約

2 ≦ N ≦ 10^5
0 ≦ M ≦ 2 * 10^5
1 ≦ D ≦ 10^9

方針

ポイント1
あみだくじを1回通った時のスタートとゴールの対応について。
添字と同じ数値をもつ配列sgを準備し、下の横棒から順番に配列値をswapしていく。
そうすると、「sg[s] = g ⇔ 縦棒sからスタートしてあみだくじを1回通ると、縦棒gに到達する」という対応をもつ配列sgが得られる。

ポイント2
あみだくじをD回通る操作について。
ダブリングという手法を用いると、D回の操作が(定数 * logD)回ですむようになる。

＜ダブリング説明① DP＞
次のようなDPを考える。
dp[i][j] : i番目の縦棒からスタートしてあみだくじを2^ j回通った時に到達する縦棒の番号　とする。
このDPは下記のように遷移する。
dp[i][0] = sg[i] （初期値、あみだくじを2^0 = 1回通った時）
dp[i][j] = dp[dp[i][j-1]][j-1]

2つ目の式について。
dp[i][j-1]=t とすると、2つ目の式は次のように書きかえられる。
dp[i][j] = dp[t][j-1]
つまり、i番目の縦棒からスタートしてあみだくじを2^(j-1)回通るとt番目の縦棒に到達しているので、t番目の縦棒からさらにあみだくじを2^(j-1)回通ることで、全体としてはi番目の縦棒からあみだくじを2^j回通っていることになる。

＜ダブリング説明② 2の累乗以外の場合＞
上記DPにより、あみだくじを通った回数が2の累乗の場合は、到達する縦棒がわかる。
回数が2の累乗以外の場合についても、操作回数の2進展開を用いることで、到達する縦棒を求めることができる。
（乗算の高速化と同じような考え方）

感想

下記のサイトを参考にしました。
mmxsrup.hatenablog.com

初ダブリングでした。
DPの式には最初面くらいましたが、応用のききそうな考え方だと思いました。

解答

Submission #4499768 - AtCoder Beginner Contest 013

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N, M, D;
	cin >> N >> M >> D;
 
	int A[M];
	rep(i, M) cin >> A[i];
 
	int sg[N+1];
	for(int i = 1; i <= N; i++) {
		sg[i] = i;
	}
 
	for(int i = M - 1; i >= 0; i--){
		swap(sg[A[i]], sg[A[i]+1]);
	}
 
	// ダブリング
	vector<vector<int>> dp(N+1, vector<int>(31, 0));
	for(int i = 1; i <= N; i++){
		dp[i][0] = sg[i];
	}
 
	for(int j = 1; j < 31; j++){
		for(int i = 1; i <= N; i++){
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
 
	for(int i = 1; i <= N; i++){
		int t = i;
		for(int j = 0; j < 31; j++){
			if((D >> j) & 1){
				t = dp[t][j];
			}
		}
 
		cout << t << endl;
	}
}