提出 #63393965

---

ソースコード 拡げる

use std::{
    cmp::Reverse,
    collections::{BinaryHeap, HashSet, VecDeque},
    hash::{BuildHasherDefault, Hasher},
    process::exit,
};

use itertools::Itertools;
use proconio::input;
use rand::{Rng, SeedableRng};
use rand_pcg::Pcg64Mcg;

const TIME_LIMIT_SEC: f64 = 1.95;
const N: usize = 20;
const M_MAX: usize = 3;
const UDLR: [char; 4] = ['U', 'D', 'L', 'R'];
const DXDY: [(usize, usize); 4] = [(usize::MAX, 0), (1, 0), (0, usize::MAX), (0, 1)];

const WARN_TIME_SEC: f64 = 0.75 * TIME_LIMIT_SEC;
const A: u8 = 3;
const B: u8 = 4;
const C: u8 = 5;
const WALL: u8 = 6;
const ROCK: u8 = 7;
const EMPTY: u8 = 8;

const FALL_BONUS: Cost = 30;
const DIST_MIN_W: Cost = 16; // A: 16, B: 12, C: 14
const DIST_MAX_W: Cost = 1;
const ROCK_CROSS_W: Cost = 5;
const ROCK_W: Cost = 70;
const STD_W: f64 = 50.0; // A: 50.0, B: 25.0, C: 40.0

fn main() {
    get_time_sec();

    let input = Input::read();
    let config = Config {
        max_turn: 10000,
        beam_width: 18000,
        tour_capacity: 1 << 16,
        hash_que_turn: 8,
    };
    let state = State::new(&input);

    let actions = beam_search(&config, state);

    for action in actions {
        let op = match action.op {
            Op::Move => 1,
            Op::Carry => 2,
            Op::Roll => 3,
            Op::Nop => unreachable!(),
        };
        println!("{} {}", op, UDLR[action.dir as usize]);
    }

    exit(0);
}

fn char_to_u8(c: char) -> u8 {
    match c {
        'a' => 0,
        'b' => 1,
        'c' => 2,
        'A' => A,
        'B' => B,
        'C' => C,
        '#' => WALL,
        '@' => ROCK,
        '.' => EMPTY,
        _ => unreachable!(),
    }
}

fn is_hole_or_wall(c: u8) -> bool {
    3 <= c && c <= 6
}

type Cost = i32;
type Hash = u64;

// beam search setting
// capacity = 0 is OK.
#[derive(Debug, Clone)]
pub struct Config {
    max_turn: usize,
    beam_width: usize,
    tour_capacity: usize,
    hash_que_turn: usize,
}

#[derive(Debug, Clone, PartialEq, Eq)]
enum Op {
    Move,
    Carry,
    Roll,
    Nop,
}

// data for a state transition
// Try to minimize memory usage.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Action {
    x: u8,
    y: u8,
    op: Op,
    dir: u8,
    bx: u8, // block x
    by: u8, // block y
}

impl Action {
    fn next_pos(&self) -> (usize, usize) {
        match self.op {
            Op::Move | Op::Carry => {
                let (dx, dy) = DXDY[self.dir as usize];
                let x = (self.x as usize).wrapping_add(dx);
                let y = (self.y as usize).wrapping_add(dy);
                (x, y)
            }
            _ => (self.x as usize, self.y as usize),
        }
    }
}

// data for an expansion node
#[derive(Debug, Clone)]
struct Candidate {
    action: Action,
    cost: Cost,
    hash: Hash,
    parent: u32,
}

// erasable max priority queue
#[derive(Debug, Clone)]
struct SegmentTree {
    n: usize,
    log: usize,
    size: usize,
    d: Vec<(Cost, usize)>,
}

impl SegmentTree {
    fn new(n: usize) -> Self {
        let mut ret = Self {
            n: 0,
            log: 0,
            size: 0,
            d: Vec::new(),
        };
        ret.init(n);
        ret
    }

