#929399 (Rust) No.5019 Hakai Project

提出ソース

結果

問題	No.5019 Hakai Project
ユーザー	hangry
提出日時	2023-11-18 11:56:50
言語	Rust (1.77.0)
結果	AC
実行時間	2,785 ms / 3,000 ms
コード長	19,777 bytes
コンパイル時間	3,031 ms
コンパイル使用メモリ	204,124 KB
実行使用メモリ	385,792 KB
スコア	2,198,791,428
最終ジャッジ日時	2023-11-18 11:59:20
合計ジャッジ時間	149,111 ms
ジャッジサーバーID （参考情報）	judge15 / judge13
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,758 ms 336,640 KB
testcase_01	AC	2,763 ms 326,144 KB
testcase_02	AC	2,756 ms 385,792 KB
testcase_03	AC	2,767 ms 243,456 KB
testcase_04	AC	2,747 ms 325,632 KB
testcase_05	AC	2,775 ms 288,000 KB
testcase_06	AC	2,764 ms 238,464 KB
testcase_07	AC	2,750 ms 333,952 KB
testcase_08	AC	2,749 ms 290,944 KB
testcase_09	AC	2,767 ms 312,960 KB
testcase_10	AC	2,754 ms 222,848 KB
testcase_11	AC	2,753 ms 295,808 KB
testcase_12	AC	2,766 ms 287,232 KB
testcase_13	AC	2,775 ms 279,552 KB
testcase_14	AC	2,767 ms 297,856 KB
testcase_15	AC	2,748 ms 228,352 KB
testcase_16	AC	2,764 ms 293,248 KB
testcase_17	AC	2,778 ms 307,072 KB
testcase_18	AC	2,742 ms 277,632 KB
testcase_19	AC	2,785 ms 288,512 KB
testcase_20	AC	2,752 ms 300,800 KB
testcase_21	AC	2,769 ms 311,680 KB
testcase_22	AC	2,753 ms 270,464 KB
testcase_23	AC	2,777 ms 297,216 KB
testcase_24	AC	2,762 ms 378,624 KB
testcase_25	AC	2,756 ms 287,872 KB
testcase_26	AC	2,738 ms 318,592 KB
testcase_27	AC	2,760 ms 338,048 KB
testcase_28	AC	2,763 ms 261,760 KB
testcase_29	AC	2,762 ms 260,480 KB
testcase_30	AC	2,759 ms 258,048 KB
testcase_31	AC	2,751 ms 231,168 KB
testcase_32	AC	2,740 ms 258,688 KB
testcase_33	AC	2,771 ms 340,096 KB
testcase_34	AC	2,755 ms 295,296 KB
testcase_35	AC	2,767 ms 273,408 KB
testcase_36	AC	2,745 ms 259,712 KB
testcase_37	AC	2,738 ms 228,992 KB
testcase_38	AC	2,726 ms 192,640 KB
testcase_39	AC	2,785 ms 370,304 KB
testcase_40	AC	2,756 ms 314,496 KB
testcase_41	AC	2,781 ms 349,696 KB
testcase_42	AC	2,734 ms 265,088 KB
testcase_43	AC	2,776 ms 364,672 KB
testcase_44	AC	2,782 ms 283,648 KB
testcase_45	AC	2,751 ms 242,688 KB
testcase_46	AC	2,770 ms 306,432 KB
testcase_47	AC	2,736 ms 304,512 KB
testcase_48	AC	2,744 ms 282,112 KB
testcase_49	AC	2,761 ms 323,200 KB

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

ソースコード

raw source code

#![allow(dead_code)]
#![allow(non_upper_case_globals)]
#![allow(unused_imports)]
use grid::{Coord, Map2d, DC};
use std::cmp::*;
use std::collections::*;
use std::io::stdin;

const TIME_LIMIT: f64 = 2.7;
const N: usize = 50;
const N2: usize = N * N;
const M: usize = 20;

