Rustコトハジメ

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

yukicoder contest No.224 反省会

疲れとインプラントの手術のダメージで死にかけてるが気合で参加した。

yukicoder contest 224 - yukicoder

D

問題が理解出来なかった。

E

ここでやっておいてよかったなぁと思った。

Nが異常にでかいのでひと目ダブリングだが、やったことがない問題なのでわからなかった。

AaN + BbNみたいな形になってダブリングが出来るようになるのではないかと予想し、ひたすらx8くらいまでa,bのまま計算して規則性を探ったがわからず発狂していたが、残り20分くらいで行列の計算に持ち込んでダブリングをすれば終わるということに気づいた。

その場で行列の掛け算を実装したのでだるかった。ライブラリ実装しておく。

こういう感じの、整数をbitに分解するコードを持っているとダブリングがやりやすくなりますし、xor系の問題でも活躍することがあってお得感があります。

残り2分で提出。

fn bin_digits(n: usize) -> Vec<bool> {
    if n == 0 {
        return vec![];
    }
    let logN = (n as f64).log2().floor() as usize;
    let mut res = vec![false; logN + 1];
    let mut n = n;
    for k in (0..logN + 1).rev() {
        if n >= 1 << k {
            res[k] = true;
            n -= (1 << k);
        }
    }
    res
}