#863243 (Rust) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: r3yohei
• 提出日時: 2023-04-27 11:08:59
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 2 ms / 1,000 ms
• コード長: 15,291 bytes
• コンパイル時間: 2,128 ms
• コンパイル使用メモリ: 163,124 KB
• 実行使用メモリ: 4,376 KB
• スコア: 6,669,031
• 最終ジャッジ日時: 2023-04-27 11:09:07
• 合計ジャッジ時間: 3,941 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

ファイルパターン	結果
other	AC * 30

ソースコード

#![allow(non_snake_case, unused)]

use std::io::*;
use std::{collections::*, fmt::format};
use std::{cmp::*, vec};
use crate::input::{*, marker::*};
use self::i64::kmeans;

// コピペで使える proconio もどき
// cunitacさんからお借りしています
// https://gist.github.com/cunitac/b00be62bf68c9fb6055d22eb77c17e14
pub mod input {
    use std::{
        cell::RefCell,
        fmt::Debug,
        io::{stdin, BufRead, BufReader, Stdin},
        str::{FromStr, SplitWhitespace},
    };

    thread_local!(
        pub static STDIN_SOURCE: RefCell<Source> = RefCell::new(Source {
            stdin: BufReader::new(stdin()),
            tokens: "".split_whitespace(),
        });
    );

    pub struct Source {
        stdin: BufReader<Stdin>,
        tokens: SplitWhitespace<'static>,
    }
    impl Source {
        pub fn next_token(&mut self) -> Option<&str> {
            self.tokens.next().or_else(|| {
                let mut input = String::new();
                self.stdin.read_line(&mut input).unwrap();
                self.tokens = Box::leak(input.into_boxed_str()).split_whitespace();
                self.tokens.next()
            })
        }
    }
    #[macro_export]
    macro_rules! read_value {
        (from $s:expr, [$t:tt; $n:expr]) => {
            (0..$n).map(|_| $crate::read_value!(from $s, $t)).collect::<Vec<_>>()
        };
        (from $s:expr, [$t:tt]) => {
            let n = $crate::read_value!(from $s, usize);
            $crate::read_value!(from $s, [$t; n])
        };
        (from $s:expr, $t:ty) => {
            <$t as $crate::input::Readable>::read(&mut $s)
        };
        (from $s:expr, $($t:tt),* $(,)?) => {
            ($($crate::read_value!(from $s, $t)),*)
        };
        ($($r:tt)*) => {
            $crate::input::STDIN_SOURCE.with(|s| {
                let mut s = s.borrow_mut();
                $crate::read_value!(from s, $($r)*)
            })
        }
    }
    #[macro_export]
    macro_rules! input {
        () => {
        };
        ($x:tt: $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (mut $x:tt: $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!($t);
            $crate::input!($($r)*);
        };
        (from $s:expr, $x:tt, $t:tt, $($r:tt)*) => {
            let $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        (from $s:expr, mut $x:tt, $t:tt, $($r:tt)*) => {
            let mut $x = $crate::read_value!(from $s, $t);
            $crate::input!(from $s, $($r)*);
        };
        ($($r:tt)*) => {
            $crate::input!($($r)*,);
        };
    }
    pub trait Readable {
        type Output;
        fn read(source: &mut Source) -> Self::Output;
    }
    impl<T: FromStr<Err = E>, E: Debug> Readable for T {
        type Output = T;
        fn read(source: &mut Source) -> T {
            source.next_token().unwrap().parse().unwrap()
        }
    }
    pub mod marker {
        macro_rules! impl_readable {
            ($e:ident, $t:ty, $u:ty, $f:expr) => {
                pub enum $e {}
                impl $crate::input::Readable for $e {
                    type Output = $t;
                    fn read(mut source: &mut $crate::input::Source) -> $t {
                        $f($crate::read_value!(from source, $u))
                    }
                }
            };
        }
        impl_readable!(Usize1, usize, usize, |x| x - 1);
        impl_readable!(Isize1, isize, isize, |x| x - 1);
        impl_readable!(Chars, Vec<char>, String, |x: String| x.chars().collect());
        impl_readable!(Bytes, Vec<u8>, String, |x: String| x.bytes().collect());
    }
}

macro_rules! impl_kmeans {
    ($kind: ty, $modname: ident) => {
        // Since we can't overload methods in rust, we have to use namespacing
        pub mod $modname {
            use std::$modname::MAX;

            /// computes sum of squared deviation between two identically sized vectors
            /// `x`, and `y`.
            fn distance(x: &[$kind], y: &[$kind]) -> $kind {
                x.iter()
                    .zip(y.iter())
                    .fold(0, |dist, (&xi, &yi)| dist + (xi - yi) * (xi - yi))
            }

            /// Returns a vector containing the indices z<sub>i</sub> in {0, ..., K-1} of
            /// the centroid nearest to each datum.
            fn nearest_centroids(xs: &[Vec<$kind>], centroids: &[Vec<$kind>]) -> Vec<usize> {
                xs.iter()
                    .map(|xi| {
                        // Find the argmin by folding using a tuple containing the argmin
                        // and the minimum distance.
                        let (argmin, _) = centroids.iter().enumerate().fold(
                            (0_usize, MAX),
                            |(min_ix, min_dist), (ix, ci)| {
                                let dist = distance(xi, ci);
                                if dist < min_dist {
                                    (ix, dist)
                                } else {
                                    (min_ix, min_dist)
                                }
                            },
                        );
                        argmin
                    })
                    .collect()
            }

            /// Recompute the centroids given the current clustering
            fn recompute_centroids(
                xs: &[Vec<$kind>],
                clustering: &[usize],
                k: usize,
            ) -> Vec<Vec<$kind>> {
                let ndims = xs[0].len();

                // NOTE: Kind of inefficient because we sweep all the data from each of the
                // k centroids.
                (0..k)
                    .map(|cluster_ix| {
                        let mut centroid: Vec<$kind> = vec![0; ndims];
                        let mut n_cluster: $kind = 0;
                        xs.iter().zip(clustering.iter()).for_each(|(xi, &zi)| {
                            if zi == cluster_ix {
                                n_cluster += 1;
                                xi.iter().enumerate().for_each(|(j, &x_ij)| {
                                    centroid[j] += x_ij;
                                });
                            }
                        });
                        centroid.iter().map(|&c_j| c_j / n_cluster).collect()
                    })
                    .collect()
            }

            /// Assign the N D-dimensional data, `xs`, to `k` clusters using K-Means clustering
            pub fn kmeans(xs: Vec<Vec<$kind>>, k: usize) -> (Vec<usize>, Vec<Vec<$kind>>) {
                assert!(xs.len() >= k);

                // Rather than pulling in a dependency to radomly select the staring
                // points for the centroids, we're going to deterministally choose them by
                // slecting evenly spaced points in `xs`
                let n_per_cluster: usize = xs.len() / k;
                let centroids: Vec<Vec<$kind>> =
                    (0..k).map(|j| xs[j * n_per_cluster].clone()).collect();

                let mut clustering = nearest_centroids(&xs, &centroids);

                loop {
                    let centroids = recompute_centroids(&xs, &clustering, k);
                    let new_clustering = nearest_centroids(&xs, &centroids);

                    // loop until the clustering doesn't change after the new centroids are computed
                    if new_clustering
                        .iter()
                        .zip(clustering.iter())
                        .all(|(&za, &zb)| za == zb)
                    {
                        // We need to use `return` to break out of the `loop`
                        return (clustering, centroids);
                    } else {
                        clustering = new_clustering;
                    }
                }
            }
        }
    };
}
impl_kmeans!(i64, i64);

const N: usize = 100;
const M: usize = 8;
const ALPHA: i64 = 5;
const INF: i64 = 1_000_000_000;
const TL: f64 = 0.97;

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;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.5
        }
        #[cfg(not(feature = "local"))]
        {
            (ms - STIME)
        }
    }
}

