結果

問題 No.5020 Averaging
ユーザー terry_u16
提出日時 2024-02-25 16:44:57
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 952 ms / 1,000 ms
コード長 7,378 bytes
コンパイル時間 1,132 ms
コンパイル使用メモリ 194,900 KB
実行使用メモリ 6,676 KB
スコア 47,637,392
最終ジャッジ日時 2024-02-25 16:48:02
合計ジャッジ時間 51,649 ms
ジャッジサーバーID
(参考情報)
judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> Main.rs:7:13
   |
7  |           let mut s = {
   |               ----^
   |               |
   |               help: remove this `mut`
...
78 | /         input! {
79 | |             n: usize,
80 | |             c: [(i64, i64); n],
81 | |         }
   | |_________- in this macro invocation
   |
   = note: `#[warn(unused_mut)]` on by default
   = note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: 1 warning emitted

ソースコード

diff #
プレゼンテーションモードにする

macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut 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")
};
}
pub trait ChangeMinMax {
fn change_min(&mut self, v: Self) -> bool;
fn change_max(&mut self, v: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn change_min(&mut self, v: T) -> bool {
*self > v && {
*self = v;
true
}
}
fn change_max(&mut self, v: T) -> bool {
*self < v && {
*self = v;
true
}
}
}
struct Input {
n: usize,
cards: Vec<(i64, i64)>,
}
impl Input {
fn read_input() -> Self {
input! {
n: usize,
c: [(i64, i64); n],
}
let mut cards = vec![];
for (a, b) in c {
let a = a - 500_000_000_000_000_000;
let b = b - 500_000_000_000_000_000;
cards.push((a, b));
}
Input { n, cards }
}
}
#[derive(Debug, Clone)]
struct State {
operations: Vec<(usize, usize)>,
}
impl State {
fn new() -> Self {
State { operations: vec![] }
}
fn calc_score(&self, input: &Input) -> i64 {
let mut cards = input.cards.clone();
for &(a, b) in &self.operations {
let x = (cards[a].0 + cards[b].0) / 2;
let y = (cards[a].1 + cards[b].1) / 2;
cards[a] = (x, y);
cards[b] = (x, y);
}
let v1 = cards[0].0.abs();
let v2 = cards[0].1.abs();
let max = v1.max(v2);
if max == 0 {
2000050 - self.operations.len() as i64
} else {
(2e6 - 1e5 * (max as f64 + 1.0).log10()).floor() as i64
}
}
}
fn main() {
let input = Input::read_input();
let initial_solution = State::new();
let solution = annealing(&input, initial_solution, 0.95);
println!("{}", solution.operations.len());
for (a, b) in solution.operations {
println!("{} {}", a + 1, b + 1);
}
}
fn annealing(input: &Input, initial_solution: State, duration: f64) -> State {
let mut solution = initial_solution;
let mut best_solution = solution.clone();
let mut current_score = solution.calc_score(input);
let mut best_score = current_score;
let init_score = current_score;
let mut all_iter = 0;
let mut valid_iter = 0;
let mut accepted_count = 0;
let mut update_count = 0;
let mut rng = Xorshift::new();
let duration_inv = 1.0 / duration;
let since = std::time::Instant::now();
let temp0 = 1e5;
let temp1 = 3e2;
let mut inv_temp = 1.0 / temp0;
loop {
all_iter += 1;
if (all_iter & ((1 << 4) - 1)) == 0 {
let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;
let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);
inv_temp = 1.0 / temp;
if time >= 1.0 {
break;
}
}
//
let neigh_type = rng.rand(4);
let mut new_state = solution.clone();
if neigh_type == 0 {
if new_state.operations.len() >= 50 {
continue;
}
let (i, j) = loop {
let i = (rng.rand(input.n as u64 * 3) as usize).saturating_sub(input.n * 2);
let j = rng.rand(input.n as u64) as usize;
if i != j {
break (i, j);
}
};
let pos = rng.rand(solution.operations.len() as u64 + 1) as usize;
new_state.operations.insert(pos, (i, j));
} else if neigh_type == 1 {
if new_state.operations.is_empty() {
continue;
}
let pos = rng.rand(solution.operations.len() as u64) as usize;
new_state.operations.remove(pos);
} else {
if new_state.operations.len() < 2 {
continue;
}
let (i, j) = loop {
let i = rng.rand(new_state.operations.len() as u64) as usize;
let j = rng.rand(new_state.operations.len() as u64) as usize;
if i != j {
break (i, j);
}
};
new_state.operations.swap(i, j);
}
//
let new_score = new_state.calc_score(input);
let score_diff = new_score - current_score;
if score_diff >= 0 || rng.randf() < f64::exp(score_diff as f64 * inv_temp) {
//
solution = new_state;
current_score = new_score;
accepted_count += 1;
if best_score.change_max(current_score) {
best_solution = solution.clone();
update_count += 1;
}
}
valid_iter += 1;
}
eprintln!("===== annealing =====");
eprintln!("init score : {}", init_score);
eprintln!("score : {}", best_score);
eprintln!("all iter : {}", all_iter);
eprintln!("valid iter : {}", valid_iter);
eprintln!("accepted : {}", accepted_count);
eprintln!("updated : {}", update_count);
eprintln!("");
best_solution
}
// https://qiita.com/hatoo@github/items/652b81e8e83b0680bc0a
#[derive(Debug)]
#[allow(dead_code)]
pub struct Xorshift {
seed: u64,
}
impl Xorshift {
#[allow(dead_code)]
pub fn new() -> Xorshift {
Xorshift {
seed: 0xf0fb588ca2196dac,
}
}
#[allow(dead_code)]
pub fn with_seed(seed: u64) -> Xorshift {
Xorshift { seed: seed }
}
#[inline]
#[allow(dead_code)]
pub fn next(&mut self) -> u64 {
self.seed = self.seed ^ (self.seed << 13);
self.seed = self.seed ^ (self.seed >> 7);
self.seed = self.seed ^ (self.seed << 17);
self.seed
}
#[inline]
#[allow(dead_code)]
pub fn rand(&mut self, m: u64) -> u64 {
self.next() % m
}
#[inline]
#[allow(dead_code)]
// 0.0 ~ 1.0
pub fn randf(&mut self) -> f64 {
use std::mem;
const UPPER_MASK: u64 = 0x3FF0000000000000;
const LOWER_MASK: u64 = 0xFFFFFFFFFFFFF;
let tmp = UPPER_MASK | (self.next() & LOWER_MASK);
let result: f64 = unsafe { mem::transmute(tmp) };
result - 1.0
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0