#860285 (Rust) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
コンテスト
ユーザー	shim0
提出日時	2023-04-16 18:09:16
言語	Rust (1.83.0 + proconio)
結果	MLE
実行時間	-
コード長	18,542 bytes
コンパイル時間	3,782 ms
実行使用メモリ	819,200 KB
スコア	0
最終ジャッジ日時	2023-04-16 18:09:22
合計ジャッジ時間	4,865 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	MLE * 1 -- * 99

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused macro definition: `input`
   --> Main.rs:589:14
    |
589 | macro_rules! input {
    |              ^^^^^
    |
    = note: `#[warn(unused_macros)]` on by default

warning: unused variable: `h`
  --> Main.rs:36:20
   |
36 |         let (n, d, h) = (ndh[0], ndh[1] as u32, ndh[2]);
   |                    ^ help: if this is intentional, prefix it with an underscore: `_h`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: field `key` is never read
  --> Main.rs:27:5
   |
24 | struct Labyrinth {
   |        --------- field in this struct
...
27 |     key: (usize, usize),
   |     ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: 3 warnings emitted

ソースコード

raw source code

// use bitset_fixed::BitSet;
// use proconio::input;
// use proconio::marker::Chars;
use std::collections::VecDeque;

#[derive(Debug, Clone)]
struct State {
    is_checked: bool,
    jewelry_bitset: BitSet,
    hp: i32,
    prev_point: Option<(usize, usize, usize)>,
}
impl State {
    fn new() -> Self {
        Self {
            is_checked: false,
            jewelry_bitset: BitSet::new(500),
            hp: 0,
            prev_point: None,
        }
    }
}

struct Labyrinth {
    n: usize,
    start: (usize, usize),
    key: (usize, usize),
    goal: (usize, usize),
    board: Vec<Vec<char>>,
    damage: Vec<Vec<Vec<i32>>>,
    jewelry_num: Vec<Vec<usize>>,
}
impl Labyrinth {
    fn new() -> Self {
        let ndh: Vec<usize> = read_vec();
        let (n, d, h) = (ndh[0], ndh[1] as u32, ndh[2]);
        let mut board: Vec<Vec<char>> = vec![];
        for _ in 0..n {
            let board_i: String = read();
            board.push(board_i.chars().collect());
        }
        let m: usize = read();
        let mut yxd = vec![];
        for _ in 0..m {
            let yxd_i: Vec<usize> = read_vec();
            yxd.push((yxd_i[0], yxd_i[1], yxd_i[2]));
        }


        let mut start = (0, 0);
        let mut key = (0, 0);
        let mut goal = (0, 0);
        let mut jewelry_num = vec![vec![0; n]; n];
        let mut num = 1;
        for x in 0..n {
            for y in 0..n {
                match board[x][y] {
                    'S' => start = (x, y),
                    'K' => key = (x, y),
                    'G' => goal = (x, y),
                    'J' => {
                        jewelry_num[x][y] = num;
                        num += 1;
                    }
                    _ => (),
                }
            }
        }
        
        let mut damage = vec![vec![vec![0; 60]; 60]; 60];
        for &(y, x, step) in yxd.iter() {
            for i in 1..60 {
                if i <= x && board[x - i][y] != '#' && board[x - i][y] != 'E' {
                    for j in (0..60).step_by(step) {
                        damage[x - i][y][j] += d as i32;
                    }
                } else {
                    break;
                }
            }
            for i in 1..60 {
                if x + i < 60 && board[x + i][y] != '#' && board[x + i][y] != 'E' {
                    for j in (0..60).step_by(step) {
                        damage[x + i][y][j] += d as i32;
                    }
                } else {
                    break;
                }
            }
            for i in 1..60 {
                if i <= y && board[x][y - i] != '#' && board[x][y - i] != 'E' {
                    for j in (0..60).step_by(step) {
                        damage[x][y - i][j] += d as i32;
                    }
                } else {
                    break;
                }
            }
            for i in 1..60 {
                if y + i < 60 && board[x][y + i] != '#' && board[x][y + i] != 'E' {
                    for j in (0..60).step_by(step) {
                        damage[x][y + i][j] += d as i32;
                    }
                } else {
                    break;
                }
            }
        }

        Self {
            n,
            start,
            key,
            goal,
            board,
            damage,
            jewelry_num,
        }
    }
}
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let labyrinth = Labyrinth::new();

    let mut dp1 = vec![vec![vec![State::new(); 1500]; 60]; 60]; // start -> key
    let mut dp2 = vec![vec![vec![State::new(); 1500]; 60]; 60]; // key -> goal

    let mut q = VecDeque::new(); // (x, y, t, dp_type)
    let (start_x, start_y) = labyrinth.start;
    dp1[start_x][start_y][0].hp = 1500;
    dp1[start_x][start_y][0].is_checked = true;
    q.push_back((start_x, start_y, 0, 1));
    while let Some((x, y, t, dp_type)) = q.pop_front() {
        if t + 1 == 1500 {
            continue;
        }
        for &(dx, dy) in &[(0, 0), (1, 0), (0, 1), (!0, 0), (0, !0)] {
            let new_x = x + dx;
            let new_y = y + dy;
            if new_x < labyrinth.n && new_y < labyrinth.n && labyrinth.board[new_x][new_y] != '#' && labyrinth.board[new_x][new_y] != 'E' {
                if dp_type == 1 {
                    if labyrinth.board[new_x][new_y] == 'K' {
                        if !dp2[new_x][new_y][t + 1].is_checked {
                            dp2[new_x][new_y][t + 1].is_checked = true;
                            q.push_back((new_x, new_y, t + 1, 2));
                        }
                        let mut bitset = dp1[x][y][t].jewelry_bitset.clone();
                        if labyrinth.jewelry_num[x][y] > 0 {
                            bitset.set(labyrinth.jewelry_num[x][y], true);
                        }
                        if dp2[new_x][new_y][t + 1].jewelry_bitset.count_ones() <= bitset.count_ones() && dp1[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1 > 0 {
                            dp2[new_x][new_y][t + 1].jewelry_bitset >>= 500;
                            let a = dp1[x][y][t].jewelry_bitset.clone();
                            dp2[new_x][new_y][t + 1].jewelry_bitset |= &a;
                            dp2[new_x][new_y][t + 1].jewelry_bitset.set(labyrinth.jewelry_num[new_x][new_y], true);
                            dp2[new_x][new_y][t + 1].hp = dp1[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1;
                            dp2[new_x][new_y][t + 1].prev_point = Some((x, y, dp_type));
                        }
                    } else {
                        if !dp1[new_x][new_y][t + 1].is_checked {
                            dp1[new_x][new_y][t + 1].is_checked = true;
                            q.push_back((new_x, new_y, t + 1, 1));
                        }
                        let mut bitset = dp1[x][y][t].jewelry_bitset.clone();
                        if labyrinth.jewelry_num[x][y] > 0 {
                            bitset.set(labyrinth.jewelry_num[x][y] , true);
                        }
                        if dp1[new_x][new_y][t + 1].jewelry_bitset.count_ones() <= bitset.count_ones() && dp1[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1 > 0 {
                            dp1[new_x][new_y][t + 1].jewelry_bitset >>= 500;
                            let a = dp1[x][y][t].jewelry_bitset.clone();
                            dp1[new_x][new_y][t + 1].jewelry_bitset |= &a;
                            dp1[new_x][new_y][t + 1].jewelry_bitset.set(labyrinth.jewelry_num[new_x][new_y], true);
                            dp1[new_x][new_y][t + 1].hp = dp1[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1;
                            dp1[new_x][new_y][t + 1].prev_point = Some((x, y, dp_type));
                        }
                    }
                } else { // dp_type == 2
                    if labyrinth.board[new_x][new_y] == 'G' {
                        dp2[new_x][new_y][t + 1].jewelry_bitset = dp2[x][y][t].jewelry_bitset.clone();
                        dp2[new_x][new_y][t + 1].hp = dp2[x][y][t].hp - 1;
                        dp2[new_x][new_y][t + 1].prev_point = Some((x, y, dp_type));
                    } else {
                        if !dp2[new_x][new_y][t + 1].is_checked {
                            dp2[new_x][new_y][t + 1].is_checked = true;
                            q.push_back((new_x, new_y, t + 1, 2));
                        }
                        let mut bitset = dp2[x][y][t].jewelry_bitset.clone();
                        if labyrinth.jewelry_num[x][y] > 0 {
                            bitset.set(labyrinth.jewelry_num[x][y] , true);
                        }
                        if dp2[new_x][new_y][t + 1].jewelry_bitset.count_ones() <= bitset.count_ones() && dp2[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1 > 0 {
                            dp2[new_x][new_y][t + 1].jewelry_bitset >>= 500;
                            let a = dp2[x][y][t].jewelry_bitset.clone();
                            dp2[new_x][new_y][t + 1].jewelry_bitset |= &a;
                            dp2[new_x][new_y][t + 1].jewelry_bitset.set(labyrinth.jewelry_num[new_x][new_y], true);
                            dp2[new_x][new_y][t + 1].hp = dp2[x][y][t].hp - labyrinth.damage[new_x][new_y][(t + 1) % 60] - 1;
                            dp2[new_x][new_y][t + 1].prev_point = Some((x, y, dp_type));
                        }
                    }
                }
            }
        }
    }

    let (goal_x, goal_y) = labyrinth.goal;
    let mut best_t = 0;
    let mut best_score = 0;
    for t in 0..1500 {
        if best_score < dp2[goal_x][goal_y][t].jewelry_bitset.count_ones() {
            best_t = t;
            best_score = dp2[goal_x][goal_y][t].jewelry_bitset.count_ones();
        }
    }
    // println!("{}", best_t);

    let mut output = vec![];
    let mut dp_type = 2;
    let (mut now_x, mut now_y, mut now_t) = (goal_x, goal_y, best_t);
    while now_t != 0 {
        output.push((now_x, now_y));
        if dp_type == 1 {
            (now_x, now_y, dp_type) = dp1[now_x][now_y][now_t].prev_point.unwrap();
        } else {
            (now_x, now_y, dp_type) = dp2[now_x][now_y][now_t].prev_point.unwrap();
        }
        now_t -= 1;
    }

    let mut prev_x = start_x;
    let mut prev_y = start_y;
    for &(x, y) in output.iter().rev() {
        let dx = x as i32 - prev_x as i32;
        let dy = y as i32 - prev_y as i32;
        prev_x = x;
        prev_y = y;
        match (dx, dy) {
            (-1, 0) => println!("M U"),
            (1, 0) => println!("M D"),
            (0, 1) => println!("M R"),
            (0, -1) => println!("M L"),
            (0, 0) => println!("S"),
            _ => unreachable!()
        }
    }
}


const TRUE: &bool = &true;
const FALSE: &bool = &false;

#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
/// Fixed sized bitset
pub struct BitSet {
    buf: Vec<u64>,
    size: usize,
}

impl BitSet {
    /// Construct a new, zero bitset with specified capacity.
    /// This method allocates O(size) bits
    pub fn new(size: usize) -> BitSet {
        BitSet {
            buf: vec![0; (size + 63) / 64],
            size,
        }
    }

    /// Set i-th bit to `b`
    #[inline]
    pub fn set(&mut self, i: usize, b: bool) {
        assert!(i < self.size);
        if b {
            self.buf[i >> 6] |= 1 << (i & 63);
        } else {
            self.buf[i >> 6] &= !(1 << (i & 63));
        }
    }

    /// Get the size of bits
    #[inline]
    pub fn size(&self) -> usize {
        self.size
    }

    /// Get the number of ones
    #[inline]
    pub fn count_ones(&self) -> u32 {
        self.buf.iter().map(|x| x.count_ones()).sum()
    }

    /// Get the number of zeros
    #[inline]
    pub fn count_zeros(&self) -> u32 {
        self.size as u32 - self.count_ones()
    }

    /// Faster left shift and or
    ///
    /// `bitset | (bitset << x)`
    #[inline]
    pub fn shl_or(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            return;
        }

        if r == 0 {
            for i in (q..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } |=
                    *unsafe { self.buf.get_unchecked(i - q) };
            }
        } else {
            for i in (q + 1..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } |=
                    (unsafe { self.buf.get_unchecked(i - q) } << r)
                        | (unsafe { self.buf.get_unchecked(i - q - 1) } >> (64 - r));
            }
            *unsafe { self.buf.get_unchecked_mut(q) } |= unsafe { self.buf.get_unchecked(0) } << r;
        }

        self.chomp();
    }

    /// Get inner buffer
    #[inline]
    pub fn buffer(&self) -> &[u64] {
        &self.buf
    }

    /// Get inner buffer with mutable reference
    #[inline]
    pub fn buffer_mut(&mut self) -> &mut [u64] {
        &mut self.buf
    }

    /// Set tailing bits in inner buffer whose index are greater than size to `0`
    #[inline]
    pub fn chomp(&mut self) {
        let r = self.size & 63;
        if r != 0 {
            if let Some(x) = self.buf.last_mut() {
                let d = 64 - r;
                *x = (*x << d) >> d;
            }
        }
    }
}

impl std::ops::Index<usize> for BitSet {
    type Output = bool;
    #[inline]
    fn index(&self, index: usize) -> &bool {
        assert!(index < self.size);
        [FALSE, TRUE][(self.buf[index >> 6] >> (index & 63)) as usize & 1]
    }
}

impl std::ops::ShlAssign<usize> for BitSet {
    #[inline]
    fn shl_assign(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            for x in &mut self.buf {
                *x = 0;
            }
            return;
        }

        if r == 0 {
            for i in (q..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    *unsafe { self.buf.get_unchecked(i - q) };
            }
        } else {
            for i in (q + 1..self.buf.len()).rev() {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    (unsafe { self.buf.get_unchecked(i - q) } << r)
                        | (unsafe { self.buf.get_unchecked(i - q - 1) } >> (64 - r));
            }
            *unsafe { self.buf.get_unchecked_mut(q) } = unsafe { self.buf.get_unchecked(0) } << r;
        }

        for x in &mut self.buf[..q] {
            *x = 0;
        }

        self.chomp();
    }
}

impl std::ops::Shl<usize> for BitSet {
    type Output = Self;

    #[inline]
    fn shl(mut self, x: usize) -> Self {
        self <<= x;
        self
    }
}

impl<'a> std::ops::Shl<usize> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn shl(self, x: usize) -> Self::Output {
        let mut result = self.clone();
        result <<= x;
        result
    }
}