pub fn main() {
    get_time();
    let input = read_input();
    let output = solve(&input);
    output.print_ans();
    eprintln!("Time = {}", get_time());
}

fn solve(input: &Input) -> Output {
    let mut state = State::new(input);
    state.calc_score(input);
    let best_state = annealing(input, TIME_LIMIT - get_time(), state);
    best_state.to_output(input)
}

#[derive(Clone)]
struct State {
    score: usize,
    use_bomb: Map2d<Vec<bool>>,
    cnt_use: Map2d<usize>,
    jun: Vec<(Coord, usize)>,
}

impl State {
    fn new(input: &Input) -> Self {
        let score = !0;
        let mut use_bomb = Map2d::new(vec![vec![false; M]; N2], N);
        let mut cnt_use = Map2d::new(vec![0; N2], N);
        let mut jun = vec![];
        for x in 0..N {
            for y in 0..N {
                let p = Coord::new(x, y);
                if input.map[p] == Square::Empty || cnt_use[p] > 0 {
                    continue;
                }
                let (bp, bid) = input.can_hakai_rev[p][rnd::next() % input.can_hakai_rev[p].len()];
                use_bomb[bp][bid] = true;
                for &np in input.can_hakai[bp][bid].iter() {
                    cnt_use[np] += 1;
                }
                jun.push((bp, bid));
            }
        }
        Self {
            score,
            use_bomb,
            cnt_use,
            jun,
        }
    }

    fn calc_score(&mut self, input: &Input) {
        let mut score = 0;
        let sz = self.jun.len();
        // uso dp
        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            score += input.bomb_cost[self.jun[i].1];
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    rui + self.jun[i].0.dist(&mae),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    self.jun[i].0.dist(&near),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
            } else {
                dp = sita.0;
                rui = sita.1;
            }
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }

        self.score = score + dp;
    }

    fn to_output(&self, input: &Input) -> Output {
        let mut actions = vec![];
        let sz = self.jun.len();

        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        let mut buyvec = vec![];

        for i in 0..sz {
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    rui + self.jun[i].0.dist(&mae),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    self.jun[i].0.dist(&near),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
                actions.extend(moves(mae, self.jun[i].0));
            } else {
                dp = sita.0;
                rui = sita.1;
                let near = *input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                    .unwrap();
                //actions.extend(moves(mae, near));
                actions.extend(moves_dijkstra(mae, near, &bombed, input));
                // ここに購入を計算 todo // あとでここに入れる
                buyvec.push(vec![]);
                actions.push((2, !0));
                //
                //actions.extend(moves(near, self.jun[i].0));
                actions.extend(moves_dijkstra(near, self.jun[i].0, &bombed, input));
            }
            // use
            actions.push((3, self.jun[i].1 + 1));
            let lll = buyvec.len() - 1;
            buyvec[lll].push((2, self.jun[i].1 + 1));
            //
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        let mut ret_actions = vec![];
        let mut buyidx = 0;
        for &(tp, dd) in actions.iter() {
            if tp != 2 {
                ret_actions.push((tp, dd));
            } else {
                for &t in buyvec[buyidx].iter() {
                    ret_actions.push(t);
                }
                buyidx += 1;
            }
        }
        Output {
            score: self.score,
            actions: ret_actions,
        }
    }

    fn add_bomb(&mut self, input: &Input, bp: Coord, bid: usize) {
        for &np in input.can_hakai[bp][bid].iter() {
            self.cnt_use[np] += 1;
        }
    }

    fn swap_jun(&mut self, pos: (usize, usize)) {
        let a = self.jun[pos.0];
        self.jun[pos.0] = self.jun[pos.1];
        self.jun[pos.1] = a;
    }

    fn swap_off(&mut self, input: &Input) -> bool {
        let idx = rnd::next() % self.jun.len();
        let bp = self.jun[idx].0;
        let bid = self.jun[idx].1;
        let mut added = vec![];
        for &np in input.can_hakai[bp][bid].iter() {
            self.cnt_use[np] -= 1;
            if self.cnt_use[np] == 0 {
                let mut revclone = input.can_hakai_rev[np].clone();
                rnd::shuffle(&mut revclone);
                if let Some(&nb) = revclone.iter().find(|&&ip| !self.use_bomb[ip.0][ip.1]) {
                    self.add_bomb(input, nb.0, nb.1);
                    added.push(nb);
                } else {
                    return false;
                }
            }
        }

        self.use_bomb[bp][bid] = false;
        self.jun.remove(idx);
        for nb in added {
            let mut min_cost = !0;
            let mut best_idx = !0;
            for i in 0..self.jun.len() {
                let dist = if i == 0 {
                    Coord::new(0, 0).dist(&nb.0) + nb.0.dist(&self.jun[i].0)
                } else {
                    self.jun[i - 1].0.dist(&nb.0) + nb.0.dist(&self.jun[i].0)
                };
                if min_cost > dist {
                    min_cost = dist;
                    best_idx = i;
                }
            }
            self.jun.insert(best_idx, nb);
        }
        true
    }
}

