結果

問題 No.5020 Averaging
ユーザー terry_u16terry_u16
提出日時 2024-02-25 14:25:15
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 952 ms / 1,000 ms
コード長 7,204 bytes
コンパイル時間 1,063 ms
コンパイル使用メモリ 194,580 KB
実行使用メモリ 6,676 KB
スコア 40,186,203
最終ジャッジ日時 2024-02-25 14:26:07
合計ジャッジ時間 51,405 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 951 ms
6,676 KB
testcase_01 AC 951 ms
6,676 KB
testcase_02 AC 951 ms
6,676 KB
testcase_03 AC 951 ms
6,676 KB
testcase_04 AC 951 ms
6,676 KB
testcase_05 AC 950 ms
6,676 KB
testcase_06 AC 952 ms
6,676 KB
testcase_07 AC 951 ms
6,676 KB
testcase_08 AC 951 ms
6,676 KB
testcase_09 AC 951 ms
6,676 KB
testcase_10 AC 951 ms
6,676 KB
testcase_11 AC 952 ms
6,676 KB
testcase_12 AC 951 ms
6,676 KB
testcase_13 AC 952 ms
6,676 KB
testcase_14 AC 951 ms
6,676 KB
testcase_15 AC 951 ms
6,676 KB
testcase_16 AC 951 ms
6,676 KB
testcase_17 AC 950 ms
6,676 KB
testcase_18 AC 951 ms
6,676 KB
testcase_19 AC 950 ms
6,676 KB
testcase_20 AC 952 ms
6,676 KB
testcase_21 AC 952 ms
6,676 KB
testcase_22 AC 952 ms
6,676 KB
testcase_23 AC 951 ms
6,676 KB
testcase_24 AC 951 ms
6,676 KB
testcase_25 AC 952 ms
6,676 KB
testcase_26 AC 951 ms
6,676 KB
testcase_27 AC 952 ms
6,676 KB
testcase_28 AC 951 ms
6,676 KB
testcase_29 AC 951 ms
6,676 KB
testcase_30 AC 951 ms
6,676 KB
testcase_31 AC 950 ms
6,676 KB
testcase_32 AC 951 ms
6,676 KB
testcase_33 AC 950 ms
6,676 KB
testcase_34 AC 951 ms
6,676 KB
testcase_35 AC 951 ms
6,676 KB
testcase_36 AC 951 ms
6,676 KB
testcase_37 AC 951 ms
6,676 KB
testcase_38 AC 951 ms
6,676 KB
testcase_39 AC 951 ms
6,676 KB
testcase_40 AC 951 ms
6,676 KB
testcase_41 AC 951 ms
6,676 KB
testcase_42 AC 951 ms
6,676 KB
testcase_43 AC 952 ms
6,676 KB
testcase_44 AC 952 ms
6,676 KB
testcase_45 AC 951 ms
6,676 KB
testcase_46 AC 951 ms
6,676 KB
testcase_47 AC 951 ms
6,676 KB
testcase_48 AC 951 ms
6,676 KB
testcase_49 AC 952 ms
6,676 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 | |             cards: [(u64, u64); 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<(u64, u64)>,
}

impl Input {
    fn read_input() -> Self {
        input! {
            n: usize,
            cards: [(u64, u64); n],
        }

        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_diff(500_000_000_000_000_000);
        let v2 = cards[0].1.abs_diff(500_000_000_000_000_000);
        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 = 1e4;
    let temp1 = 1e2;
    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(3);
        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) as usize;
                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
    }
}
0