    fn init(&mut self, n: usize) {
        self.n = n;
        self.size = n.next_power_of_two();
        self.log = self.size.trailing_zeros() as usize;
        self.d.clear();
        self.d.resize(2 * self.size, (Cost::MIN, usize::MAX));
    }

    fn build(&mut self, candidates: &Vec<Candidate>) {
        self.init(candidates.len());
        for i in 0..self.n {
            self.d[self.size + i] = (candidates[i].cost, i);
        }
        for i in (1..self.size).rev() {
            self.update(i);
        }
    }

    fn set(&mut self, p: usize, cost: Cost) {
        debug_assert!(p < self.n);
        let q = p + self.size;
        self.d[q] = (cost, p);
        for i in 1..=self.log {
            self.update(q >> i);
        }
    }

    fn top(&self) -> (Cost, usize) {
        self.d[1]
    }

    fn update(&mut self, k: usize) {
        let (c0, p0) = self.d[2 * k];
        let (c1, p1) = self.d[2 * k + 1];
        self.d[k] = if c0 >= c1 { (c0, p0) } else { (c1, p1) };
    }
}

// select beam width candidates from better evaluation
// It remains only the best one for same hash candidates.
#[derive(Debug, Clone)]
struct Selector {
    beam_width: usize,
    max_beam_width: usize,
    hash_que_size: usize,
    candidates: Vec<Candidate>,
    hashes: NoHashSet,
    hash_que: VecDeque<Hash>,
    segtree: SegmentTree,
    finished_candidate: Option<Candidate>,
}

impl Selector {
    fn new(beam_width: usize, hash_que_turn: usize) -> Self {
        let hash_que_size = beam_width * hash_que_turn;
        Self {
            beam_width,
            max_beam_width: beam_width,
            hash_que_size,
            candidates: Vec::with_capacity(beam_width),
            hashes: NoHashSet::default(),
            hash_que: VecDeque::with_capacity(hash_que_size),
            segtree: SegmentTree::new(beam_width),
            finished_candidate: None,
        }
    }

    // add a candidate
    // finished = true iff it can get feasible solution through the candidate in the turn minimizing problem.
    // It returns true iff it provisionally accept the candidate.
    #[inline(always)]
    fn push(&mut self, candidate: Candidate, finished: bool) -> bool {
        let cost = candidate.cost;
        if finished {
            self.finished_candidate = Some(candidate);
            return true;
        }
        if self.built_segtree() && cost >= self.segtree.top().0 {
            return false;
        }
        let hash = candidate.hash;
        if !self.hashes.insert(hash) {
            return false;
        }
        self.hash_que.push_back(hash);

        if self.built_segtree() {
            let p = self.segtree.top().1;
            self.candidates[p] = candidate;
            self.segtree.set(p, cost);
        } else {
            self.candidates.push(candidate);
            if self.built_segtree() {
                // candidates become full
                self.segtree.build(&self.candidates);
            }
        }
        true
    }

    fn clear(&mut self) {
        self.candidates.clear();
        self.finished_candidate = None;

        for _ in self.hash_que_size..self.hash_que.len() {
            let hash = self.hash_que.pop_front().unwrap();
            self.hashes.remove(&hash);
        }

        if get_time_sec() > WARN_TIME_SEC {
            self.beam_width = self.max_beam_width / 2;
        }
    }

    fn built_segtree(&self) -> bool {
        self.candidates.len() == self.beam_width
    }
}

#[derive(Debug, Clone)]
pub struct State {
    num_ore_type: usize,
    holes: [(usize, usize); M_MAX],
    hashes: [[Hash; N + 2]; N + 2],
    dists: [[[Cost; N + 2]; N + 2]; M_MAX],
    grid: [[u8; N + 2]; N + 2],
    num_ore: usize,
    x_sum: usize,
    x2_sum: usize,
    y_sum: usize,
    y2_sum: usize,
}

