結果

問題 No.5019 Hakai Project
ユーザー tttttaaatttttaaa
提出日時 2023-11-25 20:28:03
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 378 ms / 3,000 ms
コード長 17,133 bytes
コンパイル時間 4,381 ms
コンパイル使用メモリ 215,572 KB
実行使用メモリ 184,832 KB
スコア 2,478,690,202
最終ジャッジ日時 2023-11-25 20:28:30
合計ジャッジ時間 24,215 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 309 ms
162,432 KB
testcase_01 AC 310 ms
159,488 KB
testcase_02 AC 372 ms
184,832 KB
testcase_03 AC 234 ms
120,448 KB
testcase_04 AC 303 ms
162,816 KB
testcase_05 AC 283 ms
142,592 KB
testcase_06 AC 229 ms
116,480 KB
testcase_07 AC 306 ms
164,992 KB
testcase_08 AC 280 ms
145,792 KB
testcase_09 AC 294 ms
157,696 KB
testcase_10 AC 218 ms
111,616 KB
testcase_11 AC 276 ms
143,232 KB
testcase_12 AC 275 ms
141,184 KB
testcase_13 AC 274 ms
138,368 KB
testcase_14 AC 271 ms
144,640 KB
testcase_15 AC 232 ms
111,232 KB
testcase_16 AC 272 ms
143,744 KB
testcase_17 AC 297 ms
151,296 KB
testcase_18 AC 279 ms
139,648 KB
testcase_19 AC 271 ms
143,104 KB
testcase_20 AC 282 ms
149,504 KB
testcase_21 AC 283 ms
152,832 KB
testcase_22 AC 249 ms
132,224 KB
testcase_23 AC 274 ms
145,152 KB
testcase_24 AC 378 ms
183,680 KB
testcase_25 AC 273 ms
141,952 KB
testcase_26 AC 295 ms
153,984 KB
testcase_27 AC 318 ms
161,792 KB
testcase_28 AC 241 ms
127,744 KB
testcase_29 AC 242 ms
125,056 KB
testcase_30 AC 267 ms
128,512 KB
testcase_31 AC 231 ms
115,456 KB
testcase_32 AC 251 ms
130,176 KB
testcase_33 AC 312 ms
164,480 KB
testcase_34 AC 295 ms
144,128 KB
testcase_35 AC 253 ms
132,864 KB
testcase_36 AC 256 ms
129,920 KB
testcase_37 AC 233 ms
112,128 KB
testcase_38 AC 194 ms
97,280 KB
testcase_39 AC 319 ms
173,312 KB
testcase_40 AC 310 ms
156,416 KB
testcase_41 AC 356 ms
176,256 KB
testcase_42 AC 246 ms
130,048 KB
testcase_43 AC 323 ms
175,744 KB
testcase_44 AC 280 ms
137,856 KB
testcase_45 AC 232 ms
116,224 KB
testcase_46 AC 278 ms
149,376 KB
testcase_47 AC 285 ms
152,576 KB
testcase_48 AC 295 ms
140,288 KB
testcase_49 AC 290 ms
154,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports, non_snake_case, dead_code)]

pub use __cargo_equip::prelude::*;

use kyopro_grid::{D4, P};
use kyopro_io::get;
use kyopro_utils::*;
use std::cmp::min;
use std::collections::{BTreeSet, BinaryHeap, VecDeque};
use std::mem::{self, swap};
use std::ops::{Index, IndexMut};
use std::{
    cmp::max,
    collections::BTreeMap,
    io::{StdoutLock, Write},
};

const N: usize = 50;
const M: usize = 20;
const DC: [char; 4] = ['D', 'R', 'U', 'L'];

struct Bomb {
    C: usize,
    L: usize,
    ab: Vec<(i32, i32)>,
}
struct Input {
    A: Vec<Vec<char>>,
    bs: Vec<Bomb>,
    shops: Vec<P>,
}
fn read_input() -> Input {
    let _ = get!(usize, usize);
    let A = (0..N).map(|_| get!(String).chars().collect::<Vec<_>>()).collect::<Vec<_>>();
    let mut bs = vec![];
    for _ in 0..M {
        let (c, l) = get!(usize, usize);
        let mut ab = vec![];
        for _ in 0..l {
            let (a, b) = get!(i32, i32);
            ab.push((a, b));
        }
        bs.push(Bomb { C: c, L: l, ab });
    }
    let mut shops = vec![];
    for i in 0..N {
        for j in 0..N {
            if A[i][j] == '@' {
                shops.push(P(i, j));
            }
        }
    }
    Input { A, bs, shops }
}

