ABC 013 D

今日は3問ときました。順にメモ。
まずはこの問題。

abc013.contest.atcoder.jp

縦線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…の場合を求めてそれを組み合わせる、というやり方はよくありますね。覚えておかないと。