// data updated in depth first search
impl State {
    pub fn new(input: &Input) -> Self {
        let mut rng = Pcg64Mcg::seed_from_u64(0);

        let mut hashes = [[0; N + 2]; N + 2];
        for x in 1..=N {
            for y in 1..=N {
                hashes[x][y] = rng.gen();
            }
        }

        let mut ret = Self {
            num_ore_type: input.num_ore_type,
            holes: input.holes,
            hashes,
            dists: [[[Cost::MAX; N + 2]; N + 2]; M_MAX],
            grid: input.grid,
            num_ore: 0,
            x_sum: 0,
            x2_sum: 0,
            y_sum: 0,
            y2_sum: 0,
        };
        ret.init_dists();
        ret.init_sum();
        ret
    }

    fn init_sum(&mut self) {
        for x in 1..=N {
            for y in 1..=N {
                let gxy = self.grid[x][y] as usize;
                if gxy < M_MAX {
                    self.num_ore += 1;
                    self.x_sum += x;
                    self.x2_sum += x * x;
                    self.y_sum += y;
                    self.y2_sum += y * y;
                }
            }
        }
    }

    fn init_dists(&mut self) {
        let mut que = BinaryHeap::new();
        for ore in 0..self.num_ore_type {
            loop {
                self.dists[ore] = [[Cost::MAX; N + 2]; N + 2];
                let mut preds = [[(usize::MAX, usize::MAX); N + 2]; N + 2];

                let (sx, sy) = self.holes[ore];
                self.dists[ore][sx][sy] = 0;
                for (dx, dy) in DXDY {
                    let mut x = sx.wrapping_add(dx);
                    let mut y = sy.wrapping_add(dy);
                    let mut dist = FALL_BONUS + DIST_MAX_W;
                    loop {
                        if is_hole_or_wall(self.grid[x][y]) {
                            break;
                        }
                        if self.grid[x][y] == ROCK {
                            dist += ROCK_CROSS_W;
                        }
                        self.dists[ore][x][y] = dist;
                        preds[x][y] = (x.wrapping_sub(dx), y.wrapping_sub(dy));
                        que.push((Reverse(dist), x, y));
                        x = x.wrapping_add(dx);
                        y = y.wrapping_add(dy);
                        dist += DIST_MAX_W;
                    }
                }
                // Dijkstra
                let mut update_rock = false;
                while let Some((Reverse(dist), x, y)) = que.pop() {
                    if self.dists[ore][x][y] < dist {
                        continue;
                    }
                    if self.grid[x][y] < M_MAX as u8 {
                        // restore path
                        let mut px = x;
                        let mut py = y;
                        while px != sx || py != sy {
                            let (qx, qy) = preds[px][py];
                            if self.grid[qx][qy] == ROCK {
                                // convert rock to ore
                                self.grid[qx][qy] = ore as u8;
                                update_rock = true;
                            }
                            px = qx;
                            py = qy;
                        }
                    }
                    for (dx, dy) in DXDY {
                        let nx = x.wrapping_add(dx);
                        let ny = y.wrapping_add(dy);
                        if is_hole_or_wall(self.grid[nx][ny]) {
                            continue;
                        }
                        let mut ndist = dist + DIST_MIN_W;
                        if self.grid[nx][ny] == ROCK {
                            ndist += ROCK_W;
                        }
                        if self.dists[ore][nx][ny].chmin(ndist) {
                            preds[nx][ny] = (x, y);
                            que.push((Reverse(ndist), nx, ny));
                        }
                    }
                }
                if !update_rock {
                    break;
                }
            }
        }
    }

    fn calc_std_cost(&self, num_ore: usize, x_sum: usize, x2_sum: usize, y_sum: usize, y2_sum: usize) -> Cost {
        if num_ore == 0 {
            return 0;
        }
        let x_var = x2_sum as f64 / num_ore as f64 - (x_sum as f64 / num_ore as f64).powi(2);
        let x_std = x_var.sqrt();
        let y_var = y2_sum as f64 / num_ore as f64 - (y_sum as f64 / num_ore as f64).powi(2);
        let y_std = y_var.sqrt();
        ((x_std + y_std) * STD_W) as i32
    }

