結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 nephrologist
|
| 提出日時 | 2023-04-26 12:13:47 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 902 ms / 1,000 ms |
| コード長 | 10,191 bytes |
| コンパイル時間 | 5,477 ms |
| コンパイル使用メモリ | 156,052 KB |
| 実行使用メモリ | 4,376 KB |
| スコア | 7,908,057 |
| 最終ジャッジ日時 | 2023-04-26 12:14:23 |
| 合計ジャッジ時間 | 34,179 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
コンパイルメッセージ
warning: unused variable: `inp`
--> Main.rs:352:17
|
352 | fn doublebridge(inp: &Input, ans: &Vec<(usize, usize)>, rng: &mut Rng) -> Vec<(usize, usize)> {
| ^^^ help: if this is intentional, prefix it with an underscore: `_inp`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> Main.rs:30:13
|
30 | let mut s = {
| ----^
| |
| help: remove this `mut`
...
191 | input! {n: usize, m: usize, AB:[(i32,i32); n]};
| ---------------------------------------------- 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: variable does not need to be mutable
--> Main.rs:195:14
|
195 | let (mut aa, mut bb) = AB[i];
| ----^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:195:22
|
195 | let (mut aa, mut bb) = AB[i];
| ----^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:249:9
|
249 | let mut tempscore = calcscore(&inp, &tempans, &dist);
| ----^^^^^^^^^
| |
| help: remove this `mut`
warning: constant `ALPHA` is never used
--> Main.rs:74:7
|
74 | const ALPHA: i64 = 5;
| ^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: struct `State` is never constructed
--> Main.rs:88:8
|
88 | struct State {
| ^^^^^
warning: structure field `AB` should have a snake case name
--> Main.rs:79:5
|
79 | AB: Vec<(i32, i32)>,
| ^^ help: convert the identifier to snake case: `ab`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variabl
ソースコード
//rand
struct Rng {
seed: usize,
}
impl Rng {
pub fn new(seed: usize) -> Rng {
Rng { seed }
}
pub fn next(&mut self) {
self.seed ^= self.seed << 13;
self.seed ^= self.seed >> 15;
self.seed ^= self.seed << 17;
}
pub fn gen_range(&mut self, a: usize, b: usize) -> usize {
self.next();
self.seed % (b - a) + a
}
}
//proconio
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")
};
}
const TIMELIMIT: f64 = 0.9;
const ALPHA: i64 = 5;
const RATIO: f64 = 0.99;
struct Input {
n: usize,
m: usize,
AB: Vec<(i32, i32)>,
}
impl Input {
fn new(n: usize, m: usize, AB: Vec<(i32, i32)>) -> Input {
Input { n, m, AB }
}
}
struct State {
labels: Vec<usize>,
score: usize,
}
fn calcscore(inp: &Input, ans: &Vec<(usize, usize)>, dist: &Vec<Vec<i128>>) -> i128 {
let mut res = 0_i128;
for i in 0..ans.len() - 1 {
let (type1, mut idx1) = ans[i];
let (type2, mut idx2) = ans[i + 1];
if type1 == 2 {
idx1 += inp.n;
}
if type2 == 2 {
idx2 += inp.n;
}
res += dist[idx1][idx2];
}
res
}
// fn debug(inp: &Input) {
// for i in 0..inp.m {
// println!("{} {}", i, i);
// }
// let v = 101;
// println!("{}", v);
// for i in 0..inp.n {
// println!("{} {}", 1, i + 1);
// }
// println!("{} {}", 1, 1);
// }
fn calcdist(x: i32, y: i32, xx: i32, yy: i32) -> i128 {
(x as i128 - xx as i128) * (x as i128 - xx as i128)
+ (y as i128 - yy as i128) * (y as i128 - yy as i128)
}
fn calcdistf(x: f64, y: f64, xx: f64, yy: f64) -> f64 {
(x - xx) * (x - xx) + (y - yy) * (y - yy)
}
fn kmeans(inp: &Input, n_class: usize, ratio: f64) -> (Vec<usize>, Vec<(i32, i32)>) {
let mut res_label: Vec<usize> = (0..inp.n).map(|x| x % n_class).collect();
let mut is_update = true;
let mut res_g = Vec::new();
while is_update {
is_update = false;
let mut num_cnt = vec![0; inp.m];
let mut x_cnt = vec![0; inp.m];
let mut y_cnt = vec![0; inp.m];
for i in 0..inp.n {
let (a, b) = inp.AB[i];
let label = res_label[i];
num_cnt[label] += 1;
x_cnt[label] += a;
y_cnt[label] += b;
}
let mut g_memo = Vec::new();
for i in 0..inp.m {
let gx = x_cnt[i] as f64 / num_cnt[i] as f64;
let gy = y_cnt[i] as f64 / num_cnt[i] as f64;
g_memo.push((gx, gy));
}
for i in 0..inp.n {
let x = inp.AB[i].0 as f64;
let y = inp.AB[i].1 as f64;
let (xx, yy) = g_memo[res_label[i]];
let mut pre_dist = calcdistf(x, y, xx, yy);
for j in 0..inp.m {
let (xx, yy) = g_memo[j];
let temp_dist = calcdistf(x, y, xx, yy);
if temp_dist < pre_dist {
pre_dist = temp_dist;
is_update = true;
res_label[i] = j;
}
}
}
if !is_update {
for &(x, y) in g_memo.iter() {
res_g.push(((x * ratio) as i32, (y * ratio) as i32))
}
}
}
(res_label, res_g)
}
fn print_gmemo(g_memo: Vec<(i32, i32)>, da: i32, db: i32) {
for &(a, b) in g_memo.iter() {
println!("{} {}", a + da, b + db);
}
}
fn print_ans(ans: Vec<(usize, usize)>) {
println!("{}", ans.len());
for (a, b) in ans.iter() {
println!("{} {}", a, b + 1);
}
}
fn main() {
get_time();
input! {n: usize, m: usize, AB:[(i32,i32); n]};
let (a, b) = AB[0];
let mut ab = Vec::new();
for i in 0..n {
let (mut aa, mut bb) = AB[i];
ab.push((aa - a, bb - b));
}
let inp = Input::new(n, m, ab);
let n_class = 8;
let (labels, g_memo) = kmeans(&inp, n_class, RATIO);
let mut dist = vec![vec![0; inp.n + inp.m]; inp.n + inp.m];
for i in 0..inp.n {
let (x, y) = inp.AB[i];
for j in i + 1..inp.n {
let (xx, yy) = inp.AB[j];
let d = 5 * 5 * calcdist(x, y, xx, yy);
dist[i][j] = d;
dist[j][i] = d;
}
}
for i in 0..inp.m {
let (x, y) = g_memo[i];
for j in i + 1..inp.m {
let (xx, yy) = g_memo[j];
let d = calcdist(x, y, xx, yy);
dist[i + n][j + n] = d;
dist[j + n][i + n] = d;
}
}
for i in 0..inp.n {
let (x, y) = inp.AB[i];
for j in 0..inp.m {
let (xx, yy) = g_memo[j];
let d = 5 * calcdist(x, y, xx, yy);
dist[i][j + n] = d;
dist[j + n][i] = d;
}
}
let mut tempans: Vec<(usize, usize)> = Vec::new();
tempans.push((1, 0));
for i in 0..inp.m {
tempans.push((2, i));
for j in 0..inp.n {
if labels[j] == i {
tempans.push((1, j));
tempans.push((2, i));
}
}
}
tempans.push((1, 0));
let n_point = 210;
assert_eq!(n_point, tempans.len());
let mut tempscore = calcscore(&inp, &tempans, &dist);
let mut cnt = 0;
let mut kickcnt = 0;
let mut bestcnt = 0;
let mut bestans = tempans.clone();
let mut bestscore = tempscore;
let mut rng = Rng::new(20230424);
while get_time() < TIMELIMIT {
let (update, mut workingans) = opt2(&inp, &tempans, &dist);
cnt += 1;
if !update {
let workingscore = calcscore(&inp, &workingans, &dist);
if workingscore < bestscore {
bestscore = workingscore;
bestans = workingans.clone();
bestcnt += 1;
}
// after opt2, change to neighbor
workingans = doublebridge(&inp, &workingans, &mut rng);
kickcnt += 1;
}
// renew variables
// 100%採用
tempans = workingans;
}
print_gmemo(g_memo, a, b);
print_ans(bestans);
eprintln!("cnt {}", cnt);
eprintln!("kickcnt {}", kickcnt);
eprintln!("bestcnt {}", bestcnt);
}
pub fn get_time() -> f64 {
static mut STIME: f64 = -1.0; // 初期値
let t = std::time::SystemTime::now() // nowを取得
.duration_since(std::time::UNIX_EPOCH)
.unwrap();
// a.duration_since(b)だとa>bが前提
let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
// as_secsが秒, .subsec_nanos()が小数点以下の秒
unsafe {
if STIME < 0.0 {
STIME = ms; // 経過時間の初期化
}
// ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
#[cfg(feature = "local")]
{
(ms - STIME) * 1.3
}
#[cfg(not(feature = "local"))]
{
ms - STIME
}
}
}
fn opt2(
inp: &Input,
pre: &Vec<(usize, usize)>,
dist: &Vec<Vec<i128>>,
) -> (bool, Vec<(usize, usize)>) {
let mut res = pre.clone();
let mut update: bool = false;
for first in 1..(pre.len() - 2) {
let (type1, mut idx1) = res[first];
let (type2, mut idx2) = res[first + 1];
if type1 == 2 {
idx1 += inp.n;
}
if type2 == 2 {
idx2 += inp.n;
}
for second in (first + 2)..pre.len() - 1 {
let (type3, mut idx3) = res[second];
let (type4, mut idx4) = res[second + 1];
if type3 == 2 {
idx3 += inp.n;
}
if type4 == 2 {
idx4 += inp.n;
}
// println!("{} {} {} {}", first, nf, second, ns);
let d1 = dist[idx1][idx2];
let d2 = dist[idx3][idx4];
let d3 = dist[idx1][idx3];
let d4 = dist[idx2][idx4];
if d1 + d2 > d3 + d4 {
res[(first + 1)..(second + 1)].reverse();
update = true;
break;
}
if update {
break;
}
}
}
(update, res)
}
// t1 a1,a2 t2 b1,b2, t3 c1,c2, t4 d1,d2, t5
// t1 a1,c2, t4 d1,b2, t3 c1,a2 t2 b1,d2 t5
fn doublebridge(inp: &Input, ans: &Vec<(usize, usize)>, rng: &mut Rng) -> Vec<(usize, usize)> {
// let mut rng = Rng::new(20230424);
let n = ans.len() - 1;
let idx1 = rng.gen_range(1_usize, n - 8);
let idx2 = rng.gen_range(idx1 + 2, n - 6);
let idx3 = rng.gen_range(idx2 + 2, n - 4);
let idx4 = rng.gen_range(idx3 + 2, n - 2);
// let mut res = ans[0..=idx1].append(ans[idx1+1..=idx2])+ans[idx2+1..=idx3]+ans[idx3+1..=idx4]+[idx4+1..=n]
let mut res: Vec<(usize, usize)> = Vec::new();
for v in &ans[0..=idx1] {
res.push(*v);
}
for v in &ans[idx3 + 1..=idx4] {
res.push(*v);
}
for v in &ans[idx2 + 1..=idx3] {
res.push(*v);
}
for v in &ans[idx1 + 1..=idx2] {
res.push(*v);
}
for v in &ans[idx4 + 1..] {
res.push(*v);
}
res
}