#782960 (Rust) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
コンテスト
ユーザー	ntk-ta01
提出日時	2022-07-30 15:14:39
言語	Rust (1.83.0 + proconio)
結果	TLE
実行時間	-
コード長	21,912 bytes
コンパイル時間	1,040 ms
スコア	0
最終ジャッジ日時	2022-07-30 15:15:13
合計ジャッジ時間	33,823 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	TLE * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use ntk_rand::Xorshift;

const TIMELIMIT: f64 = 1.0;

fn main() {
    let input = Input::parse_input();
    let mut timer = Timer::new();
    let mut rng = Xorshift::new();
    let mut solution = Solution::new(&input);
    annealing(&input, &mut solution, &mut timer, &mut rng);
    println!("{}", solution);
    eprintln!("{}", solution.score);
}

fn annealing(input: &Input, solution: &mut Solution, timer: &mut Timer, rng: &mut Xorshift<usize>) {
    const T0: f64 = 100.0;
    const T1: f64 = 0.00001;
    let mut temp = T0;
    let mut prob;

    solution.compute_score(input);
    let mut best_solution = solution.clone();

    let mut count = 0;
    loop {
        if count >= 100 {
            let passed = timer.get_time() / TIMELIMIT;
            if passed >= 1.0 {
                break;
            }
            temp = T0.powf(1.0 - passed) * T1.powf(passed);
            count = 0;
        }
        count += 1;
        let mut new_solution = solution.clone();
        // 近傍解作成
        // ステーションを移動させる move_station
        // 訪問順を変える swap, 2-opt
        let v1 = rng.gen_range(1..new_solution.visits.len() - 1);
        let v2 = rng.gen_range(1..new_solution.visits.len() - 1);
        new_solution.visits.swap(v1, v2);
        // ステーションを訪問させる insert させない remove

        // 近傍解作成ここまで
        new_solution.compute_score(input);
        prob = f64::exp((new_solution.score - solution.score) as f64 / temp);
        if solution.score < new_solution.score || rng.gen_bool(prob) {
            *solution = new_solution;
        }

        if best_solution.score < solution.score {
            best_solution = solution.clone();
        }
    }
    *solution = best_solution;
}

const ALPHA: i64 = 5;

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    m: usize,
    planets: Vec<(i64, i64)>,
}

impl Input {
    fn parse_input() -> Self {
        input! {
            n: usize,
            m: usize,
            planets: [(i64, i64); n],
        }
        Input { n, m, planets }
    }
}

#[derive(Debug, Clone)]
struct Solution {
    stations: Vec<(i64, i64)>,
    visits: Vec<(usize, usize)>, // lenはinput.n + 1以上, (usize, Usize1)の気持ち
    score: i64,
}

impl std::fmt::Display for Solution {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (c, d) in self.stations.iter() {
            writeln!(f, "{} {}", c, d)?;
        }
        writeln!(f, "{}", self.visits.len())?;
        for (t, r) in self.visits.iter() {
            writeln!(f, "{} {}", t, r + 1)?;
        }
        Ok(())
    }
}

fn compute_squared_distance(p1: (i64, i64), p2: (i64, i64)) -> i64 {
    let dx = p1.0 - p2.0;
    let dy = p1.1 - p2.1;
    dx * dx + dy * dy
}

impl Solution {
    fn new(input: &Input) -> Self {
        let stations = vec![(0, 0); input.m];
        let mut visits: Vec<(usize, usize)> = (0..input.n).into_iter().map(|r| (1, r)).collect();
        visits.push((1, 0));
        Solution {
            stations,
            visits,
            score: 0,
        }
    }