    // return the initial value of Evaluator and Hash
    fn get_initial_data(&self) -> (Cost, Action, Hash) {
        let mut cost = self.calc_std_cost(self.num_ore, self.x_sum, self.x2_sum, self.y_sum, self.y2_sum);
        let mut hash = 0;
        for x in 1..=N {
            for y in 1..=N {
                let gxy = self.grid[x][y] as usize;
                if gxy >= M_MAX {
                    continue;
                }
                cost += self.dists[gxy][x][y];
                hash ^= self.hashes[x][y];
            }
        }
        let (sx, sy) = self.holes[0];
        hash ^= self.hashes[sx][sy] >> 1;

        let action = Action {
            x: sx as u8,
            y: sy as u8,
            op: Op::Nop,
            dir: 0,
            bx: 0,
            by: 0,
        };

        (cost, action, hash)
    }

    // add candidates to selector
    // argument
    // - evaluator: current evaluator
    // - action: action to move to current state
    // - hash: current hash
    // - parent: current node ID (parent node ID for next state)
    fn expand(
        &self,
        cost: Cost,
        action: &Action,
        mut hash: Hash,
        parent: u32,
        selector: &mut Selector,
    ) {
        let (px, py) = action.next_pos();
        hash ^= self.hashes[px][py] >> 1;

        // move
        for dir in 0..4 {
            let (dx, dy) = DXDY[dir];
            let nx = px.wrapping_add(dx);
            let ny = py.wrapping_add(dy);
            let gn = self.grid[nx][ny];
            if gn == WALL {
                continue;
            }
            let naction = Action {
                x: px as u8,
                y: py as u8,
                op: Op::Move,
                dir: dir as u8,
                bx: 0,
                by: 0,
            };
            let candidate = Candidate {
                action: naction,
                cost,
                hash: hash ^ (self.hashes[nx][ny] >> 1),
                parent,
            };
            selector.push(candidate, false);
        }

        let gp = self.grid[px][py] as usize;
        if gp >= M_MAX {
            // cannot pick up ore
            return;
        }
        let cost = cost - self.calc_std_cost(self.num_ore, self.x_sum, self.x2_sum, self.y_sum, self.y2_sum);
        let x_sum = self.x_sum - px;
        let x2_sum = self.x2_sum - px * px;
        let y_sum = self.y_sum - py;
        let y2_sum = self.y2_sum - py * py;

        // carry
        for dir in 0..4 {
            let (dx, dy) = DXDY[dir];
            let bx = px.wrapping_add(dx);
            let by = py.wrapping_add(dy);
            let gb = self.grid[bx][by] as usize;
            if gb != EMPTY as usize && gb != gp + M_MAX {
                continue;
            }
            let naction = Action {
                x: px as u8,
                y: py as u8,
                op: Op::Carry,
                dir: dir as u8,
                bx: bx as u8,
                by: by as u8,
            };
            let mut ncost = cost;
            let mut nhash = hash ^ (self.hashes[bx][by] >> 1);
            ncost -= self.dists[gp][px][py];
            nhash ^= self.hashes[px][py];
            if gb == EMPTY as usize {
                ncost += self.dists[gp][bx][by];
                nhash ^= self.hashes[bx][by];
                ncost += self.calc_std_cost(self.num_ore, x_sum + bx, x2_sum + bx * bx, y_sum + by, y2_sum + by * by);
            } else {
                ncost += self.calc_std_cost(self.num_ore - 1, x_sum, x2_sum, y_sum, y2_sum);
            }
            let finished = ncost == 0;
            if finished {
                debug_assert_eq!(nhash, self.hashes[bx][by] >> 1);
            }
            let candidate = Candidate {
                action: naction,
                cost: ncost,
                hash: nhash,
                parent,
            };
            selector.push(candidate, finished);
        }

        // roll
        hash ^= self.hashes[px][py] >> 1;
        for dir in 0..4 {
            let (bx, by) = self.roll_ore(px, py, gp, dir);
            if bx == px && by == py {
                continue;
            }
            let naction = Action {
                x: px as u8,
                y: py as u8,
                op: Op::Roll,
                dir: dir as u8,
                bx: bx as u8,
                by: by as u8,
            };
            let mut ncost = cost;
            let mut nhash = hash;
            ncost -= self.dists[gp][px][py];
            nhash ^= self.hashes[px][py];
            if self.grid[bx][by] == EMPTY {
                ncost += self.dists[gp][bx][by];
                nhash ^= self.hashes[bx][by];
                ncost += self.calc_std_cost(self.num_ore, x_sum + bx, x2_sum + bx * bx, y_sum + by, y2_sum + by * by);
            } else {
                ncost += self.calc_std_cost(self.num_ore - 1, x_sum, x2_sum, y_sum, y2_sum);
            }
            let finished = ncost == 0;
            if finished {
                debug_assert_eq!(nhash, self.hashes[px][py] >> 1);
            }
            let candidate = Candidate {
                action: naction,
                cost: ncost,
                hash: nhash,
                parent,
            };
            selector.push(candidate, finished);
        }
    }

