#807502 (Rust) No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance

提出ソース

結果

問題	No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー	terry_u16
提出日時	2022-10-15 00:25:49
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	1,902 ms / 2,000 ms
コード長	10,941 bytes
コンパイル時間	1,181 ms
実行使用メモリ	6,952 KB
スコア	1,352,892,399,588,136
最終ジャッジ日時	2022-10-15 00:27:35
合計ジャッジ時間	105,635 ms
ジャッジサーバーID （参考情報）	judge14 / judge9
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,901 ms 4,904 KB
testcase_01	AC	1,902 ms 4,904 KB
testcase_02	AC	1,900 ms 4,904 KB
testcase_03	AC	1,901 ms 4,904 KB
testcase_04	AC	1,902 ms 4,900 KB
testcase_05	AC	1,902 ms 6,948 KB
testcase_06	AC	1,901 ms 4,904 KB
testcase_07	AC	1,900 ms 4,900 KB
testcase_08	AC	1,901 ms 6,948 KB
testcase_09	AC	1,902 ms 4,904 KB
testcase_10	AC	1,902 ms 4,904 KB
testcase_11	AC	1,901 ms 4,900 KB
testcase_12	AC	1,900 ms 4,904 KB
testcase_13	AC	1,901 ms 4,900 KB
testcase_14	AC	1,901 ms 4,900 KB
testcase_15	AC	1,902 ms 4,908 KB
testcase_16	AC	1,902 ms 4,904 KB
testcase_17	AC	1,901 ms 4,904 KB
testcase_18	AC	1,900 ms 4,904 KB
testcase_19	AC	1,901 ms 4,900 KB
testcase_20	AC	1,901 ms 4,900 KB
testcase_21	AC	1,901 ms 4,900 KB
testcase_22	AC	1,901 ms 4,900 KB
testcase_23	AC	1,901 ms 4,900 KB
testcase_24	AC	1,900 ms 4,900 KB
testcase_25	AC	1,901 ms 6,952 KB
testcase_26	AC	1,901 ms 2,868 KB
testcase_27	AC	1,901 ms 4,900 KB
testcase_28	AC	1,901 ms 4,900 KB
testcase_29	AC	1,901 ms 4,904 KB
testcase_30	AC	1,902 ms 6,948 KB
testcase_31	AC	1,901 ms 4,900 KB
testcase_32	AC	1,901 ms 4,904 KB
testcase_33	AC	1,901 ms 6,952 KB
testcase_34	AC	1,900 ms 4,904 KB
testcase_35	AC	1,900 ms 6,948 KB
testcase_36	AC	1,902 ms 6,948 KB
testcase_37	AC	1,901 ms 6,952 KB
testcase_38	AC	1,902 ms 4,904 KB
testcase_39	AC	1,901 ms 6,952 KB
testcase_40	AC	1,900 ms 4,904 KB
testcase_41	AC	1,901 ms 4,904 KB
testcase_42	AC	1,902 ms 4,908 KB
testcase_43	AC	1,901 ms 4,904 KB
testcase_44	AC	1,901 ms 4,904 KB
testcase_45	AC	1,902 ms 4,900 KB
testcase_46	AC	1,901 ms 6,948 KB
testcase_47	AC	1,901 ms 4,900 KB
testcase_48	AC	1,902 ms 6,952 KB
testcase_49	AC	1,901 ms 4,900 KB

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

コンパイルメッセージ

warning: unused import: `time::Instant`
 --> Main.rs:1:25
  |
1 | use std::{fmt::Display, time::Instant};
  |                         ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: 1 warning emitted

ソースコード

raw source code

use std::{fmt::Display, time::Instant};

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

#[allow(unused_macros)]
macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

#[allow(unused_macros)]
macro_rules! mat {
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[allow(unused_macros)]
macro_rules! skip_none {
    ($res:expr) => {
        if let Some(v) = $res {
            v
        } else {
            continue;
        }
    };
}

#[derive(Debug, Clone)]
struct Input {
    n: usize,
    _k: usize,
    oppose_times: Vec<i64>,
    coop_times: Vec<i64>,
}

impl Input {
    fn read_input() -> Self {
        input! {
            n: usize,
            k: usize,
            oppose_times: [i64; k],
            coop_times: [i64; k]
        }

        Self {
            n,
            _k: k,
            oppose_times,
            coop_times,
        }
    }
}

#[derive(Debug, Clone)]
struct State {
    pendulums: Vec<Pendulum>,
}

impl State {
    fn calc_score_all(&self, input: &Input) -> i64 {
        let mut oppose_x = Vec::with_capacity(self.pendulums.len());
        let mut coop_x = Vec::with_capacity(self.pendulums.len());

        for p in self.pendulums.iter() {
            let op = p.get_all_x(&input.oppose_times);
            let co = p.get_all_x(&input.coop_times);
            oppose_x.push(op);
            coop_x.push(co);
        }

        let mut oppose_sum = 0.0;
        let mut coop_sum = 0.0;

        for i in 0..oppose_x.len() {
            let xi = &oppose_x[i];
            let pi = &self.pendulums[i];

            for j in (i + 1)..oppose_x.len() {
                let xj = &oppose_x[j];
                let pj = &self.pendulums[j];

                for (x, y) in xi.iter().zip(xj) {
                    oppose_sum += (x - y).abs() as f64 / (pi.init + pj.init) as f64;
                }
            }
        }

        let mut max = vec![std::i64::MIN; coop_x.len()];
        let mut min = vec![std::i64::MAX; coop_x.len()];

        for x in coop_x.iter() {
            for (i, &x) in x.iter().enumerate() {
                chmax!(max[i], x);
                chmin!(min[i], x);
            }
        }

        for i in 0..coop_x.len() {
            coop_sum += ((max[i] - min[i]) as f64 * 0.05 + 1.0).sqrt();
        }

        let oppose_score = oppose_sum * 2e7 / (input.n * (input.n - 1)) as f64;
        let coop_score = 1e7 / coop_sum;

        (oppose_score * coop_score).round() as i64
    }
}

impl Display for State {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "{} {} {}",
            self.pendulums[0].init, self.pendulums[0].min, self.pendulums[0].damper
        )?;

        for p in self.pendulums[1..].iter() {
            writeln!(f)?;
            write!(f, "{} {} {}", p.init, p.min, p.damper)?;
        }

        Ok(())
    }
}