enum OP {
    MV(usize),
    PUT(usize),
    BUY(usize),
}

struct Operations {
    ops: Vec<OP>,
}

impl Operations {
    fn new() -> Self {
        Self { ops: vec![] }
    }
    fn move_(&mut self, d: usize) {
        self.ops.push(OP::MV(d));
    }
    fn use_bomb(&mut self, m: usize) {
        self.ops.push(OP::PUT(m));
    }
    fn buy_bomb(&mut self, m: usize) {
        self.ops.push(OP::BUY(m));
    }

    fn get(&self) -> Vec<String> {
        self.ops
            .iter()
            .map(|x| match x {
                OP::MV(d) => {
                    format!("{} {}", 1, DC[*d])
                }
                OP::BUY(m) => {
                    format!("{} {}", 2, m + 1)
                }
                OP::PUT(m) => {
                    format!("{} {}", 3, m + 1)
                }
            })
            .collect::<Vec<_>>()
    }
    fn len(&self) -> usize {
        self.ops.len()
    }
}

fn get_bpoints(p: P, ab: &[(i32, i32)], inv: bool) -> Vec<P> {
    let mut res = vec![];
    for &(a, b) in ab {
        let ni = p.0 as i32 + (if inv { -a } else { a });
        let nj = p.1 as i32 + (if inv { -b } else { b });
        if 0 <= ni && ni < N as i32 && 0 <= nj && nj < N as i32 {
            let ni = ni as usize;
            let nj = nj as usize;
            res.push(P(ni, nj));
        }
    }
    res
}

fn move_to_opt(g: &Vec<Vec<char>>, ops: &mut Operations, f: P, t: P) {
    let mut dp = mat![1_000_100_000;N;N];
    let mut pre = mat![!0usize;N;N];
    dp[f] = 0i32;
    let mut que = BinaryHeap::new();
    que.push((0, f.0 * N + f.1));
    while let Some((co, tmp)) = que.pop() {
        let co = -co;
        let p = P(tmp / N, tmp % N);
        if dp[p] < co {
            continue;
        }
        if p == t {
            break;
        }
        for (di, np) in p.adj4().enumerate() {
            if np.0 < N && np.1 < N {
                let pc = if g[np] == '.' { 1 } else { 2 };
                let ncost = co + pc;
                if dp[np].setmin(ncost) {
                    pre[np] = di;
                    if pc == 1 {
                        que.push((-ncost, np.0 * N + np.1));
                    } else {
                        que.push((-ncost, np.0 * N + np.1));
                    }
                }
            }
        }
    }
    let mut moves = vec![];
    let mut now = t;
    while now != f {
        moves.push(pre[now]);
        now = now.add(&D4[(pre[now] + 2) % 4]);
    }
    moves.reverse();
    for d in moves {
        ops.move_(d);
    }
}

