ABC 013 D - 阿弥陀

問題

問題概要

省略。

解法

まず、簡単にわかることは、D=1の場合において、上側の何番目から始めたら、下側の何番目につくかというのを求める。それを利用して、それぞれの列から開始して、d回後にどこにいるかを求めればいい。しかし、このようにやってしまうと、計算量が(n*d)になりTLE。 よって、その部分を効率よく求めなければならない。このときに使えるのがダブリングらしい。
dp[i][j] := (d = 2ⁱ)についてj番目を選ぶとどこにいくかをメモしておくことで、高速に求まる。これは、数字を2進数で表した時に、bitが立っている部分をdpでメモしてあるように動かせばよいということになる。 例えば、d=6(110)回の時は、普通にやると6回移動させなければならないが、ダブリングを使うことで、dp[2]とdp[1]をつかうだけで、4回と2回動かしたことになり、合計6回動かいたことになる。
dpを求める計算であるが、前から順番に求めていたら、意味がないのが、漸化式で、
dp[i + 1][j] = dp[i][dp[i][j]]　が成り立つので、dpを早く埋めることもでき。この漸化式は、2進数で2倍すると桁が一つ大きくなることを利用して、2倍動かすことで、2ⁱ回の情報から2ⁱ⁺¹回の操作でたどり着く場所を求めている。
100 = 10 + 10 (2進数) : dp[2][now] = dp[1][dp[1][now]] (内側のdp[1][now]で2回動かし、そのあと外側で2回動かし、合計4回動かしたものが求まっている。2倍の回数動かしている。)

分かりやすく書いてあるサイト

kakira.hatenablog.jp

ミス

//(n*m)で TLE
for (int p = 0; p < n; ++p){
    int now = p;
    for (int i = 0; i < m; ++i){
        if(a[i] == now){
            now++;
        }else if(a[i] == now - 1){
            now--;
        }
    }
    goal[p] = now;
}

あみだくじの上側の何番目が下側の何番目に行くかを求めた時、上のように一列ずつ求めたら、TLE。 TLEしないためには、下のコードのように、横棒を下から見ていき、swapするようにして求めていけばいい。このとき、下の棒から見ていくことで、上側の何番目が、下側の何番目に来るかがわかるが、逆から求めようとすると、その逆が求まるので注意。

コード

#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int n, m, d;
int a[200010], goal[200010];
//dp[i][j] := d = 2^iについてj番目を選ぶとどこにいくか
int dp[30][100010];

int main(void){
    cin >> n >> m >> d;
    rep(i, m){
        int t; cin >> t; t--;
        a[i] = t;
    }

    rep(i, n) goal[i] = i;
    for (int i = m - 1; i >= 0; --i){//後ろからたどる
        swap(goal[a[i]], goal[a[i] + 1]);
    }

    //ダブリングで計算していく
    rep(i, 100010) dp[0][i] = goal[i];//2^0(d=1)の時

    for (int i = 0; i < 30; ++i){
        for (int j = 0; j < n; ++j){
            dp[i + 1][j] = dp[i][dp[i][j]];
        }
    }

    rep(i, n){//start
        int now = i;
        for (int j = 0; j < 30; ++j){//2^j回移動
            if((d & (1 << j)) != 0){//2^j回移動を使う
                now = dp[j][now];
            }
        }
        printf("%d\n", now + 1);
    }
    return 0;
}