提出 #58799365

---

ソースコード 拡げる

#![allow(non_snake_case)]

use fixedbitset::FixedBitSet;
use proconio::{input, marker::Chars};
use rustc_hash::FxHashSet;
use std::collections::BinaryHeap;

fn main() {
    get_time();
    let input = read_input();
    let mut ret = Solution {
        arm: Arm::new(vec![]),
        root: (0, 0),
        moves: vec![],
    };
    let width1 = (1.5e5 / (input.V as f64 * input.M as f64)).round().max(1.0) as usize;
    eprintln!("!log width1 {}", width1);
    let mut best = !0;
    // 小さい幅のビームサーチでアームを色々試してみて、良さげなアームを求める
    for stem in (if input.V <= 6 { 1 } else { 2 }..=3.min(input.V - 1)).rev() {
        // 長さ stem のパスの先で分岐して残りを葉とする
        let mut ls = vec![input.N as i32 * 2 / 5];
        for i in 0..stem - 1 {
            let l = (ls[i] + 1) / 2;
            ls.push(l);
        }
        if ls[stem - 1] == 1 {
            continue;
        }
        ls.reverse();
        for b in 1..[6, 3, 2][stem - 1] {
            let mut arm = vec![];
            for i in 0..stem {
                arm.push((i, ls[i]));
            }
            for i in 0..input.V - 1 - stem {
                arm.push((stem, b + i as i32));
            }
            let arm = Arm::new(arm);
            if let Some(sol) = solve_beam(&input, arm, width1, false, best) {
                best = sol.moves.len();
                ret = sol;
                eprintln!("{:.3}: {} ({:?})", get_time(), best, ret.arm.pL);
            }
        }
    }
    if ret.arm.num_joint == 4 {
        // 長さ 4 のパスの頂点 3 と 4 に残りを葉としてつなげる
        let mut ls = vec![input.N as i32 * 2 / 5];
        for i in 0..2 {
            let l = (ls[i] + 1) / 2;
            ls.push(l);
        }
        ls.reverse();
        let mut arm = vec![];
        for i in 0..3 {
            arm.push((i, ls[i]));
        }
        arm.push((3, 1));
        let leaf1 = (input.V - 1 - 4) / 3;
        for i in 0..leaf1 {
            arm.push((3, 1 + i as i32));
        }
        for i in 0..(input.V - 1 - 4 - leaf1) {
            arm.push((4, 1 + i as i32));
        }
        let arm = Arm::new(arm);
        if let Some(sol) = solve_beam(&input, arm, width1, false, best) {
            best = sol.moves.len();
            ret = sol;
            eprintln!("{:.3}: {} ({:?})", get_time(), best, ret.arm.pL);
        }
    }
    eprintln!("!log time1 {:.3}", get_time());
    // 残りの時間で大きな幅でビームサーチして解を更新
    let width = (1e7 * (2.9 - get_time())
        / (f64::powi(3.0, ret.arm.num_joint as i32 - 1) * input.V as f64 * best as f64))
        .round()
        .max(1.0) as usize;
    eprintln!("!log width {width}");
    if let Some(sol) = solve_beam(&input, ret.arm.clone(), width, true, best) {
        best = sol.moves.len();
        ret = sol;
        eprintln!("{:.3}: {}", get_time(), best);
    }
    write_output(&ret);
    eprintln!("!log stem {}", ret.arm.num_joint - 1);
    eprintln!("Time = {:.3}", get_time());
}