    fn roll_ore(&self, sx: usize, sy: usize, g: usize, dir: usize) -> (usize, usize) {
        let (dx, dy) = DXDY[dir];
        let mut x = sx;
        let mut y = sy;
        loop {
            let nx = x.wrapping_add(dx);
            let ny = y.wrapping_add(dy);
            let gn = self.grid[nx][ny];
            if gn == EMPTY {
                x = nx;
                y = ny;
            } else if gn as usize == g + M_MAX {
                // drop ore to correct hole
                return (nx, ny);
            } else if A <= gn && gn <= C {
                // drop ore to wrong hole
                return (sx, sy);
            } else {
                // collide
                return (x, y);
            }
        }
    }

    fn move_forward(&mut self, action: &Action) {
        // update grid
        match action.op {
            Op::Carry | Op::Roll => {
                let px = action.x as usize;
                let py = action.y as usize;
                let gp = self.grid[px][py] as usize;
                debug_assert!(gp < M_MAX);
                self.grid[px][py] = EMPTY;

                self.x_sum -= px;
                self.x2_sum -= px * px;
                self.y_sum -= py;
                self.y2_sum -= py * py;

                let bx = action.bx as usize;
                let by = action.by as usize;
                let gbx = self.grid[bx][by] as usize;
                if gbx == gp + M_MAX {
                    // drop ore to hole
                    self.num_ore -= 1;
                } else {
                    debug_assert_eq!(gbx, EMPTY as usize);
                    self.grid[bx][by] = gp as u8;

                    self.x_sum += bx;
                    self.x2_sum += bx * bx;
                    self.y_sum += by;
                    self.y2_sum += by * by;
                }
            }
            _ => (),
        }
    }

