結果

問題 No.5019 Hakai Project
ユーザー hangryhangry
提出日時 2023-11-18 11:07:46
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 18,510 bytes
コンパイル時間 3,393 ms
コンパイル使用メモリ 203,120 KB
実行使用メモリ 385,792 KB
スコア 2,081,715,472
最終ジャッジ日時 2023-11-18 11:10:28
合計ジャッジ時間 160,263 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,982 ms
336,640 KB
testcase_01 AC 2,950 ms
326,144 KB
testcase_02 AC 2,987 ms
385,792 KB
testcase_03 AC 2,950 ms
243,456 KB
testcase_04 AC 2,954 ms
325,632 KB
testcase_05 AC 2,953 ms
288,000 KB
testcase_06 AC 2,956 ms
238,464 KB
testcase_07 AC 2,964 ms
333,952 KB
testcase_08 AC 2,944 ms
290,944 KB
testcase_09 AC 2,960 ms
312,960 KB
testcase_10 AC 2,938 ms
222,848 KB
testcase_11 AC 2,940 ms
295,808 KB
testcase_12 AC 2,967 ms
287,232 KB
testcase_13 AC 2,975 ms
279,552 KB
testcase_14 AC 2,958 ms
297,856 KB
testcase_15 AC 2,979 ms
228,352 KB
testcase_16 AC 2,961 ms
293,248 KB
testcase_17 AC 2,961 ms
307,072 KB
testcase_18 AC 2,949 ms
277,632 KB
testcase_19 AC 2,958 ms
288,512 KB
testcase_20 AC 2,946 ms
300,800 KB
testcase_21 AC 2,969 ms
311,680 KB
testcase_22 AC 2,938 ms
270,464 KB
testcase_23 AC 2,982 ms
297,216 KB
testcase_24 TLE -
testcase_25 AC 2,967 ms
287,872 KB
testcase_26 AC 2,943 ms
318,592 KB
testcase_27 AC 2,945 ms
338,048 KB
testcase_28 AC 2,952 ms
261,760 KB
testcase_29 AC 2,950 ms
260,480 KB
testcase_30 AC 2,938 ms
258,048 KB
testcase_31 AC 2,950 ms
231,168 KB
testcase_32 AC 2,981 ms
258,688 KB
testcase_33 AC 2,972 ms
340,096 KB
testcase_34 AC 2,939 ms
295,296 KB
testcase_35 AC 2,949 ms
273,408 KB
testcase_36 AC 2,953 ms
259,712 KB
testcase_37 AC 2,943 ms
228,992 KB
testcase_38 AC 2,930 ms
192,640 KB
testcase_39 TLE -
testcase_40 AC 2,966 ms
314,496 KB
testcase_41 AC 2,969 ms
349,696 KB
testcase_42 AC 2,946 ms
265,088 KB
testcase_43 AC 2,963 ms
364,672 KB
testcase_44 AC 2,973 ms
283,648 KB
testcase_45 AC 2,961 ms
242,688 KB
testcase_46 AC 2,986 ms
306,432 KB
testcase_47 AC 2,974 ms
304,512 KB
testcase_48 AC 2,939 ms
282,112 KB
testcase_49 AC 2,964 ms
323,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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.9;
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));
                // ここに購入を計算 todo // あとでここに入れる
                buyvec.push(vec![]);
                actions.push((2, !0));
                //
                actions.extend(moves(near, self.jun[i].0));
            }
            // 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
}

#[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)
}
0