/// 指定された腕に対し、ビームサーチで解を求める
fn solve_beam(
    input: &Input,
    arm: Arm,
    width: usize,
    auto_width: bool,
    best: usize,
) -> Option<Solution> {
    let root = (input.N as i32 / 2, input.N as i32 / 2);
    // 指先を移動させにくいマスは重みを大きくして重みの総和を評価値とする
    let weight = get_weight(input, &arm)?;
    let mut trace = Trace::new();
    let mut beam = vec![];
    // 初期位置は中心に近いマスからwidth個を選択
    let mut tmp = vec![];
    for i in 0..input.N as i32 {
        for j in 0..input.N as i32 {
            tmp.push(((i - root.0).abs() + (j - root.1).abs(), i, j));
        }
    }
    tmp.sort();
    tmp.truncate(width * 5);
    for (_, i, j) in tmp {
        let mut state = State::new(&input, &arm, (i, j), &weight);
        state.id = trace.add(vec![i as u8, j as u8], state.id);
        beam.push(state);
    }
    let mut used = FastBitSet::new(input.N2);
    let mut ps = vec![(0, 0, 0); arm.num_joint];
    let mut crt = 0;
    let stime = get_time();
    if stime >= 2.9 {
        return None;
    }
    let mut total_width = 0;
    let mut prev_width = width;
    while beam[0].eval > 0 {
        let width = if !auto_width || crt <= 1 {
            width
        } else {
            // これまでの幅の総和と経過時間から、幅1あたりの期待時間を求め、残りの時間とターン数に応じて幅を自動調整
            let t = (get_time() - stime) / (2.9 - stime);
            (total_width as f64 / t.max(1e-6) * (1.0 - t) / (best - crt) as f64)
                .round()
                .min(prev_width as f64 * 1.2)
                .max(1.0) as usize
        };
        prev_width = width;
        let mut cand = BoundedSortedList::new(width);
        let mut used2 = FxHashSet::default();
        for b in 0..beam.len() {
            if get_time() > 2.95 {
                return None;
            }
            let state = &beam[b];
            // 残りのターン全ての指先がフル稼働しても最適解を更新できないなら枝刈り
            if best != !0
                && crt as i64 + (state.eval % 1000 + arm.num_leaf as i64 - 1) / arm.num_leaf as i64
                    >= best as i64
            {
                continue;
            }
            let mut ok = false;
            if state.skip > 0 {
                // どの指先も稼働しなかった場合、あらゆる移動・回転が同じスコアになって多様性が失われるため、そのまま次状態を生成せずに1回休み状態としておく。
                // k(>0)回休むとk+1回の移動とあらゆる回転が可能になるのでまとめて処理する。
                for ri in 0..input.N as i32 {
                    for rj in 0..input.N as i32 {
                        if (ri - state.root.0).abs() + (rj - state.root.1).abs() > state.skip + 1
                            || !used2.insert((ri, rj, state.eval))
                        {
                            continue;
                        }
                        ps[0] = (ri, rj, 0);
                        ok |= all_rots(
                            input,
                            &arm,
                            &weight,
                            &mut cand,
                            b,
                            state,
                            &mut used,
                            &mut state.rot.clone(),
                            &mut ps,
                            1,
                        );
                    }
                }
            } else {
                // 根の移動4方向+移動なしに対し、全ての辺の回転を全通り試し、次状態を生成
                for rd in 0..5 {
                    if crt == 0 && rd != 4 {
                        continue;
                    }
                    let ri = state.root.0 + DIJ[rd].0;
                    let rj = state.root.1 + DIJ[rd].1;
                    if input.on(ri, rj) {
                        ps[0] = (ri, rj, 0);
                        ok |= all_rots(
                            input,
                            &arm,
                            &weight,
                            &mut cand,
                            b,
                            state,
                            &mut used,
                            &mut state.rot.clone(),
                            &mut ps,
                            1,
                        );
                    }
                }
            }
            if !ok {
                // どのように動かしても指先を稼働できなかった場合、1回休み状態にする
                cand.insert(state.eval, (b, -1, -1, vec![]));
            }
        }
        total_width += (beam.len() + cand.len()) / 2;
        let mut next = vec![];
        let mut used = FxHashSet::default();
        for (eval, (b, ri, rj, rot)) in cand.list() {
            let mut state = beam[b].clone();
            state.eval = eval;
            if ri == -1 && rj == -1 {
                // 一回休み状態
                state.skip += 1;
                state.last_moved.fill(false);
                if used.insert((state.root, vec![], state.holding.clone(), eval)) {
                    next.push(state);
                }
            } else {
                let mut ps = vec![(0, 0, 0); arm.num_joint];
                ps[0] = (ri, rj, 0);
                for u in 0..arm.num_joint - 1 {
                    let (p, L) = arm.pL[u];
                    let (mut i, mut j, mut r) = ps[p];
                    r = (r + rot[u]) & 3;
                    i += DIJ[r as usize].0 * L;
                    j += DIJ[r as usize].1 * L;
                    ps[u + 1] = (i, j, r);
                }
                for u in 0..arm.num_leaf {
                    let (p, L) = arm.pL[arm.num_joint - 1 + u];
                    let (i, j, r) = ps[p];
                    let r = (r + rot[arm.num_joint - 1 + u]) & 3;
                    let i = i + DIJ[r as usize].0 * L;
                    let j = j + DIJ[r as usize].1 * L;
                    state.last_moved[u] = false;
                    if input.on(i, j) {
                        let ij = i as usize * input.N + j as usize;
                        if state.holding[u] {
                            if !state.s[ij] && input.t[ij] {
                                state.s.set(ij, true);
                                state.holding[u] = false;
                                state.last_moved[u] = true;
                            }
                        } else {
                            if state.s[ij] && !input.t[ij] {
                                state.s.set(ij, false);
                                state.holding[u] = true;
                                state.last_moved[u] = true;
                            }
                        }
                    }
                }
                let mut rot2 = rot.clone();
                for u in 0..arm.num_leaf {
                    if !state.last_moved[u] {
                        rot2[arm.num_joint - 1 + u] = 4;
                    }
                }
                if used.insert(((ri, rj), rot2, state.holding.clone(), eval)) {
                    // コマンドを生成(1+休んだターン数一気に動く)
                    let mut cmds = vec![vec![b'.'; arm.V * 2]; state.skip as usize + 1];
                    let mut t = 0;
                    while state.root.0 < ri {
                        state.root.0 += 1;
                        cmds[t][0] = b'D';
                        t += 1;
                    }
                    while state.root.0 > ri {
                        state.root.0 -= 1;
                        cmds[t][0] = b'U';
                        t += 1;
                    }
                    while state.root.1 < rj {
                        state.root.1 += 1;
                        cmds[t][0] = b'R';
                        t += 1;
                    }
                    while state.root.1 > rj {
                        state.root.1 -= 1;
                        cmds[t][0] = b'L';
                        t += 1;
                    }
                    state.skip = 0;
                    state.rot = rot;
                    let cmd = cmds.last_mut().unwrap();
                    for u in 0..arm.V - 1 {
                        match (state.rot[u] + 4 - beam[b].rot[u]) & 3 {
                            1 => cmd[1 + u] = b'R',
                            2 => cmd[1 + u] = b'U', // 休み明けは180度回転可能なので`U`とし、出力時に`RR`に変換
                            3 => cmd[1 + u] = b'L',
                            _ => (),
                        }
                    }
                    for u in 0..arm.num_leaf {
                        if state.last_moved[u] {
                            cmd[arm.V + arm.num_joint + u] = b'P';
                        }
                    }
                    for cmd in cmds {
                        state.id = trace.add(cmd, state.id);
                    }
                    next.push(state);
                }
            }
        }
        beam = next;
        if beam.len() == 0 {
            return None;
        }
        crt += 1;
    }
    let mut moves = trace.get(beam[0].id);
    let root = (moves[0][0] as i32, moves[0][1] as i32);
    moves.remove(0);
    Some(Solution { arm, root, moves })
}