    fn compute_score(&mut self, input: &Input) {
        let mut score = 0;
        for i in 0..self.visits.len() - 1 {
            let prev_type = self.visits[i].0;
            let prev_point = if prev_type == 1 {
                input.planets[self.visits[i].1]
            } else {
                self.stations[self.visits[i].1]
            };
            let next_type = self.visits[i + 1].0;
            let next_point = if next_type == 1 {
                input.planets[self.visits[i + 1].1]
            } else {
                self.stations[self.visits[i + 1].1]
            };
            let base_energy = compute_squared_distance(prev_point, next_point);
            let prev_multiplier = if prev_type == 1 { ALPHA } else { 1 };
            let next_multiplier = if next_type == 1 { ALPHA } else { 1 };
            score += base_energy * prev_multiplier * next_multiplier;
        }
        let score = (1e9 / (1000.0 + f64::sqrt(score as f64))).round() as i64;
        self.score = score;
    }
}

pub fn get_time() -> f64 {
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9
}

struct Timer {
    start_time: f64,
}

impl Timer {
    fn new() -> Timer {
        Timer {
            start_time: get_time(),
        }
    }

    fn get_time(&self) -> f64 {
        get_time() - self.start_time
    }
}

#[allow(dead_code)]
mod ntk_rand {
    pub trait Distribution<T, TX> {
        /// Generate a random value of `T`, using `rng` as the source of randomness.
        fn sample(&self, rng: &mut Xorshift<TX>) -> T;
    }

    pub struct Xorshift<T> {
        seed: T,
    }

    impl Xorshift<usize> {
        pub fn new() -> Self {
            Xorshift {
                seed: 0x139408dcbbf7a44,
            }
        }
        pub fn seed_from_u64(seed: usize) -> Xorshift<usize> {
            Xorshift { seed }
        }

        fn gen(&mut self) -> usize {
            self.seed = self.seed ^ (self.seed << 13);
            self.seed = self.seed ^ (self.seed >> 7);
            self.seed = self.seed ^ (self.seed << 17);
            self.seed
        }

        pub fn rand(&mut self) -> usize {
            self.gen()
        }

        fn sample<T, D: Distribution<T, usize>>(&mut self, distr: D) -> T {
            distr.sample(self)
        }

        pub fn gen_bool(&mut self, p: f64) -> bool {
            let d = Bernoulli::new(p).unwrap();
            self.sample(d)
        }

        pub fn gen_range<T, R>(&mut self, range: R) -> T
        where
            T: SampleUniform,
            R: SampleRange<T>,
        {
            range.sample_single(self)
        }
    }
    pub struct Uniform<X: SampleUniform>(X::Sampler);

    impl<X: SampleUniform> Uniform<X> {
        pub fn new<B1, B2>(low: B1, high: B2) -> Uniform<X>
        where
            B1: SampleBorrow<X> + Sized,
            B2: SampleBorrow<X> + Sized,
        {
            Uniform(X::Sampler::new(low, high))
        }

        pub fn new_inclusive<B1, B2>(low: B1, high: B2) -> Uniform<X>
        where
            B1: SampleBorrow<X> + Sized,
            B2: SampleBorrow<X> + Sized,
        {
            Uniform(X::Sampler::new_inclusive(low, high))
        }
    }

    impl<X: SampleUniform> Distribution<X, usize> for Uniform<X> {
        fn sample(&self, rng: &mut Xorshift<usize>) -> X {
            self.0.sample(rng)
        }
    }

    pub trait UniformSampler: Sized {
        /// The type sampled by this implementation.
        type X;

        fn new<B1, B2>(low: B1, high: B2) -> Self
        where
            B1: SampleBorrow<Self::X> + Sized,
            B2: SampleBorrow<Self::X> + Sized;

        fn new_inclusive<B1, B2>(low: B1, high: B2) -> Self
        where
            B1: SampleBorrow<Self::X> + Sized,
            B2: SampleBorrow<Self::X> + Sized;

        /// Sample a value.
        fn sample(&self, rng: &mut Xorshift<usize>) -> Self::X;

        fn sample_single<B1, B2>(low: B1, high: B2, rng: &mut Xorshift<usize>) -> Self::X
        where
            B1: SampleBorrow<Self::X> + Sized,
            B2: SampleBorrow<Self::X> + Sized,
        {
            let uniform: Self = UniformSampler::new(low, high);
            uniform.sample(rng)
        }