fn annealing(input: &Input, duration: f64, mut state: State) -> State {
    let start_time = get_time();
    let duration_inv = 1.0 / duration;
    const START_TEMP: f64 = 1000.0;
    const END_TEMP: f64 = 0.1;
    const DIFF_TEMP: f64 = END_TEMP / START_TEMP;
    let mut temp = START_TEMP;
    let update_temp = || {
        // 非線形
        return START_TEMP * DIFF_TEMP.powf((get_time() - start_time) * duration_inv);
        // 線形
        //return START_TEMP + (END_TEMP - START_TEMP) * (get_time() - start_time) * duration_inv;
    };

    let loglis = (0..0x10000)
        .map(|i| (i as f64 / 0xffff as f64).ln())
        .collect::<Vec<_>>();
    fn is_accepted(now_score: usize, next_score: usize, temp: f64, loglis: &Vec<f64>) -> bool {
        // 最大化する場合。最小化時は -(next_score - now_score)
        -(next_score as f64 - now_score as f64) >= temp * loglis[rnd::next() & 0xffff]
    }

    let mut best_state = state.clone();
    let mut iter_sa = 0;
    let mut cnt_kousin = 0;
    let mut cnt_kousin_best = 0;
    loop {
        if iter_sa & 255 == 0 {
            if get_time() - start_time > duration {
                break;
            }
            // kick! if mae_kousin > 100 {}
            temp = update_temp();
        }
        iter_sa += 1;

        let op = rnd::next() % 100;
        if op < 50 {
            let now_score = state.score;
            let pos = select_2(state.jun.len());
            state.swap_jun(pos);
            state.calc_score(input);
            let next_score = state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
            } else {
                state.swap_jun(pos);
                state.score = now_score;
            }
        } else {
            let now_score = state.score;
            let mut next_state = state.clone();
            next_state.swap_off(input);
            next_state.calc_score(input);
            let next_score = next_state.score;

            if is_accepted(now_score, next_score, temp, &loglis) {
                cnt_kousin += 1;
                state = next_state;
            } else {
                //
            }
        }
        if best_state.score > state.score {
            best_state = state.clone();
            cnt_kousin_best += 1;
        }
    }
    crate::print_data!(iter_sa);
    crate::print_data!(cnt_kousin);
    crate::print_data!(cnt_kousin_best);
    best_state
}

fn moves(a: Coord, b: Coord) -> Vec<(usize, usize)> {
    let mut ret = vec![];
    let mut p = a;
    while p != b {
        if p.y > b.y {
            p.y -= 1;
            ret.push((1, 0));
        } else if p.x > b.x {
            p.x -= 1;
            ret.push((1, 1));
        } else if p.y < b.y {
            p.y += 1;
            ret.push((1, 2));
        } else if p.x < b.x {
            p.x += 1;
            ret.push((1, 3));
        };
    }
    ret
}