fn greedy_internal(
    inp: &Input,
    shops: &[P],
    p_to_bp: &Vec<Vec<Vec<Vec<P>>>>,
    pb_cnt: &Vec<Vec<Vec<i32>>>,
) -> Operations {
    let mut dcost = mat![0;N;N];
    let mut shop_to_npts = mat![vec![];shops.len()];
    let mut p_to_nsi = mat![0;N;N];
    for i in 0..N {
        for j in 0..N {
            let p = P(i, j);
            let mut near_shop = 0;
            let mut d = !0;
            for (si, sp) in shops.iter().enumerate() {
                if d.setmin(sp.dist(&p)) {
                    near_shop = si;
                }
            }
            dcost[p] = d;
            shop_to_npts[near_shop].push(p);
            p_to_nsi[p] = near_shop;
        }
    }
    let _kill = |g: &mut Vec<Vec<char>>, pb_cnt: &mut Vec<Vec<Vec<i32>>>, p: P, c: char| {
        let pre = g[p];
        g[p] = c;
        if pre == '.' || pre == '_' {
            return;
        }
        for i in 0..M {
            for &np in &p_to_bp[p][i] {
                pb_cnt[np][i] -= 1;
            }
        }
    };
    let dkill = |g: &mut Vec<Vec<char>>, pb_cnt: &mut Vec<Vec<Vec<i32>>>, p: P| {
        _kill(g, pb_cnt, p, '_');
    };

    let kill = |g: &mut Vec<Vec<char>>, pb_cnt: &mut Vec<Vec<Vec<i32>>>, p: P| {
        _kill(g, pb_cnt, p, '.');
    };

    let mut ng_pbs = mat![0;N;N;M];
    for (i, &p) in shops.iter().enumerate() {
        for m in 0..M {
            for np in get_bpoints(p, &inp.bs[m].ab, true) {
                ng_pbs[np][m] |= 1usize << i;
            }
        }
    }

    let mut g = inp.A.clone();
    let mut pb_cnt = pb_cnt.clone();
    let mut use_bi_at_shops = vec![];
    let mut ops = Operations::new();

    for (si, &sp) in shops.iter().enumerate() {
        let mut x = 0.0;
        let mut bi = !0;
        for m in 0..M {
            if ng_pbs[sp][m] >> (si + 1) > 0 {
                continue;
            }
            let mut tot = 0;
            for bp in get_bpoints(sp, &inp.bs[m].ab, false) {
                tot += pb_cnt[bp][m];
            }
            if x.setmax(tot as f64 / inp.bs[m].C as f64) {
                bi = m;
            }
        }

        assert!(bi != !0);
        use_bi_at_shops.push(bi);
        {
            for bp in get_bpoints(sp, &inp.bs[bi].ab, false) {
                dkill(&mut g, &mut pb_cnt, bp);
            }
        }
    }
    eprintln!("{:?}", shops);
    let mut curr_shop_i = 0;
    // move to shop[0]
    move_to_opt(&g, &mut ops, P(0, 0), shops[0]);
    while curr_shop_i < shops.len() {
        let can_fire = |p: P, m: usize| ng_pbs[p][m] >> curr_shop_i == 0;
        let mut ri = 0.0;
        let mut best_pm = (P(0, 0), !0, !0);
        for (pti, &tp) in shop_to_npts[curr_shop_i].iter().enumerate() {
            if g[tp] == '.' || g[tp] == '_' {
                continue;
            }
            for m in 0..M {
                for &bp in &p_to_bp[tp][m] {
                    if can_fire(bp, m) {
                        let val = pb_cnt[bp][m] as f64;
                        let co = inp.bs[m].C as f64 + (bp.dist(&shops[curr_shop_i]) * 4) as f64;
                        if ri.setmax(val / co) {
                            best_pm = (bp, m, pti);
                        }
                    }
                }
            }
            if best_pm.1 != !0 {
                break;
            }
        }
        if best_pm.1 == !0 {
            // shop で bomb
            let m = use_bi_at_shops[curr_shop_i];
            ops.buy_bomb(m);
            ops.use_bomb(m);
            for bp in get_bpoints(shops[curr_shop_i], &inp.bs[m].ab, false) {
                kill(&mut g, &mut pb_cnt, bp);
            }
            let rest: usize = shop_to_npts[curr_shop_i].iter().filter(|&&p| g[p] != '.').count();
            eprintln!("rest:{}", rest);

            curr_shop_i += 1;
            if curr_shop_i < shops.len() {
                move_to_opt(&g, &mut ops, shops[curr_shop_i - 1], shops[curr_shop_i]);
            }
        } else {
            // m を購入して bp まで行って m でbomb
            let (p, m, pti) = best_pm;
            if p_to_nsi[p] > curr_shop_i {
                let tp = shop_to_npts[curr_shop_i].swap_remove(pti);
                shop_to_npts[p_to_nsi[p]].push(tp);
            } else {
                ops.buy_bomb(m);
                // shop[curr_shop_i] に戻る
                move_to_opt(&g, &mut ops, shops[curr_shop_i], p);
                ops.use_bomb(m);
                for bp in get_bpoints(p, &inp.bs[m].ab, false) {
                    assert!(bp != shops[curr_shop_i]);
                    kill(&mut g, &mut pb_cnt, bp);
                }
                move_to_opt(&g, &mut ops, p, shops[curr_shop_i]);
            }
        }
    }
    ops
}

