Submission #27966946

---

Source Code Expand

#![allow(non_snake_case, unused)]

use proconio::{*, marker::*};
use rand::prelude::*;
use itertools::*;
use std::{ops::*, collections::BinaryHeap, collections::BTreeSet};

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::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(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;
		}
		ms - STIME
	}
}

pub const DIJ: [(usize, usize); 4] = [(!0, 0), (0, 1), (1, 0), (0, !0)];

pub type Output = Vec<Command>;

#[allow(non_camel_case_types)]
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum Command {
	F,
	L,
	R,
	l,
	r,
	Pattern(usize),
	Rep(usize, Output)
}

impl std::fmt::Display for Command {
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		match self {
			Command::F => write!(f, "F")?,
			Command::L => write!(f, "L")?,
			Command::R => write!(f, "R")?,
			Command::l => write!(f, "l")?,
			Command::r => write!(f, "r")?,
			Command::Pattern(i) => {
				match *i {
					// command("RllF"), command("LrrF")
					0 => write!(f, "RllF")?,
					1 => write!(f, "FRll")?,
					2 => write!(f, "lFRl")?,
					3 => write!(f, "llFR")?,
					4 => write!(f, "LrrF")?,
					5 => write!(f, "FLrr")?,
					6 => write!(f, "rFLr")?,
					7 => write!(f, "rrFL")?,
					_ => unreachable!()
				}
			},
			Command::Rep(r, cs) => {
				write!(f, "{}", r)?;
				if cs.len() >= 2 || match cs[0] { Command::Rep(_, _) | Command::Pattern(_) => true, _ => false } {
					write!(f, "(")?;
					for c in cs.iter() {
						write!(f, "{}", c)?;
					}
					write!(f, ")")?;
				} else {
					write!(f, "{}", cs[0])?;
				}
			}
		}
		Ok(())
	}
}

const N: usize = 20;
const T: usize = 5000;

pub struct Input {
	si: usize,
	sj: usize,
	hs: Vec<Vec<bool>>,
	vs: Vec<Vec<bool>>,
	pat: Vec<Vec<Vec<Vec<(usize, usize, usize)>>>>
}

pub fn read_input() -> Input {
	input! {
		si: usize,
		sj: usize,
		hs: [Chars; N],
		vs: [Chars; N - 1],
	}
	let hs = hs.into_iter().map(|h| h.into_iter().map(|a| a == '1').collect()).collect();
	let vs = vs.into_iter().map(|v| v.into_iter().map(|a| a == '1').collect()).collect();
	let mut input = Input { si, sj, hs, vs, pat: mat![(!0, !0, !0); 8; N; N; 4] };
	let mut state = State::new(&input);
	for k in 0..8 {
		let mut p = [command("RllF"), command("LrrF")][k / 4].clone();
		for _ in 0..k % 4 {
			let c = p.pop().unwrap();
			p.insert(0, c);
		}
		for i in 0..N {
			for j in 0..N {
				for d in 0..4 {
					state.i = i;
					state.j = j;
					state.d = d;
					state.t = 0;
					state.apply(&input, &p);
					input.pat[k][i][j][d] = (state.i, state.j, state.d);
				}
			}
		}
	}
	input
}

impl Input {
	fn can_move(&self, i: usize, j: usize, d: usize) -> bool {
		match d {
			0 => i > 0 && !self.vs[i - 1][j],
			1 => j < N - 1 && !self.hs[i][j],
			2 => i < N - 1 && !self.vs[i][j],
			3 => j > 0 && !self.hs[i][j - 1],
			_ => unreachable!()
		}
	}
}

fn write_output(out: &Output) {
	let out = out.iter().join("");
	eprintln!("length = {}", out.len());
	println!("{}", out);
}

#[derive(Clone, Debug)]
struct State {
	visited: Vec<Vec<bool>>,
	num_visited: usize,
	out: Output,
	i: usize,
	j: usize,
	d: usize,
	t: usize,
}

impl State {
	fn new(input: &Input) -> Self {
		let mut visited = mat![false; N; N];
		visited[input.si][input.sj] = true;
		Self {
			visited,
			num_visited: 1,
			out: vec![],
			i: input.si,
			j: input.sj,
			d: 0,
			t: 0,
		}
	}
	fn apply(&mut self, input: &Input, out: &[Command]) {
		// solution::profile!(apply);
		for c in out.iter() {
			if self.t >= T {
				break;
			}
			match c {
				Command::L => {
					self.d = (self.d + 3) % 4;
					self.t += 1;
				},
				Command::R => {
					self.d = (self.d + 1) % 4;
					self.t += 1;
				},
				Command::F => {
					if input.can_move(self.i, self.j, self.d) {
						self.i += DIJ[self.d].0;
						self.j += DIJ[self.d].1;
						if self.visited[self.i][self.j].setmax(true) {
							self.num_visited += 1;
						}
					}
					self.t += 1;
				},
				Command::l => {
					if !input.can_move(self.i, self.j, self.d) {
						self.d = (self.d + 3) % 4;
					}
					self.t += 1;
				},
				Command::r => {
					if !input.can_move(self.i, self.j, self.d) {
						self.d = (self.d + 1) % 4;
					}
					self.t += 1;
				},
				Command::Rep(n, cs) => {
					for _ in 0..*n {
						self.apply(input, &cs);
						if self.t >= T {
							break;
						}
					}
				},
				&Command::Pattern(k) => {
					if self.t + 4 > T {
						let mut p = [command("RllF"), command("LrrF")][k / 4].clone();
						for _ in 0..k % 4 {
							let c = p.pop().unwrap();
							p.insert(0, c);
						}
						self.apply(input, &p);
					} else {
						let (i, j, d) = input.pat[k][self.i][self.j][self.d];
						self.i = i;
						self.j = j;
						self.d = d;
						if self.visited[i][j].setmax(true) {
							self.num_visited += 1;
						}
						self.t += 4;
					}
				}
			}
		}
	}
	fn mst(&self, input: &Input) -> usize {
		// solution::profile!(mst);
		let mut dist = mat![1000000; N; N];
		let mut fixed = mat![false; N; N];
		let mut que = BinaryHeap::new();
		dist[self.i][self.j] = 0;
		que.push((0, self.i, self.j));
		let mut total = 0;
		while let Some((c, i, j)) = que.pop() {
			if fixed[i][j] || dist[i][j] != -c {
				continue;
			}
			let mut cost = dist[i][j];
			if !fixed[i][j] && !self.visited[i][j] {
				fixed[i][j] = true;
				total += dist[i][j];
				cost = 0;
			}
			for d in 0..4 {
				if input.can_move(i, j, d) {
					let i2 = i + DIJ[d].0;
					let j2 = j + DIJ[d].1;
					if !fixed[i2][j2] && dist[i2][j2].setmin(cost + 1) {
						que.push((-dist[i2][j2], i2, j2));
					}
				}
			}
		}
		N * N - (total as usize).min(N * N)
	}
}

const P: f64 = 0.3;
const G: f64 = 8.0;
const B: usize = 1000;

fn eval(len: usize, t0: usize, t: usize, m0: usize, m: usize) -> f64 {
	if m > m0 {
		let gain = m - m0;
		if (t - t0) as f64 / (gain as f64) < G || m as f64 / (N * N) as f64 >= (t as f64 / T as f64).powf(P) {
			gain as f64 / len as f64 + gain as f64 / (t - t0) as f64 * 0.01
		} else {
			0.0
		}
	} else {
		0.0
	}
}

fn eval2(len: usize, t0: usize, t: usize, m0: usize, m: usize) -> f64 {
	if m > m0 {
		let gain = m - m0;
		if (t - t0) as f64 / (gain as f64) < 12.5 || m as f64 / (N * N) as f64 >= t as f64 / T as f64 {
			gain as f64 / len as f64 + gain as f64 / (t - t0) as f64 * 0.01
		} else {
			0.0
		}
	} else {
		0.0
	}
}

fn command(s: &str) -> Vec<Command> {
	s.chars().map(|c| match c {
		'R' => Command::R,
		'L' => Command::L,
		'r' => Command::r,
		'l' => Command::l,
		'F' => Command::F,
		_ => panic!()
	}).collect()
}

fn commands(ss: &[&str]) -> Vec<Vec<Command>> {
	ss.iter().map(|s| command(s)).collect()
}

fn rec(input: &Input, state: &State, out: &Vec<Command>, best: &mut Vec<(f64, Vec<Command>)>) {
	// solution::profile!(rec);
	if out.len() > 0 && out.iter().any(|c| c == &Command::F) {
		let mut new_state = state.clone();
		let mut prev = BTreeSet::new();
		for r in 1.. {
			if !prev.insert((new_state.i, new_state.j, new_state.d)) {
				break;
			}
			new_state.apply(input, out);
			let mut length = out.len();
			if r > 1 {
				length += r.to_string().len();
				if out.len() > 1 || match out[0] { Command::Rep(_, _) | Command::Pattern(_) => true, _ => false } {
					length += 2;
				}
			}
			let score = eval(length, state.t, new_state.t, state.num_visited, new_state.num_visited);
			if score > 0.0 && (best.len() < B || best.last().unwrap().0 < score) {
				let out = if r == 1 {
					out.clone()
				} else {
					vec![Command::Rep(r, out.clone())]
				};
				if best.len() < B {
					best.push((score, out));
				} else {
					let mut p = best.len() - 1;
					best[p] = (score, out);
					while p > 0 && best[p - 1].0 < score {
						best.swap(p - 1, p);
						p -= 1;
					}
				}
			}
			if new_state.t >= T {
				break;
			}
		}
	}
	if out.len() == 6 {
		return;
	}
	for c in vec![Command::L, Command::R, Command::F, Command::l, Command::r] {
		if out.len() > 0 {
			match (&out[out.len() - 1], &c) {
				(&Command::L, &Command::R) | (&Command::R, &Command::L) | (&Command::R, &Command::R) => continue,
				_ => ()
			}
		}
		let mut out = out.clone();
		out.push(c);
		rec(input, state, &out, best);
	}
}

fn rec2(input: &Input, state: &State, out: &Vec<Command>, t: usize, length: usize, best: &mut Vec<(f64, Vec<Command>)>) {
	// solution::profile!(rec2);
	for s in if length == 4 { commands(&["", "R", "L", "F", "RF", "LF", "FR", "FL"]) } else { vec![vec![]] } {
		let mut new_state = state.clone();
		let mut prev = BTreeSet::new();
		new_state.apply(input, &s);
		let length = length + s.len();
		for r in 1.. {
			if !prev.insert((new_state.i, new_state.j, new_state.d)) {
				break;
			}
			new_state.apply(input, out);
			let mut length = length;
			if r > 1 {
				length += r.to_string().len() + 2;
			}
			let score = eval(length, state.t, new_state.t, state.num_visited, new_state.num_visited);
			if score > 0.0 && (best.len() < B || best.last().unwrap().0 < score) {
				let out = if r == 1 {
					s.iter().chain(out).cloned().collect()
				} else {
					s.iter().cloned().chain(vec![Command::Rep(r, out.clone())]).collect()
				};
				if best.len() < B {
					best.push((score, out));
				} else {
					let mut p = best.len() - 1;
					best[p] = (score, out);
					while p > 0 && best[p - 1].0 < score {
						best.swap(p - 1, p);
						p -= 1;
					}
				}
			}
			if new_state.t >= T {
				break;
			}
			if r >= 2 && length < 10 {
				let t = t * r + s.len();
				for c in &[Command::L, Command::R, Command::l, Command::r, Command::F] {
					rec2(input, state, &s.iter().cloned().chain(vec![Command::Rep(r, out.clone()), c.clone()]).collect(), t + 1, length + 1, best);
					if length < 9 {
						for c2 in &[Command::L, Command::R, Command::l, Command::r, Command::F] {
							if c == &Command::L && c2 == &Command::R || c == &Command::R && c2 == &Command::L || c == &Command::R && c2 == &Command::R {
								continue;
							}
							rec2(input, state, &s.iter().cloned().chain(vec![Command::Rep(r, out.clone()), c.clone(), c2.clone()]).collect(), t + 2, length + 2, best);
						}
					}
				}
				for k in 0..8 {
					rec2(input, state, &s.iter().cloned().chain(vec![Command::Rep(r, out.clone()), Command::Pattern(k)]).collect(), t + 4, length + 4, best);
					if length < 8 {
						for r2 in 2..10 {
							rec2(input, state, &s.iter().cloned().chain(vec![Command::Rep(r, out.clone()), Command::Rep(r2, vec![Command::Pattern(k)])]).collect(), t + 4 * r2, length + 7, best);
						}
					}
				}
			}
		}
	}
}

fn rep(input: &Input, state: &State, best: &mut Vec<(f64, Vec<Command>)>) {
	// solution::profile!(rep);
	let t0 = state.t;
	let m0 = state.num_visited;
	for c in commands(&["", "R", "L", "F", "RF", "LF", "FR", "FL"]) {
		let mut state = state.clone();
		state.apply(input, &c);
		state.out.extend(c.clone());
		for s in 0..state.out.len() {
			let mut new_state = state.clone();
			let mut prev = BTreeSet::new();
			for r in 2.. {
				if !prev.insert((new_state.i, new_state.j, new_state.d)) {
					break;
				}
				new_state.apply(input, &state.out[s..]);
				let length = r.to_string().len() + 2 + c.len();
				
				let score = eval(length, state.t, new_state.t, m0, new_state.num_visited);
				if score > 0.0 && (best.len() < B || best.last().unwrap().0 < score) {
					let mut out = state.out.clone();
					let tmp = out.drain(s..).collect::<Vec<_>>();
					out.push(Command::Rep(r, tmp));
					if best.len() < B {
						best.push((score, out));
					} else {
						let mut p = best.len() - 1;
						best[p] = (score, out);
						while p > 0 && best[p - 1].0 < score {
							best.swap(p - 1, p);
							p -= 1;
						}
					}
				}
				if new_state.t >= T {
					break;
				}
			}
		}
	}
}