impl std::ops::ShrAssign<usize> for BitSet {
    #[inline]
    fn shr_assign(&mut self, x: usize) {
        let q = x >> 6;
        let r = x & 63;

        if q >= self.buf.len() {
            for x in &mut self.buf {
                *x = 0;
            }
            return;
        }

        if r == 0 {
            for i in 0..self.buf.len() - q {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    *unsafe { self.buf.get_unchecked(i + q) };
            }
        } else {
            for i in 0..self.buf.len() - q - 1 {
                *unsafe { self.buf.get_unchecked_mut(i) } =
                    (unsafe { self.buf.get_unchecked(i + q) } >> r)
                        | (unsafe { self.buf.get_unchecked(i + q + 1) } << (64 - r));
            }
            let len = self.buf.len();
            *unsafe { self.buf.get_unchecked_mut(len - q - 1) } =
                unsafe { self.buf.get_unchecked(len - 1) } >> r;
        }

        let len = self.buf.len();
        for x in &mut self.buf[len - q..] {
            *x = 0;
        }
    }
}

impl std::ops::Shr<usize> for BitSet {
    type Output = Self;

    #[inline]
    fn shr(mut self, x: usize) -> Self {
        self >>= x;
        self
    }
}

impl<'a> std::ops::Shr<usize> for &'a BitSet {
    type Output = BitSet;