fn moves_dijkstra(a: Coord, b: Coord, bombed: &Map2d<bool>, input: &Input) -> Vec<(usize, usize)> {
    let mut ret = vec![];
    if a == b {
        return ret;
    }
    let mut dp = Map2d::new(vec![(!0usize, !0); N2], N);
    dp[a] = (0, !0);
    let mut que = BinaryHeap::new();
    que.push((Reverse(0), a));
    while let Some((Reverse(dist), p)) = que.pop() {
        if que.len() > 10000 {
            assert!(1 == 0);
        }
        if p == b {
            break;
        }
        for dir in 0..4 {
            let np = p.next(dir);
            if !np.in_map(N) {
                continue;
            }
            let ncost = if input.map[np] == Square::Empty || bombed[np] {
                dist + 1
            } else {
                dist + 2
            };

            if ncost < dp[np].0 {
                dp[np] = (ncost, dir);
                que.push((Reverse(ncost), np));
            }
        }
    }
    assert!(dp[b].1 != !0);
    let mut p = b;
    while p != a {
        ret.push((1, dp[p].1));
        p = p.next((2 + dp[p].1) % 4);
    }
    ret.reverse();
    ret
}

#[derive(PartialEq, Eq, Clone, Copy)]
enum Square {
    Empty,
    House,
    Shop,
}

struct Input {
    map: Map2d<Square>,
    bomb_cost: Vec<usize>,
    near_shop: Map2d<Vec<Coord>>,
    can_hakai: Map2d<Vec<Vec<Coord>>>, // そのマスで爆弾iを使って破壊できるもの
    can_hakai_rev: Map2d<Vec<(Coord, usize)>>, // そのマスを破壊することができるマスと爆弾の種類
}

fn read_input() -> Input {
    let _nm = input_vecusize();
    let mut map_ = vec![];
    for _i in 0..N {
        let a = input_string();
        map_.push(a.chars().collect::<Vec<_>>());
    }
    let mut map = vec![];
    for x in 0..N {
        for y in 0..N {
            let c = match map_[x][y] {
                '.' => Square::Empty,
                '#' => Square::House,
                '@' => Square::Shop,
                _ => unreachable!(),
            };
            map.push(c);
        }
    }
    let map = Map2d::new(map, N);
    let mut can_hakai = Map2d::new(vec![vec![vec![]; M]; N2], N);
    let mut bomb_cost = vec![];
    let mut can_hakai_rev = Map2d::new(vec![vec![]; N2], N);
    for bombid in 0..M {
        let cl = input_vecusize();
        let c = cl[0];
        let l = cl[1];
        bomb_cost.push(c);
        for _ in 0..l {
            let dxdy = input_veci32();
            let dx = dxdy[0];
            let dy = dxdy[1];
            for x in 0..N as i32 {
                for y in 0..N as i32 {
                    let nx = x + dx;
                    let ny = y + dy;
                    let p = Coord::new(x as usize, y as usize);
                    let np = Coord::new(nx as usize, ny as usize);
                    if 0 <= nx
                        && nx < N as i32
                        && 0 <= ny
                        && ny < N as i32
                        && map[np] != Square::Empty
                    {
                        can_hakai[p][bombid].push(np);
                        can_hakai_rev[np].push((p, bombid));
                    }
                }
            }
        }
    }
    let mut near_shop = Map2d::new(vec![vec![]; N2], N);
    let mut shops = vec![];
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            if map[p] == Square::Shop {
                shops.push(p);
            }
        }
    }
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            near_shop[p] = shops.clone();
            near_shop[p].sort_by(|a, b| p.dist(a).cmp(&p.dist(b)));
        }
    }

    Input {
        map,
        bomb_cost,
        near_shop,
        can_hakai,
        can_hakai_rev,
    }
}

struct Output {
    score: usize,
    actions: Vec<(usize, usize)>,
}