/// 評価関数で用いる定数
const C: i64 = 6;
/// 関節が盤面からどれだけはみ出すのを許容するか
const MARGIN: i32 = 2;

/// 全ての辺の回転を再帰的に全列挙し、次状態を生成する
fn all_rots(
    input: &Input,
    arm: &Arm,
    weight: &Vec<i64>,
    cand: &mut BoundedSortedList<i64, (usize, i32, i32, Vec<u8>)>,
    b: usize,
    state: &State,
    used: &mut FastBitSet,
    rot: &mut Vec<u8>,
    ps: &mut Vec<(i32, i32, u8)>,
    u: usize,
) -> bool {
    if u == arm.num_joint {
        let mut eval = state.eval;
        // 同じターンにたこ焼きを取り合わないように変化したマスを記憶しておく
        used.clear();
        for u in 0..arm.num_leaf {
            // 各指先は、1手で掴む・離すことの出来るマスのうちで一番重みが大きいマスに向けて回転する
            let (p, L) = arm.pL[arm.num_joint - 1 + u];
            let (i, j, mut r) = ps[p];
            r = (r + state.rot[arm.num_joint - 1 + u]) & 3;
            let mut best_dir = 0;
            let mut best = 0;
            for dir in 0..4 {
                // 前のターンに稼働しなかった指先は2ターンかけて180度回転することができる
                if dir == 2 && state.last_moved[u] {
                    continue;
                }
                let r = (r + dir) & 3;
                let i = i + DIJ[r as usize].0 * L;
                let j = j + DIJ[r as usize].1 * L;
                if input.on(i, j) {
                    let ij = i as usize * input.N + j as usize;
                    if used[ij] {
                        continue;
                    }
                    if state.holding[u] && !state.s[ij] && input.t[ij]
                        || !state.holding[u] && state.s[ij] && !input.t[ij]
                    {
                        let mut delta = weight[ij];
                        // 未完成のマスが孤立している状態より隣接している状態の方が解きやすいので
                        // 評価関数として Σ_{p:未完成} w[p] - Σ_{pq:隣接する未完成} min(w[p],w[q])/C を用いる
                        for &(di, dj) in &DIJ[..4] {
                            let i2 = i + di;
                            let j2 = j + dj;
                            let ij2 = i2 as usize * input.N + j2 as usize;
                            if input.on(i2, j2) && (state.s[ij2] ^ used[ij2]) != input.t[ij2] {
                                delta -= weight[ij].min(weight[ij2]) / C;
                            }
                        }
                        if best.setmax(delta) {
                            best_dir = dir;
                        }
                    }
                }
            }
            eval -= best;
            rot[arm.num_joint - 1 + u] = (state.rot[arm.num_joint - 1 + u] + best_dir) & 3;
            if best > 0 {
                let r = (r + best_dir) & 3;
                let i = i + DIJ[r as usize].0 * L;
                let j = j + DIJ[r as usize].1 * L;
                let ij = i as usize * input.N + j as usize;
                used.set(ij);
            }
        }
        if eval != state.eval {
            if cand.can_insert(eval) {
                cand.insert(eval, (b, ps[0].0, ps[0].1, rot.clone()));
            }
            true
        } else {
            false
        }
    } else {
        // 再帰的に回転を全列挙
        let mut ok = false;
        for d in 0..4 {
            // 一回休み状態の場合は180度回転も試す
            if d != 2 || state.skip > 0 {
                let (p, L) = arm.pL[u - 1];
                let (i, j, r) = ps[p];
                let r = (rot[u - 1] + r) & 3;
                ps[u] = (i + DIJ[r as usize].0 * L, j + DIJ[r as usize].1 * L, r);
                if -MARGIN <= ps[u].0
                    && ps[u].0 < input.N as i32 + MARGIN
                    && -MARGIN <= ps[u].1
                    && ps[u].1 < input.N as i32 + MARGIN
                {
                    ok |= all_rots(input, arm, weight, cand, b, state, used, rot, ps, u + 1);
                }
            }
            rot[u - 1] = (rot[u - 1] + 1) & 3;
        }
        ok
    }
}

/// 各マスの重みを計算
/// DPにより、各指先がマス(i,j)に存在するようなアームの状態数を求め、その総和の逆数を重みとする
fn get_weight(input: &Input, arm: &Arm) -> Option<Vec<i64>> {
    let mut weight = vec![0; input.N2];
    let N = 2 * MARGIN + 2 + input.N as i32;
    let mut ps = vec![vec![0; (N * N) as usize]; arm.V];
    for ri in 0..input.N as i32 {
        for rj in 0..input.N as i32 {
            ps[0][((ri + MARGIN) * N + rj + MARGIN) as usize] = 1;
        }
    }
    for u in 1..arm.V {
        let (p, L) = arm.pL[u - 1];
        for i in 0..N {
            for j in 0..N {
                if ps[p][(i * N + j) as usize] > 0 {
                    for &(di, dj) in &DIJ[..4] {
                        let i2 = i + di * L;
                        let j2 = j + dj * L;
                        if 0 <= i2 && i2 < N && 0 <= j2 && j2 < N {
                            ps[u][(i2 * N + j2) as usize] += ps[p][(i * N + j) as usize];
                        }
                    }
                }
            }
        }
    }
    let mut tot = vec![0; input.N2];
    for u in arm.num_joint..arm.V {
        for i in 0..input.N {
            for j in 0..input.N {
                tot[i * input.N + j] +=
                    ps[u][((i as i32 + MARGIN) * N + j as i32 + MARGIN) as usize];
            }
        }
    }
    for p in 0..input.N2 {
        if input.s[p] != input.t[p] {
            if tot[p] == 0 {
                return None;
            }
            weight[p] = (1000000000 / tot[p]) * 1000 * C + 1;
        }
    }
    Some(weight)
}