const INF: i32 = 1000000000;

fn dij(input: &Input, state: &mut State) {
	// solution::profile!(dij);
	let mut dist = mat![INF; N; N; 4];
	let mut prev = mat![(!0, !0, !0, Command::L); N; N; 4];
	dist[state.i][state.j][state.d] = 0;
	let mut que = BinaryHeap::new();
	que.push((0, state.i, state.j, state.d));
	while let Some((k, i, j, d)) = que.pop() {
		let k = -k;
		if k != dist[i][j][d] {
			continue;
		}
		if !state.visited[i][j] {
			let mut i = i;
			let mut j = j;
			let mut d = d;
			let mut cs = vec![];
			while (i, j, d) != (state.i, state.j, state.d) {
				let (pi, pj, pd, c) = prev[i][j][d].clone();
				cs.push(c);
				i = pi;
				j = pj;
				d = pd;
			}
			cs.reverse();
			cs = vec![cs[0].clone()];
			state.apply(input, &cs);
			state.out.extend(cs);
			return;
		}
		if dist[i][j][(d + 3) % 4].setmin(k + 1) {
			prev[i][j][(d + 3) % 4] = (i, j, d, Command::L);
			que.push((-k - 1, i, j, (d + 3) % 4));
		}
		if dist[i][j][(d + 1) % 4].setmin(k + 1) {
			prev[i][j][(d + 1) % 4] = (i, j, d, Command::R);
			que.push((-k - 1, i, j, (d + 1) % 4));
		}
		let mut i2 = i;
		let mut j2 = j;
		for n in 1.. {
			if !input.can_move(i2, j2, d) {
				break;
			}
			i2 += DIJ[d].0;
			j2 += DIJ[d].1;
			if n == 1 {
				if dist[i2][j2][d].setmin(k + 1) {
					prev[i2][j2][d] = (i, j, d, Command::F);
					que.push((-k - 1, i2, j2, d));
				}
			} else {
				let k2 = k + n.to_string().len() as i32;
				if dist[i2][j2][d].setmin(k2) {
					prev[i2][j2][d] = (i, j, d, Command::Rep(n, vec![Command::F]));
					que.push((-k2, i2, j2, d));
				}
			}
		}
	}
	panic!();
}

fn solve(input: &Input) -> Output {
	let mut state = State::new(input);
	while state.num_visited < N * N && state.t < T {
		eprintln!("{}", state.out.iter().join(""));
		eprintln!("L = {}, M = {}, M' = {}, t = {}", state.out.iter().join("").len(), state.num_visited, state.mst(input), state.t);
		for i in 0..N {
			for j in 0..N {
				if state.visited[i][j] {
					eprint!("1");
				} else {
					eprint!("0");
				}
			}
			eprintln!();
		}
		let mut best = vec![];
		rec(&input, &state, &mut vec![], &mut best);
		for k in 0..8 {
			rec2(&input, &state, &vec![Command::Pattern(k)], 4, 4, &mut best);
		}
		for b in &mut best {
			b.1 = state.out.iter().cloned().chain(b.1.clone()).collect();
		}
		rep(&input, &state, &mut best);
		let mut max = 0.0;
		let mut best_out = vec![];
		let t0 = state.t;
		let m0 = state.mst(input);
		for (_score, out) in best {
			let mut state = State::new(input);
			state.apply(input, &out);
			if max.setmax(eval2(out.iter().join("").len(), t0, state.t, m0, state.mst(input))) {
				best_out = out;
			}
		}
		if max > 0.0 {
			state = State::new(input);
			state.apply(input, &best_out);
			state.out = best_out;
		} else {
			dij(input, &mut state);
		}
		// let mut state0 = State::new(input);
		// state0.apply(input, &state.out);
		// assert_eq!(state0.num_visited, state.num_visited);
		// assert_eq!(state0.i, state.i);
		// assert_eq!(state0.j, state.j);
		// assert_eq!(state0.d, state.d);
	}
	eprintln!("L = {}, M = {}, M' = {}, t = {}", state.out.iter().join("").len(), state.num_visited, state.mst(input), state.t);
	if state.num_visited != N * N {
		println!("orz");
	}
	state.out
}

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

Submission Info

Judge Result