結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 ntk-ta01
|
| 提出日時 | 2022-07-30 14:34:08 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 1,000 ms |
| コード長 | 20,442 bytes |
| コンパイル時間 | 919 ms |
| 実行使用メモリ | 6,952 KB |
| スコア | 1,221,702 |
| 最終ジャッジ日時 | 2022-07-30 14:34:11 |
| 合計ジャッジ時間 | 2,696 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
warning: unused variable: `timer`
--> Main.rs:57:9
|
57 | let timer = Timer::new();
| ^^^^^ help: if this is intentional, prefix it with an underscore: `_timer`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `rng`
--> Main.rs:58:13
|
58 | let mut rng = Xorshift::new();
| ^^^ help: if this is intentional, prefix it with an underscore: `_rng`
warning: unused variable: `input`
--> Main.rs:65:14
|
65 | fn annealing(input: &Input, solution: &mut Solution, timer: &mut Timer, rng: &mut Xorshift<usize>) {
| ^^^^^ help: if this is intentional, prefix it with an underscore: `_input`
warning: variable does not need to be mutable
--> Main.rs:56:9
|
56 | let mut input = Input::parse_input();
| ----^^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> Main.rs:58:9
|
58 | let mut rng = Xorshift::new();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:59:9
|
59 | let mut solution = Solution::new(&input);
| ----^^^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:84:13
|
84 | let mut new_solution = solution.clone();
| ----^^^^^^^^^^^^
| |
| help: remove this `mut`
warning: constant is never used: `TIMELIMIT`
--> Main.rs:53:1
|
53 | const TIMELIMIT: f64 = 1.0;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function is never used: `annealing`
--> Main.rs:65:4
|
65 | fn annealing(input: &Input, solution: &mut Solution, timer: &mut Timer, rng: &mut Xorshift<usize>) {
| ^^^^^^^^^
warning: constant is never used: `ALPHA`
--> Main.rs:100:1
|
100 | const ALPHA
ソースコード
// 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 mut input = Input::parse_input();
let timer = Timer::new();
let mut rng = Xorshift::new();
let mut solution = Solution::new(&input);
// ステーションをどこに置くか
// どの順番で訪問するか 数列で訪問順を持つ？
println!("{}", solution);
}
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;
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();
// 近傍解作成
// 近傍解作成ここまで
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: usize = 5;
#[derive(Debug, Clone)]
struct Input {
n: usize,
m: usize,
planets: Vec<Vec<i64>>,
}
impl Input {
fn parse_input() -> Self {
input! {
n: usize,
m: usize,
planets: [[i64; 2]; n],
}
Input { n, m, planets }
}
}
#[derive(Debug, Clone)]
struct Solution {
stations: Vec<Vec<i64>>,
transits: Vec<Vec<i64>>,
score: i64,
}
impl std::fmt::Display for Solution {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
for station in self.stations.iter() {
writeln!(f, "{} {}", station[0], station[1])?;
}
writeln!(f, "{}", self.transits.len())?;
for transit in self.transits.iter() {
writeln!(f, "{} {}", transit[0], transit[1])?;
}
Ok(())
}
}
impl Solution {
fn new(input: &Input) -> Self {
let stations = vec![vec![0; 2]; input.m];
let mut transits: Vec<Vec<i64>> = (1..=input.n)
.into_iter()
.map(|r| vec![1, r as i64])
.collect();
transits.push(vec![1, 1]);
Solution {
stations,
transits,
score: 0,
}
}
fn compute_score(&mut self) {
self.score = 0;
}
}
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
}
}
}