Submission #42958368

---

Source Code Expand

#![allow(non_snake_case)]

use bitset_fixed::BitSet;
use itertools::Itertools;
use proconio::*;
use std::collections::HashSet;

fn main() {
    get_time();
    let input = read_input();
    let out = solve(&input);
    write_output(&out);
    eprintln!("Time = {:.3}", get_time());
}

const W: usize = 2000;

fn solve(input: &Input) -> Output {
    // 一番小さいボールから順に1つずつ適切な場所へ運ぶのを1ステップとしてビームサーチをする
    // 評価値は(手数, 下方向にボールを動かすたびにその数字を減算したもの)の辞書順
    let mut beam = vec![State {
        bs: input.bs.clone(),
        id: !0,
        score: (0, 0),
        used: BitSet::new(N2),
    }];
    let mut trace = Trace::new();
    let mut dist = [((1000000000, 0), !0); N2];
    for i in 0..N2 as i32 {
        eprintln!("{}: {}", i, beam[0].score.0);
        let mut trace2 = Trace::new();
        // 高速化のため、次の状態を列挙するのではなく評価値と遷移方法のみを列挙する
        // (評価値, 現在のビームの何番目からか, 運ぶ先x, 運ぶ先y, 復元用ID)
        let mut next_move = vec![];
        let pos: Vec<(usize, usize)> = beam.iter().map(|s| pos(&s.bs, i)).collect_vec();
        for b in 0..beam.len() {
            let bs = &beam[b].bs;
            let (x0, y0) = pos[b];
            dist[id(x0, y0)] = ((0, 0), !0);
            if x0 == 0 || (y0 == 0 || bs[id(x0 - 1, y0 - 1)] < i) && (y0 == x0 || bs[id(x0 - 1, y0)] < i) {
                next_move.push((beam[b].score, b, x0, y0, !0));
                continue;
            }
            // 上方向への(評価値の観点で)最適な運び方をDPで計算する
            for dx in 1..=x0 {
                let x = x0 - dx;
                let mut ok = false;
                for y in y0 - y0.min(dx)..=y0.min(x) {
                    if bs[id(x, y)] < i {
                        continue;
                    }
                    let mut d = (1000000000, 0);
                    let mut prev = (0, !0);
                    if y + dx != y0 {
                        let d2 = dist[id(x + 1, y)];
                        if d.setmin((d2.0 .0 + 1, d2.0 .1 - bs[id(x, y)])) {
                            prev = (0, d2.1);
                            ok = true;
                        }
                    }
                    if y0 != y {
                        let d2 = dist[id(x + 1, y + 1)];
                        if d.setmin((d2.0 .0 + 1, d2.0 .1 - bs[id(x, y)])) {
                            prev = (1, d2.1);
                            ok = true;
                        }
                    }
                    let k = if d.0 < 1000000000 { trace2.add(prev.0, prev.1) } else { !0 };
                    dist[id(x, y)] = (d, k);
                    // 運び方はDPで最適なもの一つに絞るが、運び先に応じてそれぞれ別の遷移とする
                    if d.0 < 1000000000 && (x == 0 || (y == 0 || bs[id(x - 1, y - 1)] < i) && (y == x || bs[id(x - 1, y)] < i)) {
                        next_move.push((
                            (beam[b].score.0 + dist[id(x, y)].0 .0, beam[b].score.1 + dist[id(x, y)].0 .1),
                            b,
                            x,
                            y,
                            k,
                        ));
                    }
                }
                if !ok {
                    break;
                }
            }
        }
        next_move.sort_by_key(|a| a.0);
        let mut next = vec![];
        let mut set = HashSet::new();
        for (score, b, x, y, tid) in next_move {
            // 多様性確保のため、既に埋まった座標の集合が同じものは1つまでしか選ばないようにする
            let mut used = beam[b].used.clone();
            used.set(id(x, y), true);
            if !set.insert(used.clone()) {
                continue;
            }
            let (mut x, mut y) = pos[b];
            let mut k = beam[b].id;
            let mut bs = beam[b].bs.clone();
            for dy in trace2.get(tid) {
                k = trace.add(((x, y), (x - 1, y - dy)), k);
                bs.swap(id(x, y), id(x - 1, y - dy));
                x -= 1;
                y -= dy;
            }
            next.push(State { score, bs, id: k, used });
            if next.len() == W {
                break;
            }
        }
        beam = next;
    }
    trace.get(beam[0].id)
}

fn pos(bs: &Vec<i32>, i: i32) -> (usize, usize) {
    for x in 0..N {
        for y in 0..=x {
            if bs[id(x, y)] == i {
                return (x, y);
            }
        }
    }
    panic!();
}

struct State {
    bs: Vec<i32>,
    id: usize,
    score: (i32, i32),
    used: BitSet,
}

// 入出力と得点計算

const N: usize = 30;
const N2: usize = N * (N + 1) / 2;

fn id(x: usize, y: usize) -> usize {
    x * (x + 1) / 2 + y
}

pub type Output = Vec<((usize, usize), (usize, usize))>;

#[derive(Clone, Debug)]
pub struct Input {
    pub bs: Vec<i32>,
}

pub fn read_input() -> Input {
    input! {
        bs: [i32; N2]
    }
    Input { bs }
}

pub fn write_output(out: &Output) {
    println!("{}", out.len());
    for &((x1, y1), (x2, y2)) in out {
        println!("{} {} {} {}", x1, y1, x2, y2);
    }
}

// ここからライブラリ

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
        }
    }
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { vec![$($e),*] };
	($($e:expr,)*) => { vec![$($e),*] };
	($e:expr; $d:expr) => { vec![$e; $d] };
	($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

pub fn get_time() -> 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;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.3
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

struct Trace<T: Copy> {
    log: Vec<(T, usize)>,
}

impl<T: Copy> Trace<T> {
    fn new() -> Self {
        Trace { log: vec![] }
    }
    fn add(&mut self, c: T, p: usize) -> usize {
        self.log.push((c, p));
        self.log.len() - 1
    }
    fn get(&self, mut i: usize) -> Vec<T> {
        let mut out = vec![];
        while i != !0 {
            out.push(self.log[i].0);
            i = self.log[i].1;
        }
        out.reverse();
        out
    }
}

Submission Info

Judge Result