Submission #22785943

---

Source Code Expand

use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::fmt;
use std::io::{stdin, stdout, BufWriter, Write};

const SIZE: usize = 30;
const V: usize = SIZE * SIZE;
const E: usize = (SIZE - 1) * SIZE + SIZE * (SIZE - 1);
const QUERIES: usize = 1000;
//const COST_LO: f64 = 1000.0;
//const COST_HI: f64 = 9000.0;

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum LogLevel {
    Critical,
    Error,
    Warning,
    Info,
    Debug,
    Debug2,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos {
    r: isize,
    c: isize,
}

fn diff(p0: Pos, p1: Pos) -> (isize, isize) {
    (p1.r - p0.r, p1.c - p0.c)
}

impl Pos {
    fn to_id(&self) -> usize {
        (self.r * (SIZE as isize) + self.c) as usize
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Dir {
    Right,
    Down,
    Left,
    Up,
}

impl fmt::Display for Dir {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let s = match self {
            Dir::Right => "R",
            Dir::Down => "D",
            Dir::Left => "L",
            Dir::Up => "U",
        };
        write!(f, "{}", s)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Edge {
    src: Pos,
    dest: Pos,
}

impl Edge {
    fn to_dir(&self) -> Dir {
        let (dr, dc) = diff(self.src, self.dest);
        if dr == 0 {
            if dc == 1 {
                Dir::Right
            } else if dc == -1 {
                Dir::Left
            } else {
                panic!();
            }
        } else {
            if dc != 0 {
                panic!();
            } else {
                if dr == 1 {
                    Dir::Down
                } else if dr == -1 {
                    Dir::Up
                } else {
                    panic!();
                }
            }
        }
    }

    fn to_id_impl(p: Pos, dir: Dir) -> usize {
        (match dir {
            Dir::Right => p.r * (SIZE as isize - 1) + p.c,
            Dir::Down => p.r * (SIZE as isize) + p.c + ((SIZE * (SIZE - 1)) as isize),
            _ => panic!(),
        }) as usize
    }

    fn to_id(&self) -> usize {
        match self.to_dir() {
            Dir::Left => Self::to_id_impl(self.dest, Dir::Right),
            Dir::Up => Self::to_id_impl(self.dest, Dir::Down),
            Dir::Right => Self::to_id_impl(self.src, Dir::Right),
            Dir::Down => Self::to_id_impl(self.src, Dir::Down),
        }
    }
}

#[derive(Debug, Clone, PartialEq)]
struct Equation {
    edges: Vec<Edge>,
    cost: f64,
}

#[derive(Debug, Copy, Clone, PartialEq)]
struct EdgeWithCost {
    src: Pos,
    dest: Pos,
    cost: f64,
}

#[derive(Debug, Clone)]
struct Graph {
    edge_list: Vec<Vec<EdgeWithCost>>,
}

struct SpM {
    col_size: usize,
    row_starts: Vec<usize>,
    cols: Vec<usize>,
}

impl SpM {
    fn row_size(&self) -> usize {
        self.row_starts.len()
    }
}

fn spmv(spm: &SpM, a: &[f64], b: &mut [f64]) {
    for e in b.iter_mut() {
        *e = 0.;
    }
    for row in 0..spm.row_size() {
        let row_start = spm.row_starts[row];
        let row_end = if row < spm.row_size() - 1 {
            spm.row_starts[row + 1]
        } else {
            spm.cols.len()
        };
        for idx in row_start..row_end {
            let col = spm.cols[idx];
            b[row] += a[col];
        }
    }
}

fn spmv_trans(spm: &SpM, b: &[f64], a: &mut [f64]) {
    for e in a.iter_mut() {
        *e = 0.;
    }
    for row in 0..spm.row_size() {
        let row_start = spm.row_starts[row];
        let row_end = if row < spm.row_size() - 1 {
            spm.row_starts[row + 1]
        } else {
            spm.cols.len()
        };
        for idx in row_start..row_end {
            let col = spm.cols[idx];
            a[col] += b[row];
        }
    }
}

fn sub(x: &[f64], y: &[f64], z: &mut [f64]) {
    if x.len() != y.len() {
        panic!();
    }
    for idx in 0..x.len() {
        z[idx] = x[idx] - y[idx];
    }
}

fn scale(a: f64, x: &[f64], y: &mut [f64]) {
    for idx in 0..x.len() {
        y[idx] = a * x[idx];
    }
}

fn norm(x: &[f64]) -> f64 {
    let mut ans = 0.;
    for a in x {
        ans += a * a;
    }
    ans
}

fn clamp_vec(x: &mut [f64], min: f64, max: f64) {
    for a in x {
        *a = a.max(min).min(max);
    }
}

fn calc_default_weight(temp: f64) -> f64 {
    5000. - 1000. * temp.powf(0.15)
}

fn gradient_descent(spm: &SpM, b: &[f64], temp: f64, log_level: LogLevel) -> Vec<f64> {
    let default_weight = calc_default_weight(temp);
    let mut a = vec![default_weight; spm.col_size];
    let mut ta = vec![0.; spm.col_size];
    let mut c = vec![0.; spm.row_size()];
    let mut d = vec![0.; spm.row_size()];
    let mut sd = vec![0.; spm.row_size()];
    let alpha = 0.0001;
    for _i in 0..30 {
        spmv(spm, &a, &mut c);
        sub(&b, &c, &mut d);
        if log_level >= LogLevel::Debug {
            eprintln!("GD Diff: {}", norm(&d));
        }
        scale(alpha, &d, &mut sd);
        spmv_trans(spm, &sd, &mut ta);
        for idx in 0..spm.col_size {
            a[idx] += ta[idx];
        }
    }
    a
}

fn estimate_cost(eqs: &[Equation], temp: f64, log_level: LogLevel) -> Graph {
    let mut cols = Vec::new();
    let mut row_starts = Vec::new();
    let mut b = Vec::new();
    for eq in eqs {
        b.push(eq.cost);
        row_starts.push(cols.len());
        for e in &eq.edges {
            cols.push(e.to_id());
        }
    }
    let spm = SpM {
        col_size: E,
        row_starts,
        cols,
    };
    let mut a = gradient_descent(&spm, &b, temp, log_level);
    clamp_vec(&mut a, 1000.0, 9000.0);
    let mut edge_list = Vec::with_capacity(V);
    for row in 0..SIZE as isize {
        for col in 0..SIZE as isize {
            let v0 = Pos { r: row, c: col };
            let mut edges = Vec::with_capacity(4);
            let d = [0, 1, 0, -1, 0];
            for k in 0..4 {
                let nr = row + d[k];
                let nc = col + d[k + 1];
                if nr < 0 || nc < 0 || nr >= SIZE as isize || nc >= SIZE as isize {
                    continue;
                }
                let v1 = Pos { r: nr, c: nc };
                edges.push(EdgeWithCost {
                    src: v0,
                    dest: v1,
                    cost: a[Edge { src: v0, dest: v1 }.to_id()],
                });
            }
            edge_list.push(edges);
        }
    }
    Graph { edge_list }
}

#[derive(Debug, Copy, Clone, PartialEq)]
struct State {
    cost: f64,
    pos: Pos,
}

impl Eq for State {}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.cost.partial_cmp(&self.cost)
    }
}

fn dijkstra(s: Pos, t: Pos, g: &Graph) -> Vec<EdgeWithCost> {
    let mut dist: Vec<_> = (0..V).map(|_| 1e18).collect();
    let mut parent: Vec<Option<EdgeWithCost>> = (0..V).map(|_| None).collect();
    let mut heap = BinaryHeap::new();
    dist[s.to_id()] = 0.;
    heap.push(State { cost: 0., pos: s });
    while let Some(State { cost, pos }) = heap.pop() {
        if pos == t {
            break;
        }
        let i = pos.to_id();
        if cost > dist[i] {
            continue;
        }
        for e in &g.edge_list[i] {
            let next = State {
                cost: cost + e.cost,
                pos: e.dest,
            };
            let j = next.pos.to_id();
            if next.cost < dist[j] {
                dist[j] = next.cost;
                parent[j] = Some(*e);
                heap.push(next);
            }
        }
    }
    let mut edges = Vec::new();
    let mut pos = t;
    while let Some(e) = parent[pos.to_id()] {
        edges.push(e);
        pos = e.src;
    }
    edges.reverse();
    edges
}

fn solve(s: Pos, t: Pos, eqs: &[Equation], temp: f64, log_level: LogLevel) -> Vec<Edge> {
    let g = estimate_cost(eqs, temp, log_level);
    let edges = dijkstra(s, t, &g);
    edges
        .iter()
        .map(|e| Edge {
            src: e.src,
            dest: e.dest,
        })
        .collect()
}

fn respond(edges: &[Edge]) -> f64 {
    let out = stdout();
    {
        let mut out = BufWriter::new(out.lock());
        for e in edges {
            write!(out, "{}", e.to_dir()).unwrap();
        }
        writeln!(out, "").unwrap();
    }
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace().next().unwrap().parse().unwrap()
}

fn get_query() -> (Pos, Pos) {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let mut nums = buf.split_whitespace();
    let rs: isize = nums.next().unwrap().parse().unwrap();
    let cs: isize = nums.next().unwrap().parse().unwrap();
    let rt: isize = nums.next().unwrap().parse().unwrap();
    let ct: isize = nums.next().unwrap().parse().unwrap();
    let s = Pos { r: rs, c: cs };
    let t = Pos { r: rt, c: ct };
    (s, t)
}

fn main() {
    let args: Vec<String> = std::env::args().collect();
    let log_level = match args.iter().nth(1) {
        Some(s) => {
            if s == "-v" {
                LogLevel::Info
            } else if s == "-d" {
                LogLevel::Debug
            } else if s == "-D" {
                LogLevel::Debug2
            } else if s == "-w" {
                LogLevel::Warning
            } else if s == "-q" {
                LogLevel::Critical
            } else {
                panic!()
            }
        }
        None => LogLevel::Error,
    };
    let mut eqs = Vec::new();
    for i in 0..QUERIES {
        let temp = 0.998f64.powi(i as i32 - 1000);
        if log_level >= LogLevel::Info {
            eprintln!("Query {}, temp: {}", i, temp);
        }
        let (s, t) = get_query();
        let path = solve(s, t, &eqs, temp, log_level);
        let cost = respond(&path);
        eqs.push(Equation { edges: path, cost });
    }
}

Submission Info

Judge Result