結果

問題 No.5019 Hakai Project
ユーザー t33f
提出日時 2023-11-19 19:24:23
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2,940 ms / 3,000 ms
コード長 22,394 bytes
コンパイル時間 2,499 ms
コンパイル使用メモリ 204,588 KB
実行使用メモリ 6,676 KB
スコア 2,844,373,549
最終ジャッジ日時 2023-11-19 19:29:16
合計ジャッジ時間 157,493 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(non_snake_case)]
use std::fmt;
use std::ops::Add;
use std::collections::BinaryHeap;
use crate::rand::Rng;
const N: usize = 50;
const M: usize = 20;
struct Diff {
    dx: i64,
    dy: i64,
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
struct Pos {
    x: i64,
    y: i64,
}
impl Add<Diff> for Pos {
    type Output = Pos;
    fn add(self, d: Diff) -> Pos {
        Pos {x: self.x + d.dx, y: self.y + d.dy}
    }
}
impl Add<&Diff> for Pos {
    type Output = Pos;
    fn add(self, d: &Diff) -> Pos {
        Pos {x: self.x + d.dx, y: self.y + d.dy}
    }
}
impl Pos {
    fn is_valid(&self) -> bool {
        self.x >= 0 && self.y >= 0 && (self.x as usize) < N && (self.y as usize) < N
    }
}
struct Input {
    A: Vec<Vec<char>>,
    costs: [usize; M],
    offsets: [Vec<Diff>; M],
}
fn read_input() -> Input {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let nums: Vec<&str> = line.split_whitespace().collect();
    assert!(nums.len() == 2);
    assert!(nums[0].parse::<usize>() == Ok(N));
    assert!(nums[1].parse::<usize>() == Ok(M));
    let mut A = Vec::new();
    for _ in 0..N {
        line.clear();
        std::io::stdin().read_line(&mut line).unwrap();
        A.push(line.chars().collect());
    }
    let mut costs = [0; M];
    let mut offsets: [Vec<Diff>; M] = Default::default();
    for j in 0..M {
        line.clear();
        std::io::stdin().read_line(&mut line).unwrap();
        let nums: Vec<&str> = line.split_whitespace().collect();
        assert!(nums.len() == 2);
        let C: usize = nums[0].parse().unwrap();
        let L: usize = nums[1].parse().unwrap();
        costs[j] = C;
        for _ in 0..L {
            line.clear();
            std::io::stdin().read_line(&mut line).unwrap();
            let nums: Vec<&str> = line.split_whitespace().collect();
            assert!(nums.len() == 2);
            let dx: i64 = nums[0].parse().unwrap();
            let dy: i64 = nums[1].parse().unwrap();
            offsets[j].push(Diff{ dx, dy })
        }
    }
    Input { A, costs, offsets }
}
#[derive(Clone, Copy)]
enum Dir { L, R, U, D }
const ALL_DIRS: [Dir; 4] = [Dir::L, Dir:: R, Dir:: U, Dir::D];
impl fmt::Display for Dir {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let c = match self { Dir::L => 'L', Dir::R => 'R', Dir::U => 'U', Dir::D => 'D' };
        write!(f, "{}", c)
    }
}
impl Dir {
    fn to_diff(self) -> Diff {
        match self {
            Dir::L => Diff{dx: 0, dy: -1},
            Dir::R => Diff{dx: 0, dy: 1},
            Dir::U => Diff{dx: -1, dy: 0},
            Dir::D => Diff{dx: 1, dy: 0},
        }
    }
}
enum Move {
    Buy { bomb: usize, shop_pos: Pos },
    Use { bomb: usize, pos: Pos },
}
enum AtomicMove {
    Walk(Dir),
    Buy(usize),
    Use(usize),
}
fn list_bomb_use(input: &Input) -> Vec<(usize, Pos)> {
    let mut A = input.A.clone();
    let mut used_bombs = Vec::new();
    let mut ub = [[[N * N; N]; N]; M]; // 枝刈り用
    loop {
        let mut max_eval = 0;
        let mut cand = (0, 0, 0);
        let calc_eval = |count: usize, i: usize| {
            1_000_000_000 * count / input.costs[i]
        };
        for i in 0..M {
            for x in 0..N as i64 {
                for y in 0..N as i64 {
                    if calc_eval(ub[i][x as usize][y as usize], i) <= max_eval {
                        continue
                    }
                    let p = Pos{x, y};
                    let mut count = 0;
                    for d in &input.offsets[i] {
                        let q = p + d;
                        if q.is_valid() {
                            let x = q.x as usize;
                            let y = q.y as usize;
                            if A[x][y] != '.' {
                                count += 1
                            }
                        }
                    }
                    ub[i][x as usize][y as usize] = ub[i][x as usize][y as usize].min(count);
                    let eval = calc_eval(count, i);
                    if eval > max_eval {
                        max_eval = eval;
                        cand = (i, x, y)
                    }
                }
            }
        }
        if max_eval == 0 {
            break
        } else {
            let (i, x, y) = cand;
            let p = Pos{x, y};
            used_bombs.push((i, p));
            for d in &input.offsets[i] {
                let q = p + d;
                if q.is_valid() {
                    let x = q.x as usize;
                    let y = q.y as usize;
                    A[x][y] = '.';
                }
            }
        }
    }
    used_bombs
}
fn L1(a: Pos, b: Pos) -> usize {
    ((a.x - b.x).abs() + (a.y - b.y).abs()) as usize
}
fn shortest_path(A: &Vec<Vec<char>>, start: Pos, goal: Pos) -> Vec<Dir> {
    let mut pq = BinaryHeap::new();
    pq.push((0i64, goal));
    let mut distance = vec![vec![1i64 << 50; N]; N];
    let mut next_dir = vec![vec![None::<Dir>; N]; N];
    distance[goal.x as usize][goal.y as usize] = 0;
    while !pq.is_empty() {
        let (md, p) = pq.pop().unwrap();
        let d = -md;
        if distance[p.x as usize][p.y as usize] < d {
            continue
        }
        let weight = if A[p.x as usize][p.y as usize] == '.' { 1 } else { 2 };
        for dir in ALL_DIRS {
            let diff = dir.to_diff();
            // 逆向きに見ているので引く
            let x1 = p.x - diff.dx;
            let y1 = p.y - diff.dy;
            let p1 = Pos{x: x1, y: y1};
            let new_dist = distance[p.x as usize][p.y as usize] + weight;
            if p1.is_valid() && distance[x1 as usize][y1 as usize] > new_dist {
                distance[x1 as usize][y1 as usize] = new_dist;
                next_dir[x1 as usize][y1 as usize] = Some(dir);
                pq.push((-new_dist, p1));
            }
        }
    }
    let mut p = start;
    let mut result = Vec::new();
    while p != goal {
        let dir = next_dir[p.x as usize][p.y as usize].unwrap();
        result.push(dir);
        p = p + dir.to_diff();
    }
    result
}
fn split_uselist(input: &Input, sol: &Vec<Vec<(usize, Pos)>>,
                 seed: u32, timer: &Timer, tl: u64)
                 -> (Vec<Vec<(usize, Pos)>>, u64) {
    let all_shops: Vec<Pos> = {
        let mut result = Vec::new();
        for x in 0..N {
            for y in 0..N {
                if input.A[x][y] == '@' {
                    result.push(Pos{x: x as i64, y: y as i64})
                }
            }
        }
        result
    };
    let calc_cost = |sol: &Vec<Vec<(usize, Pos)>>| -> u64 {
        let mut p = Pos{x: 0, y: 0};
        let mut A = input.A.clone();
        let mut cost: u64 = 0;
        for use_list in sol {
            assert!(!use_list.is_empty());
            let q = use_list[0].1;
            let weight = ((use_list.len() + 1) * (use_list.len() + 1)) as u64;
            let best_shop: Option<&Pos> = {
                all_shops.iter()
                    .filter(|p| A[p.x as usize][p.y as usize] == '@')
                    .min_by_key(|s| L1(p, **s) as u64 + weight * L1(**s, q) as u64)
            };
            if best_shop.is_none() {
                return 1u64 << 60
            }
            assert!(best_shop.is_some());
            let s = *best_shop.unwrap();
            cost += L1(p, s) as u64;
            p = s;
            for i in 0..use_list.len() {
                let weight = ((use_list.len() - i + 1) * (use_list.len() - i + 1)) as u64;
                cost += weight * L1(p, use_list[i].1) as u64;
                p = use_list[i].1;
                for diff in &input.offsets[use_list[i].0] {
                    let q = p + diff;
                    if q.is_valid() {
                        let Pos{x, y} = q;
                        A[x as usize][y as usize] = '.';
                    }
                }
            }
        }
        cost
    };
    let mut best_sol = sol.clone();
    let mut best_cost = calc_cost(&best_sol);
    let mut cur_sol = sol.clone();
    let mut cur_cost = best_cost;
    let mut rng = rand::Rng::new(seed);
    let accept = |new_cost: u64, cur_cost: u64, progress: f64, rng: &mut Rng| {
        let start_temp = 20.0;
        let end_temp = 1.0;
        let temp = start_temp + progress * (end_temp - start_temp);
        if new_cost > cur_cost + (temp * 20.0) as u64 {
            return false
        } else if new_cost <= cur_cost {
            true
        } else {
            let prob = (-(cur_cost.abs_diff(new_cost) as f64) / temp).exp();
            rng.rand_bool(prob)
        }
    };
    #[allow(dead_code)]
    enum Neighbor {
        Split(usize, usize),
        Merge(usize),
        Rev1(usize),
        Swap(usize, usize),
        Remove(usize),
        Replace(usize, usize, usize, Pos),
    }
    let mut acc = [0; 6];
    let start_time = timer.get_elapsed_time();
    let mut iter = 0;
    while timer.get_elapsed_time() < tl {
        let mut tmp_sol = best_sol.clone();
        let nbr = loop {
            match rng.uniform_u32(0, 6) {
                0 | 1 => {
                    let i = rng.uniform_u32(0, tmp_sol.len() as u32) as usize;
                    if tmp_sol[i].len() > 1 {
                        let j = rng.uniform_u32(1, tmp_sol[i].len() as u32) as usize;
                        break Neighbor::Split(i, j)
                    }
                }
                2 => {
                    if tmp_sol.len() > 1 {
                        let i = rng.uniform_u32(0, tmp_sol.len() as u32 - 1) as usize;
                        break Neighbor::Merge(i)
                    }
                }
                3 => {
                    let i = rng.uniform_u32(0, tmp_sol.len() as u32) as usize;
                    if tmp_sol[i].len() > 1 {
                        break Neighbor::Rev1(i)
                    }
                }
                // 4 => {
                //     let mut flat_sol = Vec::new();
                //     for l in &tmp_sol { flat_sol.append(&mut l.clone()) }
                //     match find_alternative(&input, &flat_sol) {
                //         None => (),
                //         Some((j, None)) => break Neighbor::Remove(j),
                //         Some((j, Some((i, p)))) => {
                //             let mut a = 0;
                //             let mut res = None;
                //             for k in 0..tmp_sol.len() {
                //                 assert!(a <= j);
                //                 if j < a + tmp_sol[k].len() {
                //                     res = Some(Neighbor::Replace(k, j - a, i, p));
                //                     break
                //                 } else {
                //                     a += tmp_sol[k].len()
                //                 }
                //             }
                //             if let Some(n) = res { break n }
                //         }
                //     }
                // }
                _ => {
                    if tmp_sol.len() > 1 {
                        let i = rng.uniform_u32(0, tmp_sol.len() as u32) as usize;
                        let j = rng.uniform_u32(0, tmp_sol.len() as u32) as usize;
                        if i != j {
                            break Neighbor::Swap(i, j)
                        }
                    }
                }
            }
        };
        match nbr {
            Neighbor::Split(i, j) => {
                tmp_sol.insert(i + 1, tmp_sol[i][j..].iter().map(|&x| x).collect());
                tmp_sol[i].truncate(j);
            }
            Neighbor::Merge(i) => {
                assert!(i + 1 < tmp_sol.len());
                let mut tail = tmp_sol.remove(i + 1);
                tmp_sol[i].append(&mut tail);
            }
            Neighbor::Rev1(i) => {
                tmp_sol[i].reverse();
            }
            Neighbor::Swap(i, j) => {
                tmp_sol.swap(i, j);
            }
            Neighbor::Remove(j) => {
                tmp_sol.remove(j);
            }
            Neighbor::Replace(k, j, i, p) => {
                tmp_sol[k][j] = (i, p)
            }
        }
        let tmp_cost = calc_cost(&tmp_sol);
        let progress = (timer.get_elapsed_time() - start_time) as f64 / (tl - start_time) as f64;
        iter += 1;
        if accept(tmp_cost, cur_cost, progress, &mut rng) {
            cur_sol = tmp_sol;
            cur_cost = tmp_cost;
            match nbr {
                Neighbor::Split(_, _) => acc[0] += 1,
                Neighbor::Merge(_) => acc[1] += 1,
                Neighbor::Rev1(_) => acc[2] += 1,
                Neighbor::Swap(_, _) => acc[3] += 1,
                Neighbor::Remove(_) => acc[4] += 1,
                Neighbor::Replace(_, _, _, _) => acc[5] += 1,
            }
        }
        if cur_cost < best_cost {
            best_sol = cur_sol.clone();
            best_cost = cur_cost;
            eprintln!("{} {}", iter, best_cost);
        }
    }
    eprintln!("{:?}", acc);
    (best_sol, best_cost)
}
fn solve(input: &Input, timer: &Timer, tl: u64) -> Vec<Move> {
    let used_bombs: Vec<(usize, Pos)> = {
        let tmp = list_bomb_use(&input);
        let order = solve_tsp(&tmp.iter().map(|(_, p)| *p).collect());
        order.iter().map(|i| tmp[*i]).collect()
    };
    let initial_sol = used_bombs.iter().map(|x| vec![*x; 1]).collect();
    eprintln!("initial solution {}", timer.get_elapsed_time());
    let iter_count = 4;
    let sol =
        (0..iter_count).map(|i| {
            let cur_time = timer.get_elapsed_time();
            let rem_time = tl - cur_time;
            let rem_count = iter_count - i;
            let dur = rem_time / rem_count;
            split_uselist(input, &initial_sol, i as u32, timer, cur_time + dur)
        })
        .min_by_key(|(_, cost)| *cost)
        .unwrap()
        .0;
    let mut ans = Vec::new();
    let mut p = Pos{x: 0, y: 0};
    let mut A = input.A.clone();
    for use_list in &sol {
        let shop = {
            let shops: Vec<Pos> = {
                let mut result = Vec::new();
                for x in 0..N {
                    for y in 0..N {
                        if A[x][y] == '@' {
                            result.push(Pos{x: x as i64, y: y as i64})
                        }
                    }
                }
                result
            };
            assert!(!shops.is_empty());
            let weight = (use_list.len() + 1) * (use_list.len() + 1);
            let q = use_list[0].1;
            let nearest_shop = |p: Pos| {
                *shops.iter().min_by_key(|s| L1(p, **s) + weight * L1(**s, q)).unwrap()
            };
            nearest_shop(p)
        };
        // buy
        for (i, _) in use_list {
            ans.push(Move::Buy{bomb: *i, shop_pos: shop});
        }
        // use
        for (i, q) in use_list {
            ans.push(Move::Use{bomb: *i, pos: *q});
            p = *q;
            for diff in &input.offsets[*i] {
                let p1 = p + diff;
                if p1.is_valid() {
                    let Pos{x, y} = p1;
                    A[x as usize][y as usize] = '.';
                }
            }
        }
    }
    ans
}
fn write_ans(ans: &Vec<AtomicMove>) {
    println!("{}", ans.len());
    for m in ans {
        match m {
            AtomicMove::Walk(d) => println!("1 {}", d),
            AtomicMove::Buy(i) => println!("2 {}", i + 1),
            AtomicMove::Use(i) => println!("3 {}", i + 1),
        }
    }
}
fn calc_score(input: &Input, ans: &Vec<AtomicMove>) -> (u64, u64) {
    let mut cost: u64 = 0;
    let mut A = input.A.clone();
    let mut p = (0, 0);
    let mut bomb_stock = [0; M];
    let mut total_bombs = 0;
    for m in ans {
        use AtomicMove::{Walk, Buy, Use};
        match m {
            Walk(m) => {
                match m {
                    Dir::L => {
                        assert!(p.1 > 0);
                        p.1 -= 1;
                    },
                    Dir::R => {
                        assert!(p.1 + 1 < N);
                        p.1 += 1;
                    }
                    Dir::D => {
                        assert!(p.0 + 1 < N);
                        p.0 += 1;
                    }
                    Dir::U => {
                        assert!(p.0 > 0);
                        p.0 -= 1;
                    }
                }
                let base_cost = (total_bombs + 1) * (total_bombs + 1);
                let weight = if A[p.0][p.1] == '.' { 1 } else { 2 };
                cost += base_cost * weight;
            }
            Buy(i) => {
                assert!(*i < M);
                cost += input.costs[*i] as u64;
                bomb_stock[*i] += 1;
                total_bombs += 1;
            }
            Use(i) => {
                assert!(*i < M);
                assert!(bomb_stock[*i] > 0);
                bomb_stock[*i] -= 1;
                total_bombs -= 1;
                for Diff{dx, dy} in &input.offsets[*i] {
                    let x = p.0 as i64 + dx;
                    let y = p.1 as i64 + dy;
                    if 0 <= x && x < N as i64 && 0 <= y && y < N as i64 {
                        A[x as usize][y as usize] = '.';
                    }
                }
            }
        }
    }
    if (0..N).any(|i| (0..N).any(|j| A[i][j] != '.')) {
        (1, cost)
    } else {
        ((1e12 / (1e4 + cost as f64)).floor() as u64, cost)
    }
}
fn convert_solution(input: &Input, sol: &Vec<Move>) -> Vec<AtomicMove> {
    let mut cur_pos = Pos{x: 0, y: 0};
    let mut ans = Vec::new();
    let mut A = input.A.clone();
    for m in sol {
        match m {
            Move::Buy{bomb, shop_pos} => {
                assert!({
                    let Pos{x, y} = shop_pos;
                    A[*x as usize][*y as usize] == '@'
                });
                for d in shortest_path(&A, cur_pos, *shop_pos) { ans.push(AtomicMove::Walk(d)) }
                ans.push(AtomicMove::Buy(*bomb));
                cur_pos = *shop_pos;
            }
            Move::Use{bomb, pos} => {
                // let mut count = 0;
                for d in shortest_path(&A, cur_pos, *pos) { ans.push(AtomicMove::Walk(d)) }
                ans.push(AtomicMove::Use(*bomb));
                cur_pos = *pos;
                for diff in &input.offsets[*bomb] {
                    let p1 = cur_pos + diff;
                    if p1.is_valid() {
                        let Pos{x, y} = p1;
                        // if A[x as usize][y as usize] != '.' { count += 1 }
                        A[x as usize][y as usize] = '.';
                    }
                }
                // eprintln!("{} {} {} {}", bomb, pos.x, pos.y, count);
            }
        }
    }
    ans
}
fn main() {
    let timer = Timer::new();
    let input = read_input();
    let sol = solve(&input, &timer, 2900);
    let ans = convert_solution(&input, &sol);
    write_ans(&ans);
    let (score, cost) = calc_score(&input, &ans);
    eprintln!("calculated score, cost = {} {}", score, cost);
}
mod rand {
    pub struct Rng {
        x: u32,
        y: u32,
        z: u32,
        w: u32
    }
    impl Rng {
        pub fn new(seed: u32) -> Rng {
            Rng {
                x: 123456789,
                y: 362436069,
                z: 521288629,
                w: 88675123 ^ seed,
            }
        }
        pub fn next(&mut self) -> u32 {
            let t = self.x ^ (self.x << 11);
            self.x = self.y;
            self.y = self.z;
            self.z = self.w;
            self.w = (self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8));
            t
        }
        pub fn rand_bool(&mut self, prob: f64) -> bool {
            let x = (prob * (1u64 << 32) as f64) as u32;
            self.next() < x
        }
        pub fn uniform_u32(&mut self, lb: u32, ub: u32) -> u32 {
            assert!(lb < ub);
            lb + self.next() % (ub - lb)
        }
    }
}
struct Timer {
    start: std::time::SystemTime
}
impl Timer {
    fn new() -> Timer {
        let start = std::time::SystemTime::now();
        Timer {start}
    }
    fn get_elapsed_time(&self ) -> u64 {
        let dur = std::time::SystemTime::now().duration_since(self.start).unwrap();
        dur.as_millis() as u64
    }
}
fn solve_tsp(pos_list: &Vec<Pos>) -> Vec<usize> {
    let n = pos_list.len();
    let calc_cost = |ans: &Vec<usize>| -> usize {
        let mut cost = 0;
        for i in 1..ans.len() {
            let w = n - i + 1;
            let prev_pos = pos_list[ans[i - 1]];
            let next_pos = pos_list[ans[i]];
            cost += L1(prev_pos, next_pos) * w * w;
        }
        cost
    };
    let mut cur_ans = (0..pos_list.len()).collect();
    let mut cur_cost = calc_cost(&cur_ans);
    let mut best_ans = cur_ans.clone();
    let mut best_cost = cur_cost;
    let max_iter = 100_000;
    let mut rng = Rng::new(0);
    let rand_range = |n: usize, rng: &mut Rng| {
        loop {
            let i = rng.uniform_u32(0, n as u32) as usize;
            let j = rng.uniform_u32(0, n as u32) as usize;
            if i > j { break (j, i) }
            if i < j { break (i, j) }
        }
    };
    let accept = |cur_cost: usize, new_cost: usize, progress: f64, rng: &mut Rng| -> bool {
        if new_cost <= cur_cost {
            true
        } else {
            let start_temp = 10000.0;
            let end_temp = 1.0;
            let temp = start_temp + (end_temp - start_temp) * progress;
            let prob = ((cur_cost as f64 - new_cost as f64) / temp).exp();
            rng.rand_bool(prob)
        }
    };
    for iter in 0..max_iter {
        let (i, j) = rand_range(pos_list.len(), &mut rng);
        // eprintln!("{}", cur_ans.iter().join(" "));
        // eprintln!("rev {} {}", i, j);
        cur_ans[i..j].reverse();
        // eprintln!("-> {}", cur_ans.iter().join(" "));
        let tmp_cost = calc_cost(&cur_ans);
        if accept(cur_cost, tmp_cost, iter as f64 / max_iter as f64, &mut rng) {
            cur_cost = tmp_cost;
        } else {
            cur_ans[i..j].reverse();
        }
        if cur_cost < best_cost {
            best_cost = cur_cost;
            best_ans = cur_ans.clone();
            // eprintln!("{} {}", iter, best_cost);
        }
    }
    best_ans
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0