Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC013-D 阿弥陀】ダブリング

D - 阿弥陀

あほくさいが実装に一時間かかった。ジムに行く前に、こう考えるべきだったという反省をしておく。

問題

縦線がN(105)、横線がM(105)の阿弥陀くじが与えられる。これをD(109)回連結させる。この時、最終地点の並び順を答えなさい。

考え方

まず、D1回分の遷移を考えて、それを繰り返し二乗法のようにしてlogオーダーに落とし込む。1回分の遷移はスワップをM回繰り返せば計算出来る。方針自体は難しくない。

ここで遷移をどう考えるかだが、最終的には、行列のように考えるのが良いと思った。つまり、対角成分だけがあって、それぞれの成分が、「どのインデックスの値を引っ張ってくるか」を意味している行列を考える。例えばサンプルの例であれば、対角成分は4,2,5,3,1となる。こうすると、この遷移は合成可能であることが明確になる。

こう考えると、合成していく部分も、

            let tr = trans[k-1][i];
            trans[k][i] = trans[k-1][tr];

で一次変数をとるのは却って不自然だとわかるはず。

            trans[k][i] = trans[k-1][trans[k-1][i]]

合成ならばこう書けるべきなので。

この遷移の合成部分が頭の中で整理されていなくて、ピンと来なかった。

実装

bin_digitsなる関数も実装した。この関数は、用意する配列の長さを決めるのにも使えるし、どの道せいぜい109程度ならば、返り値の長さも30程度なのだから、ループの中で値を変化させていってわけのわからんことになるよりも簡明な分優ると思った。

いくつかのデータセットで200msもかかってるが、たぶん出力の方法がやばい。しかし逆にいうと、105くらいであれば、一度バッファに貯めて流すということをせずとも、毎回println!して十分に間に合うということはわかった。意味のない最適化をすべきではない。

fn solve() {
    input! {
        N: usize, M: usize, D: usize,
        A: [usize; M],
    }
    let mut dp = vec![0; N+1];
    for i in 1..N+1 {
        dp[i] = i;
    }
    for j in 0..M {
        let a = A[j];
        let tmp = dp[a+1];
        dp[a+1] = dp[a];
        dp[a] = tmp;
        // dbg!(&dp);
    }
    // dbg!(&dp);
    let bd = bin_digits(D);
    let mut trans = vec![vec![0; N+1]; bd.len()];
    trans[0] = dp;
    // dbg!(&trans);

    let mut k = 1;
    while (1<<k) <= D {
        for i in 1..N+1 {
            let tr = trans[k-1][i];
            trans[k][i] = trans[k-1][tr];
        }
        k += 1;
    }
    // dbg!(&trans);

    let mut ans = vec![0; N+1];
    for i in 1..N+1 {
        ans[i] = i;
    }
    for k in 0..bd.len() {
        if !bd[k] { continue; }
        // dbg!(k, &trans[k]);
        let mut tmp = vec![0; N+1];
        for i in 1..N+1 {
            let tr = trans[k][i];
            tmp[tr] = ans[i];
        }
        ans = tmp;
    }
    // dbg!(&ans);

    for i in 1..N+1 {
        println!("{}", ans[i]);
    }
}