        fn sample_single_inclusive<B1, B2>(low: B1, high: B2, rng: &mut Xorshift<usize>) -> Self::X
        where
            B1: SampleBorrow<Self::X> + Sized,
            B2: SampleBorrow<Self::X> + Sized,
        {
            let uniform: Self = UniformSampler::new_inclusive(low, high);
            uniform.sample(rng)
        }
    }

    impl<X: SampleUniform> From<core::ops::Range<X>> for Uniform<X> {
        fn from(r: core::ops::Range<X>) -> Uniform<X> {
            Uniform::new(r.start, r.end)
        }
    }

    impl<X: SampleUniform> From<core::ops::RangeInclusive<X>> for Uniform<X> {
        fn from(r: core::ops::RangeInclusive<X>) -> Uniform<X> {
            Uniform::new_inclusive(r.start(), r.end())
        }
    }

    pub trait SampleUniform: Sized {
        /// The `UniformSampler` implementation supporting type `X`.
        type Sampler: UniformSampler<X = Self>;
    }

    pub trait SampleBorrow<Borrowed> {
        /// Immutably borrows from an owned value. See [`Borrow::borrow`]
        ///
        /// [`Borrow::borrow`]: std::borrow::Borrow::borrow
        fn borrow(&self) -> &Borrowed;
    }
    impl<Borrowed> SampleBorrow<Borrowed> for Borrowed
    where
        Borrowed: SampleUniform,
    {
        #[inline(always)]
        fn borrow(&self) -> &Borrowed {
            self
        }
    }
    impl<'a, Borrowed> SampleBorrow<Borrowed> for &'a Borrowed
    where
        Borrowed: SampleUniform,
    {
        #[inline(always)]
        fn borrow(&self) -> &Borrowed {
            *self
        }
    }

    /// Range that supports generating a single sample efficiently.
    ///
    /// Any type implementing this trait can be used to specify the sampled range
    /// for `Rng::gen_range`.
    pub trait SampleRange<T> {
        /// Generate a sample from the given range.
        fn sample_single(self, rng: &mut Xorshift<usize>) -> T;

        /// Check whether the range is empty.
        fn is_empty(&self) -> bool;
    }

    impl<T: SampleUniform + PartialOrd> SampleRange<T> for core::ops::Range<T> {
        #[inline]
        fn sample_single(self, rng: &mut Xorshift<usize>) -> T {
            T::Sampler::sample_single(self.start, self.end, rng)
        }

        #[inline]
        fn is_empty(&self) -> bool {
            // !(self.start >= self.end)
            self.start < self.end
        }
    }

    impl<T: SampleUniform + PartialOrd> SampleRange<T> for core::ops::RangeInclusive<T> {
        #[inline]
        fn sample_single(self, rng: &mut Xorshift<usize>) -> T {
            T::Sampler::sample_single_inclusive(self.start(), self.end(), rng)
        }

        #[inline]
        fn is_empty(&self) -> bool {
            // !(self.start() <= self.end())
            self.start() > self.end()
        }
    }
    pub trait WideningMultiply<RHS = Self> {
        type Output;

        fn wmul(self, x: RHS) -> Self::Output;
    }

    macro_rules! wmul_impl {
        ($ty:ty, $wide:ty, $shift:expr) => {
            impl WideningMultiply for $ty {
                type Output = ($ty, $ty);

                #[inline(always)]
                fn wmul(self, x: $ty) -> Self::Output {
                    let tmp = (self as $wide) * (x as $wide);
                    ((tmp >> $shift) as $ty, tmp as $ty)
                }
            }
        };

        // simd bulk implementation
        ($(($ty:ident, $wide:ident),)+, $shift:expr) => {
            $(
                impl WideningMultiply for $ty {
                    type Output = ($ty, $ty);

                    #[inline(always)]
                    fn wmul(self, x: $ty) -> Self::Output {
                        // For supported vectors, this should compile to a couple
                        // supported multiply & swizzle instructions (no actual
                        // casting).
                        // TODO: optimize
                        let y: $wide = self.cast();
                        let x: $wide = x.cast();
                        let tmp = y * x;
                        let hi: $ty = (tmp >> $shift).cast();
                        let lo: $ty = tmp.cast();
                        (hi, lo)
                    }
                }
            )+
        };
    }
    wmul_impl! { u8, u16, 8 }
    wmul_impl! { u16, u32, 16 }
    wmul_impl! { u32, u64, 32 }
    wmul_impl! { u64, u128, 64 }

