#863016 (Rust) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	nephrologist
提出日時	2023-04-26 12:13:47
言語	Rust (1.77.0)
結果	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
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	901 ms 4,372 KB
testcase_01	AC	902 ms 4,368 KB
testcase_02	AC	902 ms 4,368 KB
testcase_03	AC	902 ms 4,368 KB
testcase_04	AC	902 ms 4,368 KB
testcase_05	AC	902 ms 4,372 KB
testcase_06	AC	902 ms 4,368 KB
testcase_07	AC	902 ms 4,368 KB
testcase_08	AC	902 ms 4,372 KB
testcase_09	AC	901 ms 4,368 KB
testcase_10	AC	902 ms 4,368 KB
testcase_11	AC	901 ms 4,376 KB
testcase_12	AC	901 ms 4,368 KB
testcase_13	AC	902 ms 4,372 KB
testcase_14	AC	901 ms 4,368 KB
testcase_15	AC	902 ms 4,368 KB
testcase_16	AC	902 ms 4,368 KB
testcase_17	AC	902 ms 4,368 KB
testcase_18	AC	902 ms 4,372 KB
testcase_19	AC	902 ms 4,368 KB
testcase_20	AC	901 ms 4,372 KB
testcase_21	AC	902 ms 4,368 KB
testcase_22	AC	902 ms 4,372 KB
testcase_23	AC	902 ms 4,372 KB
testcase_24	AC	902 ms 4,368 KB
testcase_25	AC	902 ms 4,372 KB
testcase_26	AC	902 ms 4,372 KB
testcase_27	AC	902 ms 4,372 KB
testcase_28	AC	902 ms 4,372 KB
testcase_29	AC	902 ms 4,368 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

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

ソースコード

raw source code

//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
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード