提出 #73751556

---

ソースコード 拡げる

use std::io::{self, Read};
use std::str::FromStr;
use std::collections::HashMap;

struct Scanner {
    buf: Vec<u8>,
    idx: usize,
}

impl Scanner {
    fn new() -> Self {
        let mut input = String::new();
        io::stdin().read_to_string(&mut input).unwrap();
        Self {
            buf: input.into_bytes(),
            idx: 0,
        }
    }

    fn next<T: FromStr>(&mut self) -> T {
        while self.idx < self.buf.len() && self.buf[self.idx].is_ascii_whitespace() {
            self.idx += 1;
        }
        let start = self.idx;
        while self.idx < self.buf.len() && !self.buf[self.idx].is_ascii_whitespace() {
            self.idx += 1;
        }
        std::str::from_utf8(&self.buf[start..self.idx])
            .unwrap()
            .parse::<T>()
            .ok()
            .unwrap()
    }
}

#[derive(Clone)]
struct RobotPlan {
    i: usize,
    j: usize,
    d: char,
    trans: Vec<(char, usize, char, usize)>,
}

impl RobotPlan {
    fn m(&self) -> usize {
        self.trans.len()
    }
}

#[derive(Clone)]
struct Candidate {
    cost: usize,
    mask: Vec<u64>,
    robot: RobotPlan,
}

fn set_bit(mask: &mut [u64], idx: usize) {
    mask[idx >> 6] |= 1_u64 << (idx & 63);
}

fn count_intersection(a: &[u64], b: &[u64]) -> usize {
    a.iter()
        .zip(b.iter())
        .map(|(&x, &y)| (x & y).count_ones() as usize)
        .sum()
}

fn any_bit(mask: &[u64]) -> bool {
    mask.iter().any(|&x| x != 0)
}

fn for_each_bit(mask: &[u64], mut f: impl FnMut(usize)) {
    for (w, &bits0) in mask.iter().enumerate() {
        let mut bits = bits0;
        while bits != 0 {
            let t = bits.trailing_zeros() as usize;
            f((w << 6) + t);
            bits &= bits - 1;
        }
    }
}

fn splitmix64(mut x: u64) -> u64 {
    x = x.wrapping_add(0x9e3779b97f4a7c15);
    x = (x ^ (x >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94d049bb133111eb);
    x ^ (x >> 31)
}

fn next_rand(state: &mut u64) -> u64 {
    *state = splitmix64(*state);
    *state
}

fn env_usize(name: &str, default: usize) -> usize {
    std::env::var(name)
        .ok()
        .and_then(|s| s.parse::<usize>().ok())
        .unwrap_or(default)
}

fn mask_popcount(mask: &[u64]) -> usize {
    mask.iter().map(|&x| x.count_ones() as usize).sum()
}

fn dir_char(d: usize) -> char {
    match d {
        0 => 'U',
        1 => 'R',
        2 => 'D',
        _ => 'L',
    }
}

fn front_blocked(n: usize, v: &[Vec<u8>], h: &[Vec<u8>], i: usize, j: usize, d: usize) -> bool {
    match d {
        0 => i == 0 || h[i - 1][j] == 1,    // U
        1 => j == n - 1 || v[i][j] == 1,    // R
        2 => i == n - 1 || h[i][j] == 1,    // D
        _ => j == 0 || v[i][j - 1] == 1,    // L
    }
}

fn apply_action(i: usize, j: usize, d: usize, a: char) -> (usize, usize, usize) {
    match a {
        'R' => (i, j, (d + 1) & 3),
        'L' => (i, j, (d + 3) & 3),
        'F' => match d {
            0 => (i - 1, j, d),
            1 => (i, j + 1, d),
            2 => (i + 1, j, d),
            _ => (i, j - 1, d),
        },
        _ => unreachable!(),
    }
}

fn generate_one_state_candidates(
    n: usize,
    v: &[Vec<u8>],
    h: &[Vec<u8>],
    words: usize,
) -> Vec<Candidate> {
    let options = [('F', 'R'), ('F', 'L'), ('R', 'R'), ('R', 'L'), ('L', 'R'), ('L', 'L')];
    let s = n * n * 4;
    let mut out = Vec::new();

    for &(a0, a1) in &options {
        let mut next = vec![0usize; s];
        for node in 0..s {
            let cell = node >> 2;
            let d = node & 3;
            let i = cell / n;
            let j = cell % n;
            let blocked = front_blocked(n, v, h, i, j, d);
            let action = if blocked { a1 } else { a0 };
            let (ni, nj, nd) = apply_action(i, j, d, action);
            next[node] = (((ni * n) + nj) << 2) | nd;
        }

        let mut node_cycle = vec![usize::MAX; s];
        let mut pos = vec![usize::MAX; s];
        let mut cycle_masks: Vec<Vec<u64>> = Vec::new();
        let mut cycle_rep: Vec<usize> = Vec::new();

        for start in 0..s {
            if node_cycle[start] != usize::MAX {
                continue;
            }
            let mut stack: Vec<usize> = Vec::new();
            let mut cur = start;
            while node_cycle[cur] == usize::MAX && pos[cur] == usize::MAX {
                pos[cur] = stack.len();
                stack.push(cur);
                cur = next[cur];
            }

            if node_cycle[cur] != usize::MAX {
                let cid = node_cycle[cur];
                for &u in stack.iter().rev() {
                    node_cycle[u] = cid;
                }
            } else {
                let p = pos[cur];
                let cycle_nodes = &stack[p..];
                let mut mask = vec![0_u64; words];
                for &u in cycle_nodes {
                    set_bit(&mut mask, u >> 2);
                }
                let cid = cycle_masks.len();
                cycle_masks.push(mask);
                cycle_rep.push(cycle_nodes[0]);
                for &u in cycle_nodes {
                    node_cycle[u] = cid;
                }
                for &u in stack[..p].iter().rev() {
                    node_cycle[u] = cid;
                }
            }

            for &u in &stack {
                pos[u] = usize::MAX;
            }
        }

        for cid in 0..cycle_masks.len() {
            let rep = cycle_rep[cid];
            let cell = rep >> 2;
            let d = rep & 3;
            let i = cell / n;
            let j = cell % n;
            out.push(Candidate {
                cost: 1,
                mask: cycle_masks[cid].clone(),
                robot: RobotPlan {
                    i,
                    j,
                    d: dir_char(d),
                    trans: vec![(a0, 0, a1, 0)],
                },
            });
        }
    }

    out
}

fn generate_row_segment_candidates(n: usize, v: &[Vec<u8>], words: usize) -> Vec<Candidate> {
    let mut out = Vec::new();
    for i in 0..n {
        let mut j = 0usize;
        while j < n {
            let start = j;
            let mut mask = vec![0_u64; words];
            set_bit(&mut mask, i * n + j);
            while j + 1 < n && v[i][j] == 0 {
                j += 1;
                set_bit(&mut mask, i * n + j);
            }
            out.push(Candidate {
                cost: 2,
                mask,
                robot: RobotPlan {
                    i,
                    j: start,
                    d: 'R',
                    trans: vec![('F', 0, 'R', 1), ('R', 0, 'R', 0)],
                },
            });
            j += 1;
        }
    }
    out
}

fn generate_col_segment_candidates(n: usize, h: &[Vec<u8>], words: usize) -> Vec<Candidate> {
    let mut out = Vec::new();
    for j in 0..n {
        let mut i = 0usize;
        while i < n {
            let start = i;
            let mut mask = vec![0_u64; words];
            set_bit(&mut mask, i * n + j);
            while i + 1 < n && h[i][j] == 0 {
                i += 1;
                set_bit(&mut mask, i * n + j);
            }
            out.push(Candidate {
                cost: 2,
                mask,
                robot: RobotPlan {
                    i: start,
                    j,
                    d: 'D',
                    trans: vec![('F', 0, 'R', 1), ('R', 0, 'R', 0)],
                },
            });
            i += 1;
        }
    }
    out
}

fn generate_two_state_candidates(
    n: usize,
    v: &[Vec<u8>],
    h: &[Vec<u8>],
    words: usize,
) -> Vec<Candidate> {
    let cells = n * n;
    let s = cells * 4 * 2;
    let a0s = ['F', 'R', 'L'];
    let a1s = ['R', 'L'];

    let mut state_cfgs = Vec::new();
    for &a0 in &a0s {
        for b0 in 0..2 {
            for &a1 in &a1s {
                for b1 in 0..2 {
                    state_cfgs.push((a0, b0, a1, b1));
                }
            }
        }
    }

    let mut out = Vec::new();
    for &c0 in &state_cfgs {
        for &c1 in &state_cfgs {
            let trans = [c0, c1];
            let mut next = vec![0usize; s];
            for node in 0..s {
                let st = node & 1;
                let dir = (node >> 1) & 3;
                let cell = node >> 3;
                let i = cell / n;
                let j = cell % n;
                let wall = front_blocked(n, v, h, i, j, dir);
                let (a, b) = if !wall {
                    (trans[st].0, trans[st].1)
                } else {
                    (trans[st].2, trans[st].3)
                };
                let (ni, nj, nd) = apply_action(i, j, dir, a);
                next[node] = ((((ni * n + nj) << 2) | nd) << 1) | b;
            }

            let mut node_cycle = vec![usize::MAX; s];
            let mut pos = vec![usize::MAX; s];
            let mut cycle_masks: Vec<Vec<u64>> = Vec::new();
            let mut rep_start: Vec<usize> = Vec::new();

            for start in 0..s {
                if node_cycle[start] != usize::MAX {
                    continue;
                }
                let mut stack = Vec::new();
                let mut cur = start;
                while node_cycle[cur] == usize::MAX && pos[cur] == usize::MAX {
                    pos[cur] = stack.len();
                    stack.push(cur);
                    cur = next[cur];
                }
                if node_cycle[cur] != usize::MAX {
                    let cid = node_cycle[cur];
                    for &u in stack.iter().rev() {
                        node_cycle[u] = cid;
                    }
                } else {
                    let p = pos[cur];
                    let mut mask = vec![0_u64; words];
                    for &u in &stack[p..] {
                        set_bit(&mut mask, u >> 3);
                    }
                    let cid = cycle_masks.len();
                    cycle_masks.push(mask);
                    rep_start.push(usize::MAX);
                    for &u in &stack[p..] {
                        node_cycle[u] = cid;
                    }
                    for &u in stack[..p].iter().rev() {
                        node_cycle[u] = cid;
                    }
                }
                for &u in &stack {
                    pos[u] = usize::MAX;
                }
            }

            for cell in 0..cells {
                for d in 0..4 {
                    let node = ((cell << 2) | d) << 1; // internal state = 0
                    let cid = node_cycle[node];
                    if rep_start[cid] == usize::MAX {
                        rep_start[cid] = node;
                    }
                }
            }

            for (cid, &node) in rep_start.iter().enumerate() {
                if node == usize::MAX {
                    continue;
                }
                let cell = node >> 3;
                let d = (node >> 1) & 3;
                let i = cell / n;
                let j = cell % n;
                out.push(Candidate {
                    cost: 2,
                    mask: cycle_masks[cid].clone(),
                    robot: RobotPlan {
                        i,
                        j,
                        d: dir_char(d),
                        trans: vec![
                            (trans[0].0, trans[0].1, trans[0].2, trans[0].3),
                            (trans[1].0, trans[1].1, trans[1].2, trans[1].3),
                        ],
                    },
                });
            }
        }
    }

    out
}

fn generate_random_m_state_candidates(
    n: usize,
    v: &[Vec<u8>],
    h: &[Vec<u8>],
    words: usize,
    m: usize,
    automata_count: usize,
    picks_per_automaton: usize,
    seed: u64,
) -> Vec<Candidate> {
    let cells = n * n;
    let s = cells * 4 * m;
    let a0s = ['F', 'R', 'L'];
    let a1s = ['R', 'L'];
    let mut rng = seed ^ (m as u64).wrapping_mul(0xabc9_8731_55aa_41c7);
    let mut out = Vec::new();

    for _ in 0..automata_count {
        let mut trans = vec![('F', 0usize, 'R', 0usize); m];
        let mut has_f = false;
        for st in 0..m {
            let a0 = a0s[(next_rand(&mut rng) % (a0s.len() as u64)) as usize];
            if a0 == 'F' {
                has_f = true;
            }
            let b0 = (next_rand(&mut rng) % (m as u64)) as usize;
            let a1 = a1s[(next_rand(&mut rng) % (a1s.len() as u64)) as usize];
            let b1 = (next_rand(&mut rng) % (m as u64)) as usize;
            trans[st] = (a0, b0, a1, b1);
        }
        if !has_f {
            continue;
        }

        let mut next = vec![0usize; s];
        for node in 0..s {
            let st = node % m;
            let q = node / m;
            let d = q & 3;
            let cell = q >> 2;
            let i = cell / n;
            let j = cell % n;
            let wall = front_blocked(n, v, h, i, j, d);
            let (a, b) = if !wall {
                (trans[st].0, trans[st].1)
            } else {
                (trans[st].2, trans[st].3)
            };
            let (ni, nj, nd) = apply_action(i, j, d, a);
            next[node] = ((((ni * n + nj) << 2) | nd) * m) + b;
        }

        let mut node_cycle = vec![usize::MAX; s];
        let mut pos = vec![usize::MAX; s];
        let mut cycle_masks: Vec<Vec<u64>> = Vec::new();
        let mut rep_start: Vec<usize> = Vec::new();

        for start in 0..s {
            if node_cycle[start] != usize::MAX {
                continue;
            }
            let mut stack = Vec::new();
            let mut cur = start;
            while node_cycle[cur] == usize::MAX && pos[cur] == usize::MAX {
                pos[cur] = stack.len();
                stack.push(cur);
                cur = next[cur];
            }
            if node_cycle[cur] != usize::MAX {
                let cid = node_cycle[cur];
                for &u in stack.iter().rev() {
                    node_cycle[u] = cid;
                }
            } else {
                let p = pos[cur];
                let mut mask = vec![0_u64; words];
                for &u in &stack[p..] {
                    set_bit(&mut mask, (u / m) >> 2);
                }
                let cid = cycle_masks.len();
                cycle_masks.push(mask);
                rep_start.push(usize::MAX);
                for &u in &stack[p..] {
                    node_cycle[u] = cid;
                }
                for &u in stack[..p].iter().rev() {
                    node_cycle[u] = cid;
                }
            }
            for &u in &stack {
                pos[u] = usize::MAX;
            }
        }

        for cell in 0..cells {
            for d in 0..4 {
                let node = (((cell << 2) | d) * m) + 0;
                let cid = node_cycle[node];
                if rep_start[cid] == usize::MAX {
                    rep_start[cid] = node;
                }
            }
        }

        let mut picks = Vec::new();
        for (cid, &node) in rep_start.iter().enumerate() {
            if node == usize::MAX {
                continue;
            }
            let sz = mask_popcount(&cycle_masks[cid]);
            picks.push((sz, cid, node));
        }
        picks.sort_by_key(|&(sz, _, node)| (std::cmp::Reverse(sz), node));
        picks.truncate(picks_per_automaton);

        for (_, cid, node) in picks {
            let cell = (node / m) >> 2;
            let d = (node / m) & 3;
            let i = cell / n;
            let j = cell % n;
            out.push(Candidate {
                cost: m,
                mask: cycle_masks[cid].clone(),
                robot: RobotPlan {
                    i,
                    j,
                    d: dir_char(d),
                    trans: trans.clone(),
                },
            });
        }
    }

    out
}

fn build_candidate_cells(candidates: &[Candidate], cells: usize) -> Vec<Vec<usize>> {
    let mut out = Vec::with_capacity(candidates.len());
    for c in candidates {
        let mut v = Vec::new();
        for_each_bit(&c.mask, |p| {
            if p < cells {
                v.push(p);
            }
        });
        out.push(v);
    }
    out
}

fn improve_by_add_remove(
    candidates: &[Candidate],
    cand_cells: &[Vec<usize>],
    mut selected: Vec<usize>,
    cells: usize,
) -> Vec<usize> {
    let n = candidates.len();
    let mut sel = vec![false; n];
    for &idx in &selected {
        sel[idx] = true;
    }

    let mut cnt = vec![0_u16; cells];
    for &idx in &selected {
        for &p in &cand_cells[idx] {
            cnt[p] += 1;
        }
    }

    let mut order: Vec<usize> = (0..n).collect();
    order.sort_by_key(|&idx| std::cmp::Reverse(candidates[idx].cost));

    for it in 0..4 {
        let mut best_add = usize::MAX;
        let mut best_removed: Vec<usize> = Vec::new();
        let mut best_delta = 0_i32;

        let mut add_order: Vec<usize> = (0..n).filter(|&idx| !sel[idx]).collect();
        add_order.sort_by_key(|&idx| splitmix64((it as u64) ^ ((idx as u64) * 0x9e3779b97f4a7c15)));
        for &add_idx in add_order.iter().take(1024) {
            if sel[add_idx] {
                continue;
            }
            let mut cnt2 = cnt.clone();
            for &p in &cand_cells[add_idx] {
                cnt2[p] += 1;
            }
            let mut removed = Vec::new();
            let mut removed_cost = 0_i32;

            for &idx in &order {
                if !sel[idx] {
                    continue;
                }
                let mut ok = true;
                for &p in &cand_cells[idx] {
                    if cnt2[p] <= 1 {
                        ok = false;
                        break;
                    }
                }
                if ok {
                    for &p in &cand_cells[idx] {
                        cnt2[p] -= 1;
                    }
                    removed.push(idx);
                    removed_cost += candidates[idx].cost as i32;
                }
            }

            let delta = candidates[add_idx].cost as i32 - removed_cost;
            if delta < best_delta {
                best_delta = delta;
                best_add = add_idx;
                best_removed = removed;
            }
        }

        if best_add == usize::MAX {
            break;
        }

        sel[best_add] = true;
        for &p in &cand_cells[best_add] {
            cnt[p] += 1;
        }
        selected.push(best_add);

        for &idx in &best_removed {
            if !sel[idx] {
                continue;
            }
            sel[idx] = false;
            for &p in &cand_cells[idx] {
                cnt[p] -= 1;
            }
        }
        selected.retain(|&idx| sel[idx]);
    }

    selected
}

fn improve_by_drop_repair(
    candidates: &[Candidate],
    cand_cells: &[Vec<usize>],
    selected: Vec<usize>,
    cells: usize,
    seed: u64,
    passes: usize,
) -> Vec<usize> {
    let n = candidates.len();
    let mut sel = vec![false; n];
    for &idx in &selected {
        sel[idx] = true;
    }
    let mut cnt = vec![0_u16; cells];
    let mut cost: i32 = 0;
    for &idx in &selected {
        cost += candidates[idx].cost as i32;
        for &p in &cand_cells[idx] {
            cnt[p] += 1;
        }
    }

    for pass in 0..(passes as u64) {
        let mut sel_list: Vec<usize> = (0..n).filter(|&idx| sel[idx]).collect();
        sel_list.sort_by_key(|&idx| {
            (
                std::cmp::Reverse(candidates[idx].cost),
                splitmix64(seed ^ pass ^ ((idx as u64) * 0x9e3779b97f4a7c15)),
            )
        });
        let mut improved = false;

        for rm in sel_list {
            let mut lsel = sel.clone();
            let mut lcnt = cnt.clone();
            let mut lcost = cost;
            lsel[rm] = false;
            lcost -= candidates[rm].cost as i32;
            for &p in &cand_cells[rm] {
                lcnt[p] -= 1;
            }

            let mut uncovered = 0usize;
            for &x in &lcnt {
                if x == 0 {
                    uncovered += 1;
                }
            }
            if uncovered == 0 && lcost < cost {
                sel = lsel;
                cnt = lcnt;
                cost = lcost;
                improved = true;
                break;
            }

            while uncovered > 0 && lcost < cost {
                let mut best_idx = usize::MAX;
                let mut best_gain = 0usize;
                let mut best_cost = 1usize;
                let mut best_key = u64::MAX;

                for idx in 0..n {
                    if lsel[idx] {
                        continue;
                    }
                    let mut gain = 0usize;
                    for &p in &cand_cells[idx] {
                        if lcnt[p] == 0 {
                            gain += 1;
                        }
                    }
                    if gain == 0 {
                        continue;
                    }
                    let c = candidates[idx].cost;
                    let key = splitmix64(seed ^ pass ^ ((idx as u64) * 0xbf58476d1ce4e5b9));
                    let better = if best_idx == usize::MAX {
                        true
                    } else {
                        let lhs = gain * best_cost;
                        let rhs = best_gain * c;
                        lhs > rhs
                            || (lhs == rhs
                                && (gain > best_gain
                                    || (gain == best_gain
                                        && (c < best_cost || (c == best_cost && key < best_key)))))
                    };
                    if better {
                        best_idx = idx;
                        best_gain = gain;
                        best_cost = c;
                        best_key = key;
                    }
                }

                if best_idx == usize::MAX {
                    break;
                }
                lsel[best_idx] = true;
                lcost += candidates[best_idx].cost as i32;
                for &p in &cand_cells[best_idx] {
                    if lcnt[p] == 0 {
                        uncovered -= 1;
                    }
                    lcnt[p] += 1;
                }
            }

            if uncovered == 0 && lcost < cost {
                sel = lsel;
                cnt = lcnt;
                cost = lcost;
                improved = true;
                break;
            }
        }

        if !improved {
            break;
        }
    }

    (0..n).filter(|&idx| sel[idx]).collect()
}

fn dedup_candidates(candidates: Vec<Candidate>) -> Vec<Candidate> {
    let mut out: Vec<Candidate> = Vec::new();
    let mut pos: HashMap<Vec<u64>, usize> = HashMap::new();
    for c in candidates {
        if let Some(&idx) = pos.get(&c.mask) {
            if c.cost < out[idx].cost {
                out[idx] = c;
            }
        } else {
            let idx = out.len();
            pos.insert(c.mask.clone(), idx);
            out.push(c);
        }
    }
    out
}

fn solve_weighted_cover(candidates: &[Candidate], cells: usize, seed: u64) -> Vec<usize> {
    let words = (cells + 63) >> 6;
    let mut uncovered = vec![!0_u64; words];
    if cells & 63 != 0 {
        uncovered[words - 1] = (1_u64 << (cells & 63)) - 1;
    }

    let mut used = vec![false; candidates.len()];
    let mut selected: Vec<usize> = Vec::new();

    while any_bit(&uncovered) {
        let mut best_idx = usize::MAX;
        let mut best_gain = 0usize;
        let mut best_cost = 1usize;
        let mut best_key = u64::MAX;

        for (idx, c) in candidates.iter().enumerate() {
            if used[idx] {
                continue;
            }
            let gain = count_intersection(&c.mask, &uncovered);
            if gain == 0 {
                continue;
            }
            let better = if best_idx == usize::MAX {
                true
            } else {
                let lhs = gain * best_cost;
                let rhs = best_gain * c.cost;
                let key = splitmix64(seed ^ (idx as u64).wrapping_mul(0x9e3779b97f4a7c15));
                lhs > rhs
                    || (lhs == rhs
                        && (gain > best_gain
                            || (gain == best_gain
                                && (c.cost < best_cost
                                    || (c.cost == best_cost && key < best_key)))))
            };
            if better {
                best_idx = idx;
                best_gain = gain;
                best_cost = c.cost;
                best_key = splitmix64(seed ^ (idx as u64).wrapping_mul(0x9e3779b97f4a7c15));
            }
        }

        if best_idx == usize::MAX {
            break;
        }
        used[best_idx] = true;
        selected.push(best_idx);
        for (u, &m) in uncovered.iter_mut().zip(candidates[best_idx].mask.iter()) {
            *u &= !m;
        }
    }

    let mut cnt = vec![0_u16; cells];
    for &idx in &selected {
        for_each_bit(&candidates[idx].mask, |p| {
            if p < cells {
                cnt[p] += 1;
            }
        });
    }

    let mut active = vec![true; selected.len()];
    loop {
        let mut changed = false;
        for t in (0..selected.len()).rev() {
            if !active[t] {
                continue;
            }
            let idx = selected[t];
            let mut removable = true;
            for_each_bit(&candidates[idx].mask, |p| {
                if p < cells && cnt[p] <= 1 {
                    removable = false;
                }
            });
            if removable {
                active[t] = false;
                changed = true;
                for_each_bit(&candidates[idx].mask, |p| {
                    if p < cells {
                        cnt[p] -= 1;
                    }
                });
            }
        }
        if !changed {
            break;
        }
    }

    let mut out = Vec::new();
    for (t, &idx) in selected.iter().enumerate() {
        if active[t] {
            out.push(idx);
        }
    }
    out
}

fn main() {
    let mut sc = Scanner::new();

    let n: usize = sc.next();
    let _ak: i64 = sc.next();
    let _am: i64 = sc.next();
    let _aw: i64 = sc.next();

    let mut v = vec![vec![0_u8; n - 1]; n];
    for row in &mut v {
        let s: String = sc.next();
        for (j, &b) in s.as_bytes().iter().enumerate() {
            row[j] = (b == b'1') as u8;
        }
    }
    let mut h = vec![vec![0_u8; n]; n - 1];
    for row in &mut h {
        let s: String = sc.next();
        for (j, &b) in s.as_bytes().iter().enumerate() {
            row[j] = (b == b'1') as u8;
        }
    }

    let cells = n * n;
    let words = (cells + 63) >> 6;

    let mut seed_base = 0x1234_5678_9abc_def0_u64 ^ (n as u64);
    for row in &v {
        for &x in row {
            seed_base = splitmix64(seed_base ^ (x as u64 + 1));
        }
    }
    for row in &h {
        for &x in row {
            seed_base = splitmix64(seed_base ^ (x as u64 + 3));
        }
    }

    let mut candidates = generate_one_state_candidates(n, &v, &h, words);
    let row_candidates = generate_row_segment_candidates(n, &v, words);
    let col_candidates = generate_col_segment_candidates(n, &h, words);
    let two_state_candidates = generate_two_state_candidates(n, &v, &h, words);
    let c3 = env_usize("C3_AUT", 768);
    let p3 = env_usize("C3_PICK", 12);
    let c4 = env_usize("C4_AUT", 512);
    let p4 = env_usize("C4_PICK", 10);
    let c5 = env_usize("C5_AUT", 256);
    let p5 = env_usize("C5_PICK", 8);
    let c6 = env_usize("C6_AUT", 512);
    let p6 = env_usize("C6_PICK", 8);
    let c7 = env_usize("C7_AUT", 256);
    let p7 = env_usize("C7_PICK", 6);
    let c8 = env_usize("C8_AUT", 96);
    let p8 = env_usize("C8_PICK", 5);
    let c9 = env_usize("C9_AUT", 192);
    let p9 = env_usize("C9_PICK", 5);
    let c12 = env_usize("C12_AUT", 96);
    let p12 = env_usize("C12_PICK", 4);
    let c15 = env_usize("C15_AUT", 64);
    let p15 = env_usize("C15_PICK", 3);
    let three_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 3, c3, p3, seed_base ^ 0x1357_9bdf);
    let four_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 4, c4, p4, seed_base ^ 0x2468_ace0);
    let five_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 5, c5, p5, seed_base ^ 0x3141_5926);
    let six_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 6, c6, p6, seed_base ^ 0x2718_2818);
    let seven_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 7, c7, p7, seed_base ^ 0x1618_0339);
    let eight_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 8, c8, p8, seed_base ^ 0x5772_1566);
    let nine_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 9, c9, p9, seed_base ^ 0x1414_2135);
    let twelve_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 12, c12, p12, seed_base ^ 0x1234_4321);
    let fifteen_state_candidates =
        generate_random_m_state_candidates(n, &v, &h, words, 15, c15, p15, seed_base ^ 0x0f0f_a5a5);
    candidates.extend(row_candidates.clone());
    candidates.extend(col_candidates.clone());
    candidates.extend(two_state_candidates);
    candidates.extend(three_state_candidates);
    candidates.extend(four_state_candidates);
    candidates.extend(five_state_candidates);
    candidates.extend(six_state_candidates);
    candidates.extend(seven_state_candidates);
    candidates.extend(eight_state_candidates);
    candidates.extend(nine_state_candidates);
    candidates.extend(twelve_state_candidates);
    candidates.extend(fifteen_state_candidates);
    candidates = dedup_candidates(candidates);
    let cand_cells = build_candidate_cells(&candidates, cells);

    let mut best_selected = solve_weighted_cover(&candidates, cells, seed_base);
    let starts = env_usize("START_TRIALS", 20).max(1);
    let drop_passes = env_usize("DROP_PASSES", 4).max(1);
    best_selected = improve_by_add_remove(&candidates, &cand_cells, best_selected, cells);
    let mut best_m: usize = best_selected.iter().map(|&idx| candidates[idx].cost).sum();
    for t in 1_u64..(starts as u64) {
        let selected = solve_weighted_cover(&candidates, cells, seed_base ^ splitmix64(t));
        let selected = improve_by_add_remove(&candidates, &cand_cells, selected, cells);
        let m: usize = selected.iter().map(|&idx| candidates[idx].cost).sum();
        if m < best_m {
            best_m = m;
            best_selected = selected;
        }
    }
    best_selected = improve_by_drop_repair(
        &candidates,
        &cand_cells,
        best_selected,
        cells,
        seed_base,
        drop_passes,
    );

    let mut robots: Vec<RobotPlan> = best_selected
        .iter()
        .map(|&idx| candidates[idx].robot.clone())
        .collect();
    let mut m_sum: usize = robots.iter().map(RobotPlan::m).sum();

    let mut row_baseline: Vec<RobotPlan> = row_candidates.iter().map(|c| c.robot.clone()).collect();
    let mut col_baseline: Vec<RobotPlan> = col_candidates.iter().map(|c| c.robot.clone()).collect();
    let row_m: usize = row_baseline.iter().map(RobotPlan::m).sum();
    let col_m: usize = col_baseline.iter().map(RobotPlan::m).sum();
    let baseline = if row_m <= col_m {
        (&mut row_baseline, row_m)
    } else {
        (&mut col_baseline, col_m)
    };

    if m_sum > baseline.1 {
        robots = baseline.0.clone();
        m_sum = baseline.1;
    }

    if robots.is_empty() {
        robots.push(RobotPlan {
            i: 0,
            j: 0,
            d: 'U',
            trans: vec![('R', 0, 'R', 0)],
        });
        m_sum = 1;
    }

    let _ = m_sum;
    println!("{}", robots.len());
    for rb in &robots {
        println!("{} {} {} {}", rb.m(), rb.i, rb.j, rb.d);
        for &(a0, b0, a1, b1) in &rb.trans {
            println!("{} {} {} {}", a0, b0, a1, b1);
        }
    }

    let z1 = "0".repeat(n.saturating_sub(1));
    for _ in 0..n {
        println!("{}", z1);
    }
    let z2 = "0".repeat(n);
    for _ in 0..n.saturating_sub(1) {
        println!("{}", z2);
    }
}

提出情報

ジャッジ結果