ABC 013 D
今日は3問ときました。順にメモ。
まずはこの問題。
縦線n本、横線m本からなるあみだくじを、d個縦につなげたあみだくじを考えます。
左から1~n本目それぞれについて、あみだくじの結果左から何番目にたどり着くかを求めましょう、という問題です。
n, m <= 10^5、k <= 10^9とかなり大きいです。これに注意しないといけません。
解答は以下のようになりました。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int result[100001][31]; int main() { int n, m; long long int d; cin >> n >> m >> d; int a[200001]; for(int i = 0; i < m; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ result[i][0] = i; } for(int j = 0; j < m; j++){ swap(result[a[j]][0], result[a[j] + 1][0]); } for(int i = 1; i < 31; i++){ for(int j = 1; j <= n; j++){ result[j][i] = result[result[j][i - 1]][i - 1]; } } vector<int> ans(100001); for(int i = 1; i <= n; i++){ ans[i] = i; } for(int i = 30; i >= 0; i--){ if(d < (long long int)pow(2, i)) continue; vector<int> newans(100001); for(int j = 1; j <= n; j++){ newans[j] = result[ans[j]][i]; } ans = newans; d -= (long long int)pow(2, i); } vector<int> finalans(100001); for(int i = 1; i <= n; i++){ finalans[ans[i]] = i; } for(int i = 1; i <= n; i++){ cout << finalans[i] << endl; } return 0; }
result[i][j]は、あみだくじを2^j個つなげたとき、左からi番目がたどりつく先を表します。
まずresult[i][0]、つまりあみだくじを一回試行した時の結果を求めます。
一本ずつ順に確認するとO(nm)となるので間に合いません。
すべての線を同時にスタートして横線があるところをswapする、というふうにすればm回計算するだけですべての縦線に対して到着点がわかります。
つぎにあみだくじを2^1個、2^2個、…、2^j個、…とつなげたときの到着点を求めます。
2^j個つなげた時を求めるのに、2^(j - 1)個つなげた時の結果を利用します。
i番目の縦線について、2^(j-1)個あみだくじをつなげた時の到着点から、さらに2^(j-1)個あみだくじをつなげた時の到着点を求めればよいです。
これを30回くりかえせば2^30 = 1073741824より、dが最大値を取った時でも対応できます。
あとはこれを利用して答えを得ることができます。
スタート地点から到着点への写像(?)となる行列があることに気づき、この2^1、2^2…の場合を求めていく方法を思いつきました。今回はnの値が大きいので行列は無理でしたが。
回数が多い時に、2^1, 2^2, 2^3…の場合を求めてそれを組み合わせる、というやり方はよくありますね。覚えておかないと。