#[derive(Debug, Clone, Copy)]
struct Pendulum {
    init: i64,
    min: i64,
    damper: i64,
}

impl Pendulum {
    fn new(init: i64, min: i64, damper: i64) -> Self {
        Self { init, min, damper }
    }

    fn get_x(&self, time: i64) -> i64 {
        // 振幅がmin以下になる時間
        let min_round = (self.init - self.min) / self.damper / 2;
        let init_period = self.get_period(0);
        let last_period = self.get_period(min_round);
        let min_t = min_round * (init_period + last_period) / 2;

        let round = if time >= min_t {
            min_round
        } else {
            binary_search(
                &|round| {
                    let last_period = self.get_period(round);
                    let t = min_round * (init_period + last_period) / 2;
                    t <= time
                },
                0,
                (time + init_period - 1) / init_period + 1,
            )
        };

        let round_period = self.get_period(round);
        let mut t = round * (init_period + round_period) / 2;
        let mut amp = self.get_amp(round);
        let mut dir = 1;

        loop {
            let mut remain = time - t;

            if amp == self.min {
                remain %= 2 * amp;
            }

            if remain <= 2 * amp {
                if remain <= amp {
                    return dir * remain;
                } else {
                    return dir * (2 * amp - remain);
                }
            }

            t += 2 * amp;
            amp -= self.damper;
            amp = amp.max(self.min);
            dir = -dir;
        }
    }

    fn get_all_x(&self, times: &[i64]) -> Vec<i64> {
        let mut x = Vec::with_capacity(times.len());

        for &t in times {
            x.push(self.get_x(t));
        }

        x
    }

    fn get_amp(&self, round: i64) -> i64 {
        (self.init - self.damper * round * 2).max(self.min)
    }

    fn get_period(&self, round: i64) -> i64 {
        self.get_amp(round) * 4 - 4
    }
}

fn main() {
    let input = Input::read_input();
    let state = get_init_state(&input);
    let state = annealing(&input, state, 1.9);

    eprintln!("{}", state.calc_score_all(&input));
    println!("{}", state);
}

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_all(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(42);

    let duration_inv = 1.0 / duration;
    let since = std::time::Instant::now();

    let temp0 = 1e12;
    let temp1 = 1e10;

    loop {
        all_iter += 1;

        let time = (std::time::Instant::now() - since).as_secs_f64() * duration_inv;
        if time >= 1.0 {
            break;
        }
        let temp = f64::powf(temp0, 1.0 - time) * f64::powf(temp1, time);

        // 変形
        let index = rng.rand(input.n as u64) as usize;
        let mut new_state = solution.clone();

        let init = rng.rand(10) as i64 + 1;
        let min = rng.rand(init as u64) as i64 + 1;
        let damper = rng.rand(init as u64) as i64 + 1;
        new_state.pendulums[index].init = init;
        new_state.pendulums[index].min = min;
        new_state.pendulums[index].damper = damper;

        // スコア計算
        let new_score = new_state.calc_score_all(input);
        let score_diff = new_score - current_score;

        if score_diff >= 0 || rng.randf() < f64::exp(score_diff as f64 / temp) {
            // 解の更新
            current_score = new_score;
            solution = new_state;
            accepted_count += 1;

            if chmax!(best_score, 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
}

fn get_init_state(input: &Input) -> State {
    let mut pendulums = vec![];

    for i in 0..input.n {
        let j = (i % 2 + 1) as i64;
        pendulums.push(Pendulum::new(j, j, j));
    }

    State { pendulums }
}

fn binary_search<F: Fn(i64) -> bool>(f: &F, mut ok: i64, mut ng: i64) -> i64 {
    while (ok - ng).abs() > 1 {
        let mid = (ok + ng) / 2;

        if f(mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    ok
}

#[derive(Debug)]
#[allow(dead_code)]
pub struct Xorshift {
    seed: u64,
}

#[allow(dead_code)]
impl Xorshift {
    pub fn new(seed: u64) -> Xorshift {
        Xorshift { seed }
    }

    #[inline]
    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]
    pub fn rand(&mut self, m: u64) -> u64 {
        self.next() % m
    }

    #[inline]
    // 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
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード