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

提出ソース

結果

問題	No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー	terry_u16
提出日時	2022-10-14 23:07:39
言語	Rust (1.77.0 + proconio)
結果	TLE
実行時間	-
コード長	11,006 bytes
コンパイル時間	1,289 ms
実行使用メモリ	9,228 KB
スコア	0
最終ジャッジ日時	2022-10-14 23:08:09
合計ジャッジ時間	8,432 ms
ジャッジサーバーID （参考情報）	judge8 / judge9

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-

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

コンパイルメッセージ

warning: variable `inv_temp` is assigned to, but never used
   --> Main.rs:304:13
    |
304 |     let mut inv_temp = 1.0 / temp0;
    |             ^^^^^^^^
    |
    = note: `#[warn(unused_variables)]` on by default
    = note: consider using `_inv_temp` instead

warning: value assigned to `inv_temp` is never read
   --> Main.rs:311:13
    |
311 |             inv_temp = 1.0 / temp;
    |             ^^^^^^^^
    |
    = note: `#[warn(unused_assignments)]` on by default
    = help: maybe it is overwritten before being read?

warning: 2 warnings emitted

ソースコード

raw source code

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

#[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;
        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 remain = time - t;
            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));
}

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 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 mut time = 0.0;

    let temp0 = 1e5;
    let temp1 = 1e3;
    let mut inv_temp = 1.0 / temp0;

    while time < 1.0 {
        all_iter += 1;
        if (all_iter & ((1 << 4) - 1)) == 0 {
            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;
        }

        // 変形
        let index = rng.rand(input.n as u64) as usize;
        let sign = rng.rand(2) as i64 * 2 - 1;
        let change_type = rng.rand(3);
        let mut new_state = solution.clone();

        if change_type == 1 {
            let new_init = new_state.pendulums[index].init + sign;

            if new_init <= 0 || new_init > 1_000_000_000 {
                continue;
            }

            new_state.pendulums[index].init = new_init;
        } else if change_type == 2 {
            let new_min = new_state.pendulums[index].min + sign;

            if new_min <= 0 || new_min > new_state.pendulums[index].init {
                continue;
            }

            new_state.pendulums[index].min = new_min;
        } else {
            let damper = new_state.pendulums[index].damper + sign;

            if damper <= 0
                || damper > new_state.pendulums[index].init - new_state.pendulums[index].min
            {
                continue;
            }

            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 * inv_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!("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 _ in 0..input.n {
        pendulums.push(Pendulum::new(1, 1, 1));
    }

    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

結果

テストケース

コンパイルメッセージ

ソースコード