結果

問題 No.262 面白くないビットすごろく
コンテスト
ユーザー akakimidori
提出日時 2026-05-09 19:59:40
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,193 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,127 ms
コンパイル使用メモリ 196,524 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-09 19:59:52
合計ジャッジ時間 6,137 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() {
    proconio::input!(n: usize);
    let mut x = 1usize;
    let mut cnt = 1;
    let mut map = Map::new();
    for i in (0..40).rev() {
        if n >> i & 1 == 1 && x >> i & 1 == 0 {
            let b = (x >> i).count_ones() as usize;
            let c = x & ((1 << i) - 1);
            let p = dfs(i, b, c, &mut map);
            x += p.1;
            cnt += p.0;
        }
    }
    if x == n {
        println!("{cnt}");
    } else {
        println!("-1");
    }
}

type Map<K, V> = std::collections::HashMap<K, V>;

// 2^a まで決めた、暫定桁和b, +c して始める、2^aに寄与発生するまでに足す回数、足される値
fn dfs(
    a: usize,
    b: usize,
    c: usize,
    map: &mut Map<(usize, usize, usize), (usize, usize)>,
) -> (usize, usize) {
    assert!(b + c > 0);
    if c >= 1 << a {
        return (0, 0);
    }
    if a == 0 {
        return (1, b);
    }
    if let Some(&v) = map.get(&(a, b, c)) {
        return v;
    }
    let mut p = dfs(a - 1, b, c, map);
    if c + p.1 < (1 << a) {
        let q = dfs(a - 1, b + 1, c + p.1 - (1 << (a - 1)), map);
        p.0 += q.0;
        p.1 += q.1;
    }
    map.insert((a, b, c), p);
    p
}
0