impl Output {
    fn print_ans(&self) {
        let cost = self.score;
        crate::print_data!(cost);
        let score = 1000000000000usize / (10000 + cost);
        crate::print_data!(score);
        let q = self.actions.len();
        println!("{}", q);
        for i in 0..q {
            if self.actions[i].0 == 1 {
                println!("{} {}", self.actions[i].0, DC[self.actions[i].1]);
            } else {
                println!("{} {}", self.actions[i].0, self.actions[i].1);
            }
        }
    }
}

// ここからライブラリ
#[macro_export]
macro_rules! print_data {
    ( $($x:expr),* ) => {{
        $(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)*
    }}
}

pub fn get_time() -> f64 {
    static mut START: f64 = -1.0;
    let end = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap()
        .as_secs_f64();
    unsafe {
        if START < 0.0 {
            START = end;
        }
        end - START
    }
}

#[allow(unused)]
mod rnd {
    static mut S: usize = 88172645463325252;

    pub fn next() -> usize {
        unsafe {
            S ^= S << 7;
            S ^= S >> 9;
            S
        }
    }

    pub fn nextf() -> f64 {
        f64::from_bits((0x3ff0000000000000 | next() & 0xfffffffffffff) as u64) - 1.
    }

    pub fn range(a: usize, b: usize) -> usize {
        next() % (b - a) + a
    }

    pub fn exu(a: usize, b: usize, skip: usize) -> usize {
        assert!(a <= skip && skip < b);
        let ret = range(a, b - 1);

        ret + (skip <= ret) as usize
    }

    pub fn rangei(a: i64, b: i64) -> i64 {
        (next() % ((b - a) as usize)) as i64 + a
    }

    pub fn shuffle<T>(list: &mut [T]) {
        for i in (0..list.len()).rev() {
            list.swap(i, next() % (i + 1));
        }
    }
}

#[allow(dead_code)]
mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coord {
        pub x: usize,
        pub y: usize,
    }

    impl Coord {
        pub const fn new(x: usize, y: usize) -> Self {
            Self { x, y }
        }

        pub const fn new2(p: usize, width: usize) -> Self {
            Self {
                x: p / width,
                y: p % width,
            }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.x < size && self.y < size
        }

        pub const fn idx(&self, size: usize) -> usize {
            self.x * size + self.y
        }

        pub fn next(self, dir: usize) -> Self {
            self + DXY[dir]
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y)
        }

        const fn dist_1d(x0: usize, x1: usize) -> usize {
            x0.abs_diff(x1)
        }
    }

    impl std::ops::Add for Coord {
        type Output = Self;

        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }

    pub const DXY: [Coord; 4] = [
        Coord::new(0, !0),
        Coord::new(!0, 0),
        Coord::new(0, 1),
        Coord::new(1, 0),
    ];

    pub const DC: [char; 4] = ['L', 'U', 'R', 'D'];

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        pub height: usize,
        pub width: usize,
        map: Vec<T>,
    }

    impl<T: Clone> Map2d<T> {
        pub fn new(map: Vec<T>, width: usize) -> Self {
            let height = map.len() / width;
            debug_assert!(width * height == map.len());
            Self { height, width, map }
        }

        pub fn fill(&mut self, value: T) {
            self.map.fill(value);
        }
    }

    impl<T> std::ops::Index<Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: Coord) -> &Self::Output {
            unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::IndexMut<Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: Coord) -> &mut Self::Output {
            unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::Index<&Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: &Coord) -> &Self::Output {
            &self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::IndexMut<&Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output {
            &mut self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::Index<usize> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, p: usize) -> &Self::Output {
            &self.map[p]
        }
    }

    impl<T> std::ops::IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, p: usize) -> &mut Self::Output {
            &mut self.map[p]
        }
    }
}

fn input_vecusize() -> Vec<usize> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}
fn input_veci32() -> Vec<i32> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}

fn input_string() -> String {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a.trim().parse().unwrap();
}

fn select_2(r: usize) -> (usize, usize) {
    let a = rnd::next() % r;
    let b = rnd::exu(0, r, a);
    (a, b)
}

yukicoder

結果

テストケース

ソースコード