    #[inline]
    fn shr(self, x: usize) -> Self::Output {
        let mut result = self.clone();
        result >>= x;
        result
    }
}

impl<'a> std::ops::BitAndAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitand_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a &= *b;
        }
    }
}

impl<'a> std::ops::BitAnd<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitand(mut self, rhs: &'a Self) -> Self::Output {
        self &= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitAnd<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitand(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result &= rhs;
        result
    }
}

impl<'a> std::ops::BitOrAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitor_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a |= *b;
        }
        self.chomp();
    }
}

impl<'a> std::ops::BitOr<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitor(mut self, rhs: &'a Self) -> Self::Output {
        self |= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitOr<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitor(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result |= rhs;
        result
    }
}

impl<'a> std::ops::BitXorAssign<&'a BitSet> for BitSet {
    #[inline]
    fn bitxor_assign(&mut self, rhs: &'a Self) {
        for (a, b) in self.buf.iter_mut().zip(rhs.buf.iter()) {
            *a ^= *b;
        }
        self.chomp();
    }
}

impl<'a> std::ops::BitXor<&'a BitSet> for BitSet {
    type Output = Self;
    #[inline]
    fn bitxor(mut self, rhs: &'a Self) -> Self {
        self ^= rhs;
        self
    }
}

impl<'a, 'b> std::ops::BitXor<&'b BitSet> for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn bitxor(self, rhs: &'b BitSet) -> Self::Output {
        let mut result = self.clone();
        result ^= rhs;
        result
    }
}

impl std::ops::Not for BitSet {
    type Output = Self;
    #[inline]
    fn not(mut self) -> Self::Output {
        for x in &mut self.buf {
            *x = !*x;
        }
        self.chomp();
        self
    }
}

impl<'a> std::ops::Not for &'a BitSet {
    type Output = BitSet;
    #[inline]
    fn not(self) -> Self::Output {
        !self.clone()
    }
}

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

yukicoder

結果

コンパイルメッセージ

ソースコード