    macro_rules! wmul_impl_large {
        ($ty:ty, $half:expr) => {
            impl WideningMultiply for $ty {
                type Output = ($ty, $ty);

                #[inline(always)]
                fn wmul(self, b: $ty) -> Self::Output {
                    const LOWER_MASK: $ty = !0 >> $half;
                    let mut low = (self & LOWER_MASK).wrapping_mul(b & LOWER_MASK);
                    let mut t = low >> $half;
                    low &= LOWER_MASK;
                    t += (self >> $half).wrapping_mul(b & LOWER_MASK);
                    low += (t & LOWER_MASK) << $half;
                    let mut high = t >> $half;
                    t = low >> $half;
                    low &= LOWER_MASK;
                    t += (b >> $half).wrapping_mul(self & LOWER_MASK);
                    low += (t & LOWER_MASK) << $half;
                    high += t >> $half;
                    high += (self >> $half).wrapping_mul(b >> $half);

                    (high, low)
                }
            }
        };

        // simd bulk implementation
        (($($ty:ty,)+) $scalar:ty, $half:expr) => {
            $(
                impl WideningMultiply for $ty {
                    type Output = ($ty, $ty);

                    #[inline(always)]
                    fn wmul(self, b: $ty) -> Self::Output {
                        // needs wrapping multiplication
                        const LOWER_MASK: $scalar = !0 >> $half;
                        let mut low = (self & LOWER_MASK) * (b & LOWER_MASK);
                        let mut t = low >> $half;
                        low &= LOWER_MASK;
                        t += (self >> $half) * (b & LOWER_MASK);
                        low += (t & LOWER_MASK) << $half;
                        let mut high = t >> $half;
                        t = low >> $half;
                        low &= LOWER_MASK;
                        t += (b >> $half) * (self & LOWER_MASK);
                        low += (t & LOWER_MASK) << $half;
                        high += t >> $half;
                        high += (self >> $half) * (b >> $half);

                        (high, low)
                    }
                }
            )+
        };
    }
    wmul_impl_large! { u128, 64 }

    macro_rules! wmul_impl_usize {
        ($ty:ty) => {
            impl WideningMultiply for usize {
                type Output = (usize, usize);

                #[inline(always)]
                fn wmul(self, x: usize) -> Self::Output {
                    let (high, low) = (self as $ty).wmul(x as $ty);
                    (high as usize, low as usize)
                }
            }
        };
    }
    #[cfg(target_pointer_width = "16")]
    wmul_impl_usize! { u16 }
    #[cfg(target_pointer_width = "32")]
    wmul_impl_usize! { u32 }
    #[cfg(target_pointer_width = "64")]
    wmul_impl_usize! { u64 }

    pub struct UniformInt<X> {
        low: X,
        range: X,
        z: X,
    }

