結果

問題 No.3 ビットすごろく
コンテスト
ユーザー srtry
提出日時 2025-05-05 04:02:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 1,685 bytes
コンパイル時間 12,931 ms
コンパイル使用メモリ 406,920 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-05 04:02:27
合計ジャッジ時間 14,533 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* 
 *     Author:  srtry
 *     Created: 2025-05-05T02:26:22+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::io::{stdout,Write,BufWriter};
use std::collections::VecDeque;

fn main() {
    input!{
        n:usize
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    
    let mut dp:Vec<Option<usize>> = vec![None;n+1];
    let mut set:VecDeque<usize> = VecDeque::from([1]);
    dp[1] = Some(1);
    let mut pos:Option<usize>;
    loop {
        pos = set.pop_front();
        match pos {
            Some(x) => {
                let step:usize = x.count_ones() as usize;
                if x+step <= n {
                    match dp[x+step] {
                        None => {
                            dp[x+step] = Some(dp[x].unwrap() + 1);
                            set.push_back(x+step);
                            if x+step == n {
                                break;
                            }
                        },
                        Some(_) => (),
                    }
                }
                if x-step > 0 {
                    match dp[x-step] {
                        None => {
                            dp[x-step] = Some(dp[x].unwrap() + 1);
                            set.push_back(x-step);
                            if x-step == n {
                                break;
                            }
                        },
                        Some(_) => (),
                    }
                }
            },
            None => break,
        }
    }

    match dp[n] {
        Some(x) => write!(out, "{}", x).unwrap(),
        None => write!(out, "-1").unwrap(),
    }
}
0