AtCoder Begginer Contest #013 D.阿弥陀

問題

http://abc013.contest.atcoder.jp/tasks/abc013_4

問題概要

N本の縦線とM本の横線で構成されたあみだくじがある。
(M本の横線の位置の情報が与えられる。)
このくじをD個縦につなげたとき、
左からi番目(1<=i<=Nを満たすi全て)の縦線を選ぶと
最終的にどこにたどり着くかそれぞれ答えなさい。

制約

• 2<=N<=10^5
• 0<=M<=2*10^5
• 1<=D<=10^9

解法

まず「D=1について左からi番目を選ぶとどこに飛ぶか」という対応表を作る。

ここから、D回地道にシュミレーションすると、1回のシュミレーションにO(D)かかる。
これをN回(iの範囲分)繰り返すので、O(ND)となってしまい、TLE。

そこで、「D=2^iについてj番目を選ぶとどこに飛ぶか」という対応表dp[i][j]を考える。
この配列の大きさは、NlogDとなる。
この対応表を埋めるとき、i=0については、D=1の場合と同様。
iとi+1番目について、

dp[i + 1][j] = dp[i][dp[i][j]];

が成り立つ。
(内側のdp[i][j]で移動した先を入力として、さらに移動させている。こうすると、2^i回のみに限るが、
効率よく場所を計算することが出来る。)
こんな感じに、2^n回の操作の移動先を2^(n-1)回の操作の移動先から求めることをダブリングというらしい。

これが求まってしまえば、後はDを２進数表記で解釈して、操作をしていけば良い。
（D=7なら、4回操作→2回操作→1回操作をすれば良い）

計算量はO(NlogD)。

もっと一般的に

ある写像f:A→Aがあるとき、fをD回掛けた結果を素早く求めるときは
先程のようなテーブルを取ると良い。
今回の写像は、左からi番目と右からj番目を対応づける写像。

また、一般的な木（グラフ理論の木）について、
f(v):V→Vを「f(v) : vの親」と定義すると、これもこのテクニックを使うことが出来る。
（具体的には、LCA(Lowest Common Ancestor)などで使える。）

つまずいたところ

• 移動先をもとめるときに、横棒は逆順から適用していかないとダメ
  • 普通の順番で適用すると、「下側のi番目に上側の何番目が入るか」を求めてしまう
  • 求めるべきは「上側のi番目が下側の何番目に入るか」である
• dpの配列の大きさを間違えた
  • なぜかDが10万だと思ってたり、Nが1万だと思ってたり
• D回適用するところで、now = [j][i]; とやってしまった
  • 8回移動したのを「取り消して」、16回移動…

感想

• ダブリングはかなり一般的に使えそうな気がした。
• 解いてて面白かったです。(小並感)

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
 
const int MAX_LOG_V = 30;
 
int dp[MAX_LOG_V][100001] = {0};
 
bool comp(pii a, pii b) {
	return a.second < b.second;
}
 
int main(int argc, char const *argv[]) {
	int n, m, d;
	cin >> n >> m >> d;
 
 
	for (int i = 0; i < 100001; ++i) {
		dp[0][i] = i;
	}
	std::vector<int> v;
	for (int i = 0; i < m; ++i) {
		int a;
		cin >> a;
		a--;
		v.push_back(a);
	}
	for (int i = v.size() - 1; i >= 0; --i) {
		swap(dp[0][v[i]], dp[0][v[i] + 1]);
	}
 
	for (int i = 0; i < MAX_LOG_V - 1; ++i) {
		for (int j = 0; j < n; ++j) {
			dp[i + 1][j] = dp[i][dp[i][j]];
		}
	}
 
	for (int i = 0; i < n; ++i) {
		int d_ = d;
		int now = i;
		int j = 0;
		do {
			if (d_ & 1) {
				now = dp[j][now];
			}
			d_ >>= 1;
			j++;
		} while(d_ != 0);
 
		cout << now + 1 << endl;
	}
 
	return 0;
}