// 距離の二乗を返す
pub fn squared_distance(x1: i64, y1: i64, type_1: usize, x2: i64, y2: i64, type_2: usize) -> i64 {
    if type_1 == 1 && type_2 == 1 {
        ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * ALPHA * ALPHA
    } else if type_1 == 1 || type_2 == 1 {
        ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) * ALPHA
    } else {
        ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
    }
}

#[derive(Clone)]
pub struct Input {
    pos: Vec<Vec<i64>>,
}
impl Input {
    fn new() -> Self {
        input! {
            _n: usize,
            _m: usize,
        }
        let mut pos = vec![];
        for _ in 0..N {
            input! {
                ai: i64,
                bi: i64,
            }
            pos.push(vec![ai, bi]);
        }
        Self { pos }
    }
}

// 初期解を貪欲法で作る
pub fn init_route_greedy(input: &Input) -> Vec<(usize, usize)> {
    let mut route = vec![(1, 0)];
    let mut visited = vec![false; N];
    visited[0] = true;
    while route.len() < N {
        let &(crt_t, crt_r) = route.last().unwrap();
        let mut min_dist = INF;
        let mut min_index = !0;
        for i in 1..N {
            if crt_r == i || visited[i] {continue;}
            let crt_pos = &input.pos[crt_r];
            let next_pos = &input.pos[i];
            let dist = squared_distance(crt_pos[0], crt_pos[1], crt_t, next_pos[0], next_pos[1], 1);
            if dist < min_dist {
                min_dist = dist;
                min_index = i;
            }
        }
        route.push((1, min_index));
        visited[min_index] = true;
    }
    route.push((1, 0));
    route
}