    macro_rules! uniform_int_impl {
        ($ty:ty, $unsigned:ident, $u_large:ident) => {
            impl SampleUniform for $ty {
                type Sampler = UniformInt<$ty>;
            }

            impl UniformSampler for UniformInt<$ty> {
                type X = $ty;

                #[inline]
                fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
                where
                    B1: SampleBorrow<Self::X> + Sized,
                    B2: SampleBorrow<Self::X> + Sized,
                {
                    let low = *low_b.borrow();
                    let high = *high_b.borrow();
                    assert!(low < high, "Uniform::new called with `low >= high`");
                    UniformSampler::new_inclusive(low, high - 1)
                }

                #[inline]
                fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
                where
                    B1: SampleBorrow<Self::X> + Sized,
                    B2: SampleBorrow<Self::X> + Sized,
                {
                    let low = *low_b.borrow();
                    let high = *high_b.borrow();
                    assert!(
                        low <= high,
                        "Uniform::new_inclusive called with `low > high`"
                    );
                    let unsigned_max = core::$u_large::MAX;

                    let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned;
                    let ints_to_reject = if range > 0 {
                        let range = $u_large::from(range);
                        (unsigned_max - range + 1) % range
                    } else {
                        0
                    };

                    UniformInt {
                        low,
                        range: range as $ty,
                        z: ints_to_reject as $unsigned as $ty,
                    }
                }

                #[inline]
                fn sample(&self, rng: &mut Xorshift<$u_large>) -> Self::X {
                    let range = self.range as $unsigned as $u_large;
                    if range > 0 {
                        let unsigned_max = core::$u_large::MAX;
                        let zone = unsigned_max - (self.z as $unsigned as $u_large);
                        loop {
                            let v: $u_large = rng.gen();
                            let (hi, lo) = v.wmul(range);
                            if lo <= zone {
                                return self.low.wrapping_add(hi as $ty);
                            }
                        }
                    } else {
                        rng.gen()
                    }
                }

                #[inline]
                fn sample_single<B1, B2>(
                    low_b: B1,
                    high_b: B2,
                    rng: &mut Xorshift<$u_large>,
                ) -> Self::X
                where
                    B1: SampleBorrow<Self::X> + Sized,
                    B2: SampleBorrow<Self::X> + Sized,
                {
                    let low = *low_b.borrow();
                    let high = *high_b.borrow();
                    assert!(low < high, "UniformSampler::sample_single: low >= high");
                    Self::sample_single_inclusive(low, high - 1, rng)
                }

                #[inline]
                fn sample_single_inclusive<B1, B2>(
                    low_b: B1,
                    high_b: B2,
                    rng: &mut Xorshift<$u_large>,
                ) -> Self::X
                where
                    B1: SampleBorrow<Self::X> + Sized,
                    B2: SampleBorrow<Self::X> + Sized,
                {
                    let low = *low_b.borrow();
                    let high = *high_b.borrow();
                    assert!(
                        low <= high,
                        "UniformSampler::sample_single_inclusive: low > high"
                    );
                    let range = high.wrapping_sub(low).wrapping_add(1) as $unsigned as $u_large;
                    if range == 0 {
                        return rng.gen();
                    }

                    let zone = if core::$unsigned::MAX <= core::u16::MAX as $unsigned {
                        let unsigned_max: $u_large = core::$u_large::MAX;
                        let ints_to_reject = (unsigned_max - range + 1) % range;
                        unsigned_max - ints_to_reject
                    } else {
                        (range << range.leading_zeros()).wrapping_sub(1)
                    };

                    loop {
                        let v: $u_large = rng.gen();
                        let (hi, lo) = v.wmul(range);
                        if lo <= zone {
                            return low.wrapping_add(hi as $ty);
                        }
                    }
                }
            }
        };
    }

    uniform_int_impl! { usize, usize, usize }

    pub struct Bernoulli {
        p_int: u64,
    }

    const ALWAYS_TRUE: u64 = u64::max_value();

    const SCALE: f64 = 2.0 * (1u64 << 63) as f64;

    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
    pub enum BernoulliError {
        InvalidProbability,
    }

    impl Bernoulli {
        #[inline]
        pub fn new(p: f64) -> Result<Bernoulli, BernoulliError> {
            if !(0.0..1.0).contains(&p) {
                if p == 1.0 {
                    return Ok(Bernoulli { p_int: ALWAYS_TRUE });
                }
                return Err(BernoulliError::InvalidProbability);
            }
            Ok(Bernoulli {
                p_int: (p * SCALE) as u64,
            })
        }
    }

    impl Distribution<bool, usize> for Bernoulli {
        #[inline]
        fn sample(&self, rng: &mut Xorshift<usize>) -> bool {
            if self.p_int == ALWAYS_TRUE {
                return true;
            }
            let v: u64 = rng.gen() as u64;
            v < self.p_int
        }
    }
}
yukicoder

結果

ソースコード
