結果

問題 No.3158 Collect Stamps
ユーザー Theta
提出日時 2025-05-30 14:55:40
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,635 bytes
コンパイル時間 13,219 ms
コンパイル使用メモリ 403,868 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-30 14:55:55
合計ジャッジ時間 14,128 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: trait `DisplayVec` is never used
  --> src/main.rs:20:7
   |
20 | trait DisplayVec<T> {
   |       ^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `mod_pow` is never used
  --> src/main.rs:88:4
   |
88 | fn mod_pow(num: i64, index_: i64, mod_: i64) -> i64 {
   |    ^^^^^^^

warning: function `combinations` is never used
  --> src/main.rs:99:4
   |
99 | fn combinations<T, F>(
   |    ^^^^^^^^^^^^

ソースコード

diff # 

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::fmt::Debug;
#[allow(unused_imports)]
use std::iter::{Flatten, FromIterator};
#[allow(unused_imports)]
use std::ops::Index;
#[allow(unused_imports)]
use std::vec::IntoIter;
use std::{cmp::Reverse, collections::BinaryHeap};

trait DisplayVec<T> {
    fn print(&self, sep: &str);
}

impl<T> DisplayVec<T> for Vec<T>
where
    T: ToString,
{
    fn print(&self, sep: &str) {
        println!(
            "{}",
            self.iter()
                .map(std::string::ToString::to_string)
                .collect::<Vec<_>>()
                .join(sep)
        )
    }
}
#[allow(dead_code)]
fn print_chars(input_: &[char]) {
    println!("{}", &input_.iter().collect::<String>())
}
#[allow(dead_code)]
fn ctoi(c: &char) -> i32 {
    *c as i32 - 48
}
#[allow(dead_code)]
#[allow(non_snake_case)]
fn YESNO(res: bool) {
    if res {
        println!("YES")
    } else {
        println!("NO")
    }
}
#[allow(dead_code)]
#[allow(non_snake_case)]
fn YesNo(res: bool) {
    if res {
        println!("Yes")
    } else {
        println!("No")
    }
}
#[allow(dead_code)]
fn yesno(res: bool) {
    if res {
        println!("yes")
    } else {
        println!("no")
    }
}

#[allow(unused_macros)]
macro_rules! input_arrays_with_len {
    ($e:expr, $t:ty) => {
        (0..$e)
            .map(|_| {
                input! {
                    l: u32,
                    nums: [$t; l]
                }
                nums
            })
            .collect_vec()
    };
}

fn mod_pow(num: i64, index_: i64, mod_: i64) -> i64 {
    if index_ == 0 {
        return 1;
    }
    if index_ % 2 == 0 {
        return mod_pow((num * num) % mod_, index_ / 2, mod_);
    } else {
        return num * mod_pow(num, index_ - 1, mod_) % mod_;
    }
}

fn combinations<T, F>(
    origin: &Vec<Vec<T>>,
    cur_idx: usize,
    cur_rest: usize,
    cur_array: &mut Vec<usize>,
    func: &F,
) -> i64
where
    F: Fn(&Vec<Vec<T>>, &Vec<usize>) -> bool,
{
    if cur_rest == 0 {
        return func(origin, &cur_array) as i64;
    }
    if cur_idx + cur_rest > origin.len() {
        return 0;
    }
    let mut ans = combinations(origin, cur_idx + 1, cur_rest, cur_array, func);

    if cur_rest > 0 {
        cur_array.push(cur_idx);
        ans += combinations(origin, cur_idx + 1, cur_rest - 1, cur_array, func);
        cur_array.pop();
    }

    ans
}

fn main() {
    input! {
        n: u8, m: u8, k: u32,
        goals: [Usize1; k],
        times: [[i64; n];n],
    }

    let mut q = BinaryHeap::new();
    let mut dists_min = HashMap::new();
    for start in 0..n {
        q.push(Reverse((0, (1 << start) as i64, start)));
        dists_min.insert(((1 << start as i64), start), 0);
    }

    let goals_bit = goals.iter().map(|idx| 1 << idx).sum::<i64>();

    while let Some(Reverse((cur_time, visited_bits, cur_pos))) = q.pop() {
        if dists_min.get(&(visited_bits, cur_pos)).unwrap_or(&i64::MAX) < &cur_time {
            continue;
        }

        *dists_min.entry((visited_bits, cur_pos)).or_insert(i64::MAX) = cur_time;

        if ((goals_bit & (1 << cur_pos)) > 0) && (visited_bits.count_ones() >= m as u32) {
            println!("{}", cur_time);
            return;
        }
        if visited_bits.count_ones() >= m as u32 {
            for &goal_idx in goals.iter() {
                let next_time = cur_time + times[cur_pos as usize][goal_idx];
                let next_visited = visited_bits | (1 << goal_idx);
                if dists_min
                    .get(&(next_visited, goal_idx as u8))
                    .unwrap_or(&i64::MAX)
                    < &next_time
                {
                    continue;
                }
                q.push(Reverse((next_time, next_visited, goal_idx as u8)));
            }
        } else {
            for next_pos in 0..n {
                if visited_bits & (1 << next_pos) > 0 {
                    continue;
                }
                let next_visited = visited_bits | (1 << next_pos);
                let next_time = cur_time + times[cur_pos as usize][next_pos as usize];
                if dists_min
                    .get(&(next_visited, next_pos))
                    .unwrap_or(&i64::MAX)
                    < &next_time
                {
                    continue;
                }
                q.push(Reverse((next_time, next_visited, next_pos)));
            }
        }
    }
}
0