// 初期解をkmeansのクラスタ分けを参考にして作る
pub fn init_route_kmeans(input: &Input, cluster: &Vec<usize>, station: &Vec<Vec<i64>>) -> Vec<(usize, usize)> {
    // 惑星1から惑星1が属するステーションに行く
    let mut route = vec![(1, 0)];
    route.push((2, cluster[0]));
    let mut visited = vec![false; N];
    visited[0] = true;
    let mut visited_cluster = vec![false; M];
    visited_cluster[cluster[0]] = true;
    loop {
        // 惑星1は例えばcluster[0]に属する
        // cluster[0]に属する惑星のうち，station[cluster[0]]との距離が一定以下のものはスターグラフとしてつなぐ
        let &(crt_t, crt_r) = route.last().unwrap();
        let crt_cluster = if crt_t == 1 {
            cluster[crt_r]
        } else {
            crt_r
        };
        let crt_station = &station[crt_cluster];
        let mut min_dist = INF;
        let mut min_index = !0;
        let mut is_updated = false;
        for i in 1..N {
            // 現在見ているクラスタに属する惑星のうちで，距離が一定以下のものをつなぐ
            if visited[i] || cluster[i] != crt_cluster {continue;}
            let crt_pos = if crt_t == 1 {
                &input.pos[crt_r]
            } else {
                &station[crt_cluster]
            };
            let next_pos = &input.pos[i];
            let dist = squared_distance(crt_pos[0], crt_pos[1], crt_t, next_pos[0], next_pos[1], 1);
            if dist < min_dist {
                min_dist = dist;
                min_index = i;
                is_updated = true;
            }
            if !is_updated {break;}
        }
        if is_updated {
            route.push((1, min_index));
            route.push((2, crt_cluster));
            visited[min_index] = true;
            visited_cluster[crt_cluster] = true;
        }

        // 現在のクラスタでの更新が終わったとき，そのクラスタから一番近い未訪問のステーションに移動する
        if !is_updated {
            let mut min_dist = INF;
            let mut min_index = !0;
            let mut is_updated_cluster = false;
            for i in 0..M {
                if visited_cluster[i] {continue;}
                let crt_pos = &station[crt_cluster];
                let next_pos = &station[i];
                let dist = squared_distance(crt_pos[0], crt_pos[1], 2, next_pos[0], next_pos[1], 2);
                if dist < min_dist {
                    min_dist = dist;
                    min_index = i;
                    is_updated_cluster = true;
                }
            }
            if is_updated_cluster {
                route.push((2, min_index));
                visited_cluster[min_index] = true;
            }
            if !is_updated_cluster {break;}
        }
    }
    route.push((1, 0));
    route
}

#[derive(Clone)]
struct State {
    turn: i64,
    is_done: bool,
    game_score: i64,
    evaluated_score: i64,
    station: Vec<Vec<i64>>, // i番目のステーションの場所
    route: Vec<(usize, usize)>, // 道順 (惑星orステーション，番号)
}
impl State {
    fn new(input: &Input) -> Self {
        // 各惑星をkmeansでクラスタリングする
        // どのクラスタに所属するかと，各クラスタのセントロイドを保持し，セントロイドは宇宙ステーションとする
        let (cluster, station) = kmeans(input.pos.clone(), M);
        // let route = init_route_greedy(&input);
        let route = init_route_kmeans(&input, &cluster, &station);
        Self {
            turn: 0,
            is_done: false,
            game_score: 0,
            evaluated_score: 0,
            station,
            route,
        }
    }
    // 2-optを行う
    pub fn two_opt(&mut self) {
        let v = self.route.len();
    }
    // 回答を出力
    pub fn print(&self) {
        for i in 0..M {
            let station_i = &self.station[i];
            println!("{} {}", station_i[0], station_i[1]);
        }
        let v = self.route.len();
        println!("{}", v);
        for i in 0..v {
            let (ti, ri) = self.route[i];
            println!("{} {}", ti, ri + 1);
        }
    }
}

fn main() {
    // 2-optに見えるが，再訪ありなので単純には適応できない
    // ただ，宇宙ステーションに再訪してもいいが，惑星は再訪しないほうがよい
    // 近傍: 
    // - 2-opt (ただし，最初と最後が惑星1なのは固定する)
    // - 少なくとも一方が宇宙ステーションであるパスの追加
    // - いずれかの宇宙ステーションの座標をずらす (あるいは，これはあらかじめk-meansで求めておく)
    get_time();
    let input = Input::new();
    let mut state = State::new(&input);

    state.print();
    eprintln!("score: {}", state.game_score);
    eprintln!("time: {}", get_time());
}