fn select_shops(inp: &Input) -> Vec<P> {
    let mut spos1 = vec![vec![]; 10];
    inp.shops.iter().enumerate().for_each(|(i, &p)| {
        let x = min(p.0 / 16, 2);
        let y = min(p.1 / 16, 2);
        let mut prio = 20;
        if p.0 < 5 {
            prio -= p.0;
        }
        if p.0 >= N - 5 {
            prio -= N - p.0;
        }
        if p.1 < 5 {
            prio -= p.1;
        }
        if p.1 >= N - 5 {
            prio -= N - p.1;
        }
        spos1[x * 3 + y].push((i, p, prio as i32));
    });
    let mut dame = mat![false;N;N];
    let mut shops = vec![];
    for i in [0, 1, 2, 5, 4, 3, 6, 7, 8] {
        if spos1[i].len() == 0 {
            continue;
        }
        spos1[i].sort_by_key(|x| -x.2);
        for &(_, p, _) in &spos1[i] {
            if dame[p] {
                continue;
            }
            shops.push(p);
            for bp in get_bpoints(p, &inp.bs[0].ab, false) {
                dame[bp] = true;
            }
            break;
        }
    }
    shops
}
fn greedy(inp: &Input) -> Operations {
    let shops = select_shops(inp);
    let mut p_to_bp = mat![vec![];N;N;M]; // [i][j][b]: bomb b で P(i,j)に攻撃できる座標リスト
    let mut pb_cnt = mat![0i32;N;N;M]; // [i][j][b]: P(i,j) で b を使用したときに攻撃できる座標の数
    for i in 0..N {
        for j in 0..N {
            if inp.A[i][j] == '.' {
                continue;
            }
            for k in 0..M {
                for np in get_bpoints(P(i, j), &inp.bs[k].ab, true) {
                    p_to_bp[i][j][k].push(np);
                    pb_cnt[np][k] += 1;
                }
            }
        }
    }
    let res = greedy_internal(inp, &shops, &p_to_bp, &pb_cnt);
    res
}

fn main() {
    let stdout = std::io::stdout();
    let mut writer = std::io::BufWriter::new(stdout.lock());
    let inp = read_input();

    let res = greedy(&inp);
    writeln!(writer, "{}", res.len()).unwrap();
    for s in res.get() {
        writeln!(writer, "{}", s).unwrap();
    }
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `kyopro-grid 0.1.0 (path+██████████████████████████████████████████████████)`   published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_grid`
///  - `kyopro-io 0.1.0 (path+████████████████████████████████████████████████)`       published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_io`
///  - `kyopro-utils 0.1.0 (path+███████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::kyopro_utils`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod kyopro_grid {use std::ops::{Index,IndexMut};pub const D4:[P;4]=[P(1,0),P(0,1),P(!0,0),P(0,!0)];#[derive(Clone,Copy,PartialEq,Eq,Debug)]pub struct P(pub usize,pub usize);impl P{pub fn adj4(self)->impl Iterator<Item=P>{D4.iter().map(move|&d|self.add(&P(d.0,d.1)))}pub fn add(self,rhs:&P)->P{P(self.0.wrapping_add(rhs.0),self.1.wrapping_add(rhs.1))}pub fn dist(&self,rhp:&P)->usize{let a=(self.0 as i32-rhp.0 as i32).abs()as usize;let b=(self.1 as i32-rhp.1 as i32).abs()as usize;a+b}}impl<T>Index<P>for Vec<Vec<T>>{type Output=T;fn index(&self,p:P)->&T{&self[p.0][p.1]}}impl<T>IndexMut<P>for Vec<Vec<T>>{fn index_mut(&mut self,p:P)->&mut T{&mut self[p.0][p.1]}}pub struct Grid<T>{h:usize,w:usize,g:Vec<Vec<T>>,}impl<T>Grid<T>where T:Copy,{pub fn from(g:&Vec<Vec<T>>)->Self{Grid{h:g.len(),w:g[0].len(),g:g.clone()}}#[allow(non_snake_case)]pub fn new(h:usize,w:usize,I:T)->Self{let g=vec![vec![I;w];h];Grid{h,w,g}}}impl<T>Grid<T>{pub fn adj4<'a>(&'a self,p:P)->impl Iterator<Item=P>+'a{D4.iter().map(move|&d|p.add(&P(d.0,d.1))).filter(|&p|p.0<self.h&&p.1<self.w)}pub fn positions_from<'a>(&'a self,b:P,offsets:&'a[P])->impl Iterator<Item=P>+'a{let x=offsets.iter().map(move|&d|P(b.0.wrapping_add(d.0),b.1.wrapping_add(d.1)));x.filter(|&p|p.0<self.h&&p.1<self.w)}pub fn position_from(&self,b:P,offset:P)->Option<P>{let x=b.add(&offset);if self.is_valid_position(&x){Some(x)}else{None}}pub fn is_valid_position(&self,p:&P)->bool{p.0<self.h&&p.1<self.w}}impl<T>Index<usize>for Grid<T>{type Output=[T];#[inline]fn index(&self,idx:usize)->&[T]{&self.g[idx]}}impl<T>IndexMut<usize>for Grid<T>{#[inline]fn index_mut(&mut self,idx:usize)->&mut[T]{&mut self.g[idx]}}impl<T>Index<P>for Grid<T>{type Output=T;#[inline]fn index(&self,idx:P)->&T{&self.g[idx.0][idx.1]}}impl<T>IndexMut<P>for Grid<T>{#[inline]fn index_mut(&mut self,p:P)->&mut T{&mut self.g[p.0][p.1]}}}
        pub mod kyopro_io {pub use crate::__cargo_equip::macros::kyopro_io::*;#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_io_get{($t:ty)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter=line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty;$n:expr)=>{(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*;$n:expr)=>{(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty;;)=>{{let mut line:String=String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t|t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty;;$n:expr)=>{(0..$n).map(|_|get!($t;;)).collect::<Vec<_>>()};}macro_rules!get{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_io_get!{$($tt)*})}}
        pub mod kyopro_utils {pub use crate::__cargo_equip::macros::kyopro_utils::*;use std::ops::{Add,Rem};#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_mat{($($e:expr),*)=>{Vec::from(vec![$($e),*])};($($e:expr,)*)=>{Vec::from(vec![$($e),*])};($e:expr;$d:expr)=>{Vec::from(vec![$e;$d])};($e:expr;$d:expr$(;$ds:expr)+)=>{Vec::from(vec![mat![$e$(;$ds)*];$d])};}macro_rules!mat{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_mat!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_echo{($($num:expr),*)=>{let mut tmp=vec![];$(tmp.push(format!("{}",$num));)*println!("{}",tmp.join(" "));};}macro_rules!echo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_echo!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_YesNo{($num:expr)=>{if($num)as i64==0{println!("No");}else{println!("Yes");}};}macro_rules!YesNo{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_YesNo!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_Yes{()=>{println!("Yes");};}macro_rules!Yes{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_Yes!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_kyopro_utils_No{()=>{println!("No");};}macro_rules!No{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_kyopro_utils_No!{$($tt)*})}pub trait SetMinMax{fn setmin(&mut self,v:Self)->bool;fn setmax(&mut self,v:Self)->bool;}impl<T>SetMinMax for T where T:PartialOrd,{fn setmin(&mut self,v:T)->bool{*self>v&&{*self=v;true}}fn setmax(&mut self,v:T)->bool{*self<v&&{*self=v;true}}}pub fn print_vec<T>(v:&[T])where T:std::fmt::Display,{for i in 0..v.len(){print!("{}{}",v[i],if i+1==v.len(){""}else{" "});}println!();}pub fn pmod<T:Copy+Add<Output=T>+Rem<Output=T>>(x:T,m:T)->T{((x%m)+m)%m}pub fn lower_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>=*x{return 0;}let mut l=0;let mut r=a.len();while l+1<r{let m=(l+r)/2;if a[m]<*x{l=m;}else{r=m;}}r}pub fn upper_bound<T>(a:&[T],x:&T)->usize where T:Ord,{if a.len()==0||a[0]>*x{return 0;}let mut l=0;let mut r=a.len();while l+1<r{let m=(l+r)/2;if a[m]<=*x{l=m;}else{r=m;}}r}}
    }

    pub(crate) mod macros {
        pub mod kyopro_grid {}
        pub mod kyopro_io {pub use crate::__cargo_equip_macro_def_kyopro_io_get as get;}
        pub mod kyopro_utils {pub use crate::{__cargo_equip_macro_def_kyopro_utils_No as No,__cargo_equip_macro_def_kyopro_utils_Yes as Yes,__cargo_equip_macro_def_kyopro_utils_YesNo as YesNo,__cargo_equip_macro_def_kyopro_utils_echo as echo,__cargo_equip_macro_def_kyopro_utils_mat as mat};}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod kyopro_grid {}
        pub mod kyopro_io {}
        pub mod kyopro_utils {}
    }
}
0