#[derive(Clone, Debug)]
struct Arm {
    V: usize,
    pL: Vec<(usize, i32)>,
    num_joint: usize,
    num_leaf: usize,
}

impl Arm {
    fn new(pL: Vec<(usize, i32)>) -> Self {
        let V = pL.len() + 1;
        let mut is_leaf = vec![true; V];
        for &(p, _) in &pL {
            is_leaf[p] = false;
        }
        let num_joint = is_leaf.iter().filter(|&&b| !b).count();
        Self {
            V,
            pL,
            num_joint,
            num_leaf: V - num_joint,
        }
    }
}

struct Solution {
    arm: Arm,
    root: (i32, i32),
    moves: Vec<Vec<u8>>,
}

#[derive(Clone, Debug)]
struct State {
    s: FixedBitSet,
    rot: Vec<u8>,
    holding: Vec<bool>,
    last_moved: Vec<bool>,
    root: (i32, i32),
    skip: i32,
    eval: i64,
    id: usize,
}

impl State {
    fn new(input: &Input, arm: &Arm, root: (i32, i32), weight: &Vec<i64>) -> Self {
        let mut eval = 0;
        for p in 0..input.N2 {
            if input.s[p] != input.t[p] {
                eval += weight[p];
                if p % input.N + 1 < input.N {
                    if input.s[p + 1] != input.t[p + 1] {
                        eval -= weight[p].min(weight[p + 1]) / C;
                    }
                }
                if p / input.N + 1 < input.N {
                    if input.s[p + input.N] != input.t[p + input.N] {
                        eval -= weight[p].min(weight[p + input.N]) / C;
                    }
                }
            }
        }
        Self {
            s: input.s.clone(),
            rot: vec![0; arm.pL.len()],
            holding: vec![false; arm.V - arm.num_joint],
            last_moved: vec![true; arm.V - arm.num_joint],
            root,
            skip: 0,
            eval,
            id: !0,
        }
    }
}

// 入出力と得点計算

const DIJ: [(i32, i32); 5] = [(0, 1), (1, 0), (0, -1), (-1, 0), (0, 0)];

#[allow(unused)]
struct Input {
    N: usize,
    N2: usize,
    M: usize,
    V: usize,
    s: FixedBitSet,
    t: Vec<bool>,
}

impl Input {
    fn on(&self, x: i32, y: i32) -> bool {
        0 <= x && x < self.N as i32 && 0 <= y && y < self.N as i32
    }
}

fn read_input() -> Input {
    input! {
        N: usize,
        M: usize,
        V: usize,
        s2: [Chars; N],
        t: [Chars; N],
    }
    let mut s = FixedBitSet::with_capacity(N * N);
    for i in 0..N {
        for j in 0..N {
            s.set(i * N + j, s2[i][j] == '1');
        }
    }
    let t = t.into_iter().flatten().map(|c| c == '1').collect();
    Input {
        N,
        N2: N * N,
        M,
        V,
        s,
        t,
    }
}

fn write_output(sol: &Solution) {
    println!("{}", sol.arm.V);
    for &(p, L) in &sol.arm.pL {
        println!("{} {}", p, L);
    }
    println!("{} {}", sol.root.0, sol.root.1);
    let mut moves = sol.moves.clone();
    for t in 1..moves.len() {
        for u in 1..sol.arm.V {
            if moves[t][u] == b'U' {
                assert_eq!(moves[t - 1][u], b'.', "{}/{}", u, sol.arm.num_joint);
                moves[t][u] = b'R';
                moves[t - 1][u] = b'R';
            }
        }
    }
    for cmd in moves {
        println!("{}", String::from_utf8(cmd).unwrap());
    }
}

// ここからライブラリ

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

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.2
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

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

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

#[derive(Clone, Debug)]
struct Entry<K, V> {
    k: K,
    v: V,
}

impl<K: PartialOrd, V> Ord for Entry<K, V> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl<K: PartialOrd, V> PartialOrd for Entry<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.k.partial_cmp(&other.k)
    }
}

impl<K: PartialEq, V> PartialEq for Entry<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.k.eq(&other.k)
    }
}

impl<K: PartialEq, V> Eq for Entry<K, V> {}

/// K が小さいトップn個を保持
#[derive(Clone, Debug)]
pub struct BoundedSortedList<K: PartialOrd + Copy, V: Clone> {
    que: BinaryHeap<Entry<K, V>>,
    size: usize,
}

impl<K: PartialOrd + Copy, V: Clone> BoundedSortedList<K, V> {
    pub fn new(size: usize) -> Self {
        Self {
            que: BinaryHeap::with_capacity(size),
            size,
        }
    }
    pub fn can_insert(&self, k: K) -> bool {
        self.que.len() < self.size || self.que.peek().unwrap().k > k
    }
    pub fn insert(&mut self, k: K, v: V) {
        if self.que.len() < self.size {
            self.que.push(Entry { k, v });
        } else if let Some(mut top) = self.que.peek_mut() {
            if top.k > k {
                top.k = k;
                top.v = v;
            }
        }
    }
    pub fn list(self) -> Vec<(K, V)> {
        let v = self.que.into_sorted_vec();
        v.into_iter().map(|e| (e.k, e.v)).collect()
    }
    pub fn len(&self) -> usize {
        self.que.len()
    }
}

struct FastBitSet {
    bs: Vec<u32>,
    id: u32,
}

impl FastBitSet {
    fn new(n: usize) -> Self {
        Self {
            bs: vec![0; n],
            id: 1,
        }
    }
    fn clear(&mut self) {
        self.id += 1;
    }
    fn set(&mut self, i: usize) {
        self.bs[i] = self.id;
    }
}

impl std::ops::Index<usize> for FastBitSet {
    type Output = bool;
    fn index(&self, i: usize) -> &bool {
        if self.bs[i] == self.id {
            &true
        } else {
            &false
        }
    }
}

提出情報

ジャッジ結果