    fn move_backward(&mut self, action: &Action) {
        // update grid
        match action.op {
            Op::Carry | Op::Roll => {
                let px = action.x as usize;
                let py = action.y as usize;
                debug_assert_eq!(self.grid[px][py], EMPTY);

                self.x_sum += px;
                self.x2_sum += px * px;
                self.y_sum += py;
                self.y2_sum += py * py;

                let bx = action.bx as usize;
                let by = action.by as usize;
                let gbx = self.grid[bx][by] as usize;
                if gbx < M_MAX {
                    self.grid[px][py] = gbx as u8;
                    self.grid[bx][by] = EMPTY;

                    self.x_sum -= bx;
                    self.x2_sum -= bx * bx;
                    self.y_sum -= by;
                    self.y2_sum -= by * by;
                } else {
                    // pick up ore from hole
                    debug_assert!(gbx < 2 * M_MAX);
                    self.grid[px][py] = (gbx - M_MAX) as u8;
                    self.num_ore += 1;
                }
            }
            _ => (),
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
enum EdgeProperty {
    Leaf,
    Forward,
    Backward,
}

#[derive(Debug, Clone)]
struct Edge {
    property: EdgeProperty,
    action: Action,
}

#[derive(Debug, Clone)]
struct Tree {
    state: State,
    curr_tour: Vec<Edge>,
    next_tour: Vec<Edge>,
    leaves: Vec<(Cost, Hash)>,
    buckets: Vec<Vec<(Action, Cost, Hash)>>,
    direct_road: Vec<Action>,
}

impl Tree {
    fn new(state: State, config: &Config) -> Self {
        Self {
            state,
            curr_tour: Vec::with_capacity(config.tour_capacity),
            next_tour: Vec::with_capacity(config.tour_capacity),
            leaves: Vec::with_capacity(config.beam_width as usize),
            buckets: vec![vec![]; config.beam_width as usize],
            direct_road: Vec::new(),
        }
    }

    // add candidates to selector while updating state
    fn dfs(&mut self, selector: &mut Selector) {
        if self.curr_tour.is_empty() {
            // the first turn
            let (cost, action, hash) = self.state.get_initial_data();
            self.state.expand(cost, &action, hash, 0, selector);
            return;
        }

        let mut leaf_id = 0;
        for edge in &self.curr_tour {
            match edge.property {
                EdgeProperty::Leaf => {
                    let (cost, hash) = self.leaves[leaf_id];
                    self.state.move_forward(&edge.action);
                    self.state
                        .expand(cost, &edge.action, hash, leaf_id as u32, selector);
                    self.state.move_backward(&edge.action);
                    leaf_id += 1;
                }
                EdgeProperty::Forward => self.state.move_forward(&edge.action),
                EdgeProperty::Backward => self.state.move_backward(&edge.action),
            }
        }
    }

    // add new nodes and remove useless nodes
    fn update(&mut self, candidates: &Vec<Candidate>) {
        self.leaves.clear();

        if self.curr_tour.is_empty() {
            // no branch
            self.curr_tour.clear();
            for candidate in candidates {
                self.curr_tour.push(Edge {
                    property: EdgeProperty::Leaf,
                    action: candidate.action.clone(),
                });
                self.leaves.push((candidate.cost, candidate.hash));
            }
            return;
        }

        // bucket sort
        for candidate in candidates {
            self.buckets[candidate.parent as usize].push((
                candidate.action.clone(),
                candidate.cost,
                candidate.hash,
            ));
        }

        let mut curr_tour_id = 0;

        // do not repeat direct road
        let is_direct_road = |curr_tour_id: usize, curr_tour: &Vec<Edge>| {
            curr_tour[curr_tour_id].property == EdgeProperty::Forward
                && curr_tour.last().unwrap().action == curr_tour[curr_tour_id].action
        };
        while is_direct_road(curr_tour_id, &self.curr_tour) {
            let action = self.curr_tour[curr_tour_id].action.clone();
            self.state.move_forward(&action);
            self.direct_road.push(action);
            self.curr_tour.pop();
            curr_tour_id += 1;
        }

        let mut leaf_id = 0;
        for edge in &self.curr_tour[curr_tour_id..] {
            match edge.property {
                EdgeProperty::Leaf => {
                    if self.buckets[leaf_id].is_empty() {
                        leaf_id += 1;
                        continue;
                    }
                    self.next_tour.push(Edge {
                        property: EdgeProperty::Forward,
                        action: edge.action.clone(),
                    });
                    for (action, evaluator, hash) in &self.buckets[leaf_id] {
                        self.next_tour.push(Edge {
                            property: EdgeProperty::Leaf,
                            action: action.clone(),
                        });
                        self.leaves.push((evaluator.clone(), *hash));
                    }
                    self.next_tour.push(Edge {
                        property: EdgeProperty::Backward,
                        action: edge.action.clone(),
                    });
                    self.buckets[leaf_id].clear();
                    leaf_id += 1;
                }
                EdgeProperty::Forward => {
                    self.next_tour.push(edge.clone());
                }
                EdgeProperty::Backward => {
                    if self.next_tour.last().unwrap().property == EdgeProperty::Forward {
                        self.next_tour.pop();
                    } else {
                        self.next_tour.push(edge.clone());
                    }
                }
            }
        }
        std::mem::swap(&mut self.curr_tour, &mut self.next_tour);
        self.next_tour.clear();
    }

    // get the path from the root
    fn get_path(&self, best_leaf_id: usize, turn: usize) -> Vec<Action> {
        // eprintln!("curr_tour.len() = {}", self.curr_tour.capacity());

        let mut ret = self.direct_road.clone();
        ret.reserve(turn);
        let mut leaf_id = 0;
        for edge in &self.curr_tour {
            match edge.property {
                EdgeProperty::Leaf => {
                    if leaf_id == best_leaf_id {
                        ret.push(edge.action.clone());
                        return ret;
                    }
                    leaf_id += 1;
                }
                EdgeProperty::Forward => ret.push(edge.action.clone()),
                EdgeProperty::Backward => {
                    ret.pop();
                }
            }
        }

        panic!("invalid argument: best_leaf_id");
    }
}

pub fn beam_search(config: &Config, state: State) -> Vec<Action> {
    let mut tree = Tree::new(state, config);
    let mut selector = Selector::new(config.beam_width, config.hash_que_turn);

    for turn in 0..config.max_turn {
        tree.dfs(&mut selector);

        if let Some(candidate) = &selector.finished_candidate {
            // find the feasible solution in turn minimizing problem
            let mut ret = tree.get_path(candidate.parent as usize, turn + 1);
            ret.push(candidate.action.clone());
            return ret;
        }

        debug_assert!(!selector.candidates.is_empty());

        tree.update(&selector.candidates);
        selector.clear();
    }

    unreachable!();
}

#[derive(Debug, Clone)]
pub struct Input {
    num_ore_type: usize,
    grid: [[u8; N + 2]; N + 2],
    holes: [(usize, usize); M_MAX],
}

impl Input {
    fn read() -> Self {
        input! {
            n: usize,
            m: usize,
            c: [String; n],
        }
        debug_assert_eq!(n, N);

        let c = c.iter().map(|s| s.chars().collect_vec()).collect_vec();
        let mut grid = [[WALL; N + 2]; N + 2];
        for x in 0..n {
            for y in 0..n {
                grid[x + 1][y + 1] = char_to_u8(c[x][y]);
            }
        }

        let mut holes = [(usize::MAX, usize::MAX); 3];
        for x in 1..=N {
            for y in 1..=N {
                if grid[x][y] == A {
                    holes[0] = (x, y);
                } else if grid[x][y] == B {
                    holes[1] = (x, y);
                } else if grid[x][y] == C {
                    holes[2] = (x, y);
                }
            }
        }

        Self {
            num_ore_type: m,
            grid,
            holes,
        }
    }
}

#[derive(Default)]
struct NoHashHasher {
    value: u64,
}

impl Hasher for NoHashHasher {
    fn write(&mut self, bytes: &[u8]) {
        self.value = u64::from_ne_bytes(bytes[..8].try_into().unwrap());
    }

    fn finish(&self) -> u64 {
        self.value
    }
}

type NoHashSet = HashSet<u64, BuildHasherDefault<NoHashHasher>>;

pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: T) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }

    fn chmax(&mut self, x: T) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}

pub fn get_time_sec() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

提出情報

ジャッジ結果