提出 #27962539

---

ソースコード 拡げる

use grid::Coordinate;
#[allow(unused_imports)]
use proconio::*;
#[allow(unused_imports)]
use rand::prelude::*;
use std::{collections::VecDeque, time::Instant};

#[allow(unused_macros)]
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

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

const N: usize = 20;
const MAX_TURN: usize = 5000;
const INIT_TURN: usize = 4000;
const U: usize = 0;
const R: usize = 1;
const D: usize = 2;
const L: usize = 3;

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    start: Coordinate,
    graph: Vec<Vec<[Option<Coordinate>; 4]>>,
    since: Instant,
}

impl Input {
    fn new(start: Coordinate, graph: Vec<Vec<[Option<Coordinate>; 4]>>) -> Self {
        let since = Instant::now();
        Self {
            n: N,
            start,
            graph,
            since,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Command {
    L,
    R,
    l,
    r,
    F,
}

impl ToString for Command {
    fn to_string(&self) -> String {
        match self {
            Command::L => String::from("L"),
            Command::R => String::from("R"),
            Command::l => String::from("l"),
            Command::r => String::from("r"),
            Command::F => String::from("F"),
        }
    }
}

enum Operation {
    Single(usize, Command),
    Multiple(usize, Vec<Operation>),
}

impl Operation {
    fn Apply(
        &self,
        input: &Input,
        mut coordinate: Coordinate,
        mut direction: usize,
        mut cleaned: Vec<Vec<bool>>,
        mut turn: usize,
    ) -> (Coordinate, usize, Vec<Vec<bool>>, usize) {
        match self {
            Operation::Single(rep, command) => {
                for _ in 0..*rep {
                    if turn >= MAX_TURN {
                        break;
                    }

                    let edges = &input.graph[coordinate.row][coordinate.col];

                    match command {
                        Command::L => direction = direction.wrapping_sub(1) % 4,
                        Command::R => direction = (direction + 1) % 4,
                        Command::l => {
                            if edges[direction] == None {
                                direction = direction.wrapping_sub(1) % 4;
                            }
                        }
                        Command::r => {
                            if edges[direction] == None {
                                direction = (direction + 1) % 4;
                            }
                        }
                        Command::F => {
                            if let Some(next) = edges[direction] {
                                coordinate = next;
                                cleaned[next.row][next.col] = true;
                            }
                        }
                    }

                    turn += 1;
                }
            }
            Operation::Multiple(rep, operation) => {
                for _ in 0..*rep {
                    if turn >= MAX_TURN {
                        break;
                    }

                    for op in operation.iter() {
                        if turn >= MAX_TURN {
                            break;
                        }

                        let (c, d, cl, t) = op.Apply(input, coordinate, direction, cleaned, turn);
                        coordinate = c;
                        direction = d;
                        cleaned = cl;
                        turn = t;
                    }
                }
            }
        }

        (coordinate, direction, cleaned, turn)
    }
}

impl ToString for Operation {
    fn to_string(&self) -> String {
        match self {
            Operation::Single(rep, command) => {
                let mut str = String::new();

                if *rep > 1 {
                    for c in rep.to_string().chars() {
                        str.push(c);
                    }
                }

                for c in command.to_string().chars() {
                    str.push(c);
                }

                str
            }
            Operation::Multiple(rep, operation) => {
                let mut str = String::new();

                if *rep > 1 {
                    for c in rep.to_string().chars() {
                        str.push(c);
                    }

                    str.push('(');
                }

                for op in operation.iter() {
                    for c in op.to_string().chars() {
                        str.push(c);
                    }
                }

                if *rep > 1 {
                    str.push(')');
                }

                str
            }
        }
    }
}

fn main() {
    let input = read_input();
    let operation = solve(&input);
    println!("{}", operation.to_string());
    eprintln!("{}", calc_score(&input, &operation));
}

fn read_input() -> Input {
    input! {
        s_row: usize,
        s_col: usize,
    }

    let start = Coordinate::new(s_row, s_col);

    let mut graph = mat![[None; 4]; N; N];

    for row in 0..N {
        input! {
            s: String
        }

        for (col, c) in s.chars().enumerate() {
            if c == '0' {
                graph[row][col][R] = Some(Coordinate::new(row, col + 1));
                graph[row][col + 1][L] = Some(Coordinate::new(row, col));
            }
        }
    }

    for row in 0..(N - 1) {
        input! {
            s: String
        }

        for (col, c) in s.chars().enumerate() {
            if c == '0' {
                graph[row][col][D] = Some(Coordinate::new(row + 1, col));
                graph[row + 1][col][U] = Some(Coordinate::new(row, col));
            }
        }
    }

    let input = Input::new(start, graph);
    input
}

fn solve(input: &Input) -> Operation {
    let init_operation = get_best_init_operation(input);
    let (init_coordinate, init_direction, cleaned) = generate_init_state(input);
    let (init_coordinate, init_direction, cleaned, _) =
        init_operation.Apply(input, init_coordinate, init_direction, cleaned, 0);

    let distances = calc_dists(input);
    let unvisited = get_unvisited(&cleaned);

    if unvisited.len() == 0 {
        return init_operation;
    }

    let tsp_perm = tsp(init_coordinate, init_direction, &unvisited, &distances);
    let after_operation = get_operation(
        input,
        init_coordinate,
        init_direction,
        0,
        &unvisited,
        &tsp_perm,
    );

    Operation::Multiple(1, vec![init_operation, after_operation])
}

fn get_best_init_operation(input: &Input) -> Operation {
    let mut best_score = 0;
    let mut best_operation = Operation::Single(1, Command::F);

    for operation in generate_init_candidates() {
        let (coordinate, direction, cleaned) = generate_init_state(input);
        let (_, _, cleaned, _) =
            operation.Apply(input, coordinate, direction, cleaned, 0);
        let score = calc_score(input, &operation);

        if chmax!(best_score, score) {
            best_operation = operation;
        }
    }

    best_operation
}

fn generate_init_state(input: &Input) -> (Coordinate, usize, Vec<Vec<bool>>) {
    let coordinate = input.start;
    let direction = U;
    let mut cleaned = mat![false; N; N];
    cleaned[coordinate.row][coordinate.col] = true;
    (coordinate, direction, cleaned)
}

fn generate_init_candidates() -> Vec<Operation> {
    let mut candidates = vec![];

    for left in 1..15 {
        for right in 1..15 {
            let rep = INIT_TURN / (4 * (left + right));
            let operation = Operation::Multiple(
                rep,
                vec![
                    Operation::Multiple(
                        left,
                        vec![
                            Operation::Single(1, Command::L),
                            Operation::Single(1, Command::r),
                            Operation::Single(1, Command::r),
                            Operation::Single(1, Command::F),
                        ],
                    ),
                    Operation::Multiple(
                        right,
                        vec![
                            Operation::Single(1, Command::R),
                            Operation::Single(1, Command::l),
                            Operation::Single(1, Command::l),
                            Operation::Single(1, Command::F),
                        ],
                    ),
                ],
            );
            candidates.push(operation);
        }
    }

    candidates
}

fn calc_dists(input: &Input) -> Vec<Vec<i32>> {
    // TODO: 関係あるやつだけに絞る？現状133msくらい
    const LENGTH: usize = N * N * 4 * 3;
    let mut distances = mat![0; LENGTH; LENGTH];

    for row in 0..N {
        for col in 0..N {
            let coordinate = Coordinate::new(row, col);
            for dir in 0..4 {
                for flag in 0..3 {
                    let index = to_index(row, col, dir, flag);
                    let distances = &mut distances[index];
                    let dists = calc_dist(input, coordinate, dir, flag);

                    let mut index = 0;

                    for row in 0..N {
                        for col in 0..N {
                            for dir in 0..4 {
                                for flag in 0..3 {
                                    distances[index] = dists[row][col][dir][flag];
                                    index += 1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    distances
}

fn calc_dist(
    input: &Input,
    start_coordinate: Coordinate,
    start_direction: usize,
    flag: usize,
) -> Vec<Vec<[[i32; 3]; 4]>> {
    let mut distances = mat![[[100000000; 3]; 4]; N; N];
    let mut queue = VecDeque::new();
    distances[start_coordinate.row][start_coordinate.col][start_direction][flag] = 0;
    queue.push_back((
        start_coordinate.row,
        start_coordinate.col,
        start_direction,
        flag,
    ));

    while let Some((row, col, dir, flag)) = queue.pop_front() {
        let dist = distances[row][col][dir][flag];

        // Forward
        if let Some(next) = input.graph[row][col][dir] {
            // 9 -> 10の時は考慮できないけどええやろ
            if flag == 2 {
                if chmin!(distances[next.row][next.col][dir][flag], dist) {
                    queue.push_front((next.row, next.col, dir, flag));
                }
            } else if flag < 2 {
                if chmin!(distances[next.row][next.col][dir][flag + 1], dist + 1) {
                    queue.push_back((next.row, next.col, dir, flag + 1));
                }
            }
        }

        // Left
        let next_dir = dir.wrapping_sub(1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }

        // Right
        let next_dir = (dir + 1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            queue.push_back((row, col, next_dir, 0));
        }
    }

    distances
}

fn get_unvisited(cleaned: &[Vec<bool>]) -> Vec<Coordinate> {
    let mut unvisited = vec![];

    for row in 0..N {
        for col in 0..N {
            if !cleaned[row][col] {
                unvisited.push(Coordinate::new(row, col));
            }
        }
    }

    unvisited
}

fn tsp(
    mut coordinate: Coordinate,
    mut direction: usize,
    to_visits: &[Coordinate],
    distances: &[Vec<i32>],
) -> Vec<(usize, usize, usize)> {
    let mut visited = vec![false; to_visits.len()];
    let mut flag = 0;
    let mut results = Vec::with_capacity(to_visits.len());

    // とりあえずNearest Neighbor
    for _ in 0..visited.len() {
        let dists = &distances[to_index(coordinate.row, coordinate.col, direction, flag)];
        let mut best_dist = std::i32::MAX;
        let mut best_index = 0;
        let mut best_dir = 0;
        let mut best_flag = 0;

        for (i, next) in to_visits.iter().enumerate() {
            if visited[i] {
                continue;
            }

            for dir in 0..4 {
                for fl in 0..3 {
                    let d = dists[to_index(next.row, next.col, dir, fl)];

                    if chmin!(best_dist, d) {
                        best_index = i;
                        best_dir = dir;
                        best_flag = fl;
                    } else if best_dist == d && chmax!(best_flag, fl) {
                        best_index = i;
                        best_dir = dir;
                    }
                }
            }
        }

        eprintln!(
            "({}, {}) -> ({}, {}) : {}",
            coordinate.row,
            coordinate.col,
            to_visits[best_index].row,
            to_visits[best_index].col,
            best_dist
        );

        results.push((best_index, best_dir, best_flag));
        coordinate = to_visits[best_index];
        direction = best_dir;
        flag = best_flag;
        visited[best_index] = true;
    }

    results
}

fn get_operation(
    input: &Input,
    mut coordinate: Coordinate,
    mut dir: usize,
    mut flag: usize,
    unvisited: &[Coordinate],
    tsp: &[(usize, usize, usize)],
) -> Operation {
    let mut commands = vec![];

    for &(i, next_dir, next_flag) in tsp.iter() {
        let next_coordinate = unvisited[i];
        let next_commands = get_command(
            input,
            coordinate,
            dir,
            flag,
            next_coordinate,
            next_dir,
            next_flag,
        );

        for cmd in next_commands {
            commands.push(cmd);
        }

        coordinate = next_coordinate;
        dir = next_dir;
        flag = next_flag;
    }

    compress_commands(&commands)
}

fn get_command(
    input: &Input,
    start_coordinate: Coordinate,
    start_dir: usize,
    start_flag: usize,
    goal_coordinate: Coordinate,
    goal_dir: usize,
    goal_flag: usize,
) -> Vec<Command> {
    let mut distances = mat![[[100000000; 3]; 4]; N; N];
    let mut from = mat![[[(Coordinate::new(0, 0), 0, 0, Command::F); 3]; 4]; N; N];
    let mut queue = VecDeque::new();
    distances[start_coordinate.row][start_coordinate.col][start_dir][start_flag] = 0;
    queue.push_back((
        start_coordinate.row,
        start_coordinate.col,
        start_dir,
        start_flag,
    ));

    while let Some((row, col, dir, flag)) = queue.pop_front() {
        let dist = distances[row][col][dir][flag];
        let current = Coordinate::new(row, col);

        // Forward
        if let Some(next) = input.graph[row][col][dir] {
            // 9 -> 10の時は考慮できないけどええやろ
            if flag == 2 {
                if chmin!(distances[next.row][next.col][dir][flag], dist) {
                    from[next.row][next.col][dir][flag] = (current, dir, flag, Command::F);
                    queue.push_front((next.row, next.col, dir, flag));
                }
            } else if flag < 2 {
                if chmin!(distances[next.row][next.col][dir][flag + 1], dist + 1) {
                    from[next.row][next.col][dir][flag + 1] = (current, dir, flag, Command::F);
                    queue.push_back((next.row, next.col, dir, flag + 1));
                }
            }
        }

        // Left
        let next_dir = dir.wrapping_sub(1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            from[row][col][next_dir][0] = (current, dir, flag, Command::L);
            queue.push_back((row, col, next_dir, 0));
        }

        // Right
        let next_dir = (dir + 1) % 4;
        if chmin!(distances[row][col][next_dir][0], dist + 1) {
            from[row][col][next_dir][0] = (current, dir, flag, Command::R);
            queue.push_back((row, col, next_dir, 0));
        }
    }

    let mut current = goal_coordinate;
    let mut dir = goal_dir;
    let mut flag = goal_flag;

    let mut commands = Vec::with_capacity(distances[current.row][current.col][dir][flag]);

    while start_coordinate != current || start_dir != dir || start_flag != flag {
        let (c, d, f, com) = from[current.row][current.col][dir][flag];
        commands.push(com);
        current = c;
        dir = d;
        flag = f;
    }

    commands.reverse();
    commands
}

fn compress_commands(commands: &[Command]) -> Operation {
    // さすがに1個以上あるやろ
    let mut last_command = commands[0];
    let mut rep_count = 1;
    let mut operations = vec![];

    for &command in commands.iter().skip(1) {
        if last_command != command {
            operations.push(Operation::Single(rep_count, last_command));
            last_command = command;
            rep_count = 1;
        } else {
            rep_count += 1;
        }
    }

    operations.push(Operation::Single(rep_count, last_command));

    Operation::Multiple(1, operations)
}

fn calc_score(input: &Input, operation: &Operation) -> i32 {
    let (coordinate, direction, cleaned) = generate_init_state(input);
    let (_, _, cleaned_result, _) = operation.Apply(input, coordinate, direction, cleaned, 0);

    let cleaned_count = cleaned_result
        .iter()
        .map(|v| v.iter().filter(|&&b| b).count())
        .sum::<usize>();

    if cleaned_count < N * N {
        cleaned_count as i32
    } else {
        let len = operation.to_string().len() as f64;
        let score = (N * N) as i32 + (1e8 / (100.0 + len)).round() as i32;
        score
    }
}

fn to_index(row: usize, col: usize, dir: usize, flag: usize) -> usize {
    (((row * N + col) * 4 + dir) * 3) + flag
}

#[allow(dead_code)]
mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coordinate {
        pub row: usize,
        pub col: usize,
    }

    impl Coordinate {
        pub const fn new(row: usize, col: usize) -> Self {
            Self { row, col }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.row < size && self.col < size
        }

        pub const fn to_index(&self, size: usize) -> usize {
            self.row * size + self.col
        }
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct CoordinateDiff {
        pub dr: usize,
        pub dc: usize,
    }

    impl CoordinateDiff {
        pub const fn new(dr: usize, dc: usize) -> Self {
            Self { dr, dc }
        }

        pub const fn invert(&self) -> Self {
            Self::new(0usize.wrapping_sub(self.dr), 0usize.wrapping_sub(self.dc))
        }
    }

    impl std::ops::Add<CoordinateDiff> for Coordinate {
        type Output = Coordinate;

        fn add(self, rhs: CoordinateDiff) -> Self::Output {
            Coordinate::new(self.row.wrapping_add(rhs.dr), self.col.wrapping_add(rhs.dc))
        }
    }

    pub const ADJACENTS: [CoordinateDiff; 4] = [
        CoordinateDiff::new(!0, 0),
        CoordinateDiff::new(0, 1),
        CoordinateDiff::new(1, 0),
        CoordinateDiff::new(0, !0),
    ];
}

提出情報

コンパイルエラー

warning: variant `l` should have an upper camel case name
  --> src/main.rs:98:5
   |
98 |     l,
   |     ^ help: convert the identifier to upper camel case: `L`
   |
   = note: `#[warn(non_camel_case_types)]` on by default

warning: variant `r` should have an upper camel case name
  --> src/main.rs:99:5
   |
99 |     r,
   |     ^ help: convert the identifier to upper camel case: `R`

warning: unused variable: `cleaned`
   --> src/main.rs:311:20
    |
311 |         let (_, _, cleaned, _) =
    |                    ^^^^^^^ help: consider prefixing with an underscore: `_cleaned`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: method `Apply` should have a snake case name
   --> src/main.rs:121:8
    |
121 |     fn Apply(
    |        ^^^^^ help: convert the identifier to snake case: `apply`
    |
    = note: `#[warn(non_snake_case)]` on by default

ジャッジ結果