結果

問題 No.5020 Averaging
ユーザー nephrologistnephrologist
提出日時 2024-02-25 19:21:46
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 972 ms / 1,000 ms
コード長 8,274 bytes
コンパイル時間 1,861 ms
コンパイル使用メモリ 199,452 KB
実行使用メモリ 67,552 KB
スコア 26,483,611
最終ジャッジ日時 2024-02-25 19:22:47
合計ジャッジ時間 55,205 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 949 ms
63,304 KB
testcase_01 AC 957 ms
64,380 KB
testcase_02 AC 900 ms
63,304 KB
testcase_03 AC 941 ms
62,684 KB
testcase_04 AC 937 ms
63,132 KB
testcase_05 AC 910 ms
63,624 KB
testcase_06 AC 928 ms
65,868 KB
testcase_07 AC 943 ms
64,180 KB
testcase_08 AC 931 ms
64,832 KB
testcase_09 AC 924 ms
64,980 KB
testcase_10 AC 942 ms
66,916 KB
testcase_11 AC 930 ms
65,896 KB
testcase_12 AC 919 ms
62,576 KB
testcase_13 AC 934 ms
65,432 KB
testcase_14 AC 881 ms
62,988 KB
testcase_15 AC 906 ms
62,452 KB
testcase_16 AC 947 ms
65,568 KB
testcase_17 AC 918 ms
63,088 KB
testcase_18 AC 879 ms
61,548 KB
testcase_19 AC 914 ms
64,372 KB
testcase_20 AC 947 ms
65,676 KB
testcase_21 AC 961 ms
67,456 KB
testcase_22 AC 898 ms
65,436 KB
testcase_23 AC 902 ms
63,096 KB
testcase_24 AC 929 ms
64,460 KB
testcase_25 AC 914 ms
65,604 KB
testcase_26 AC 928 ms
67,552 KB
testcase_27 AC 907 ms
65,944 KB
testcase_28 AC 972 ms
65,644 KB
testcase_29 AC 909 ms
63,424 KB
testcase_30 AC 905 ms
65,592 KB
testcase_31 AC 915 ms
64,668 KB
testcase_32 AC 941 ms
65,440 KB
testcase_33 AC 910 ms
64,728 KB
testcase_34 AC 888 ms
64,712 KB
testcase_35 AC 909 ms
62,680 KB
testcase_36 AC 934 ms
63,328 KB
testcase_37 AC 918 ms
66,712 KB
testcase_38 AC 914 ms
64,112 KB
testcase_39 AC 930 ms
65,780 KB
testcase_40 AC 945 ms
66,892 KB
testcase_41 AC 935 ms
66,160 KB
testcase_42 AC 898 ms
66,304 KB
testcase_43 AC 923 ms
64,344 KB
testcase_44 AC 937 ms
63,376 KB
testcase_45 AC 962 ms
64,444 KB
testcase_46 AC 890 ms
63,412 KB
testcase_47 AC 912 ms
66,148 KB
testcase_48 AC 946 ms
65,112 KB
testcase_49 AC 934 ms
65,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(unused_mut)]
#![allow(non_upper_case_globals)]
//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 mokuhyou: usize = 500000000000000000;
const n: usize = 45;
use std::cmp::Ordering;
use std::cmp::{Eq, Ord, PartialEq, PartialOrd};
use std::collections::{BinaryHeap, HashSet};
const WID: usize = 500;
const CHA: usize = 20;
const keta: usize = 1000000000000000000;
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 main() {
    get_time();
    input! {nn:usize, XY:[(usize,usize);n]}
    let inp = Input { XY };
    let mut rng = Xorshift::new(20250225);
    // eprintln!("XY {:?}", &inp.XY);
    let bestboard = beam_search(&inp, &mut rng, WID, CHA);
    bestboard.printstate();
    eprintln!(
        "{}",
        bestboard.nowval[0].0.abs_diff(mokuhyou) + bestboard.nowval[0].1.abs_diff(mokuhyou)
    );
    eprintln!("time {}", get_time());
    eprintln!("cost {}", bestboard.cost);
}

struct Xorshift {
    val: usize,
}
impl Xorshift {
    fn new(seed: usize) -> Self {
        let mut hoge = seed;
        hoge ^= seed << 17;
        hoge ^= seed >> 13;
        hoge ^= seed << 5;
        Xorshift { val: hoge }
    }
    fn next(&mut self) {
        let hoge = self.val;
        self.val ^= hoge << 17;
        self.val ^= hoge >> 13;
        self.val ^= hoge << 5;
    }
    fn rand(&mut self) -> f64 {
        self.next();
        (self.val / std::usize::MAX) as f64
    }
    fn randint(&mut self, a: usize, b: usize) -> usize {
        self.next();
        self.val % (b - a) + a
    }
}
struct Input {
    XY: Vec<(usize, usize)>,
}
#[derive(Clone)]
// #[derive(Debug, PartialEq, PartialOrd, Eq)]
struct Board {
    orders: Vec<(usize, usize)>,
    nowval: Vec<(usize, usize)>,
    goukei: f64,
    nijou: f64,
    cost: f64,
    turn: usize,
    hash: usize,
}

impl Board {
    fn new(inp: &Input) -> Self {
        let mut goukei = 0.0;
        let mut nijou = 0.0;
        let mut hash = 0;
        for &(a, b) in inp.XY.iter() {
            let aa = a as f64 / keta as f64;
            let bb = b as f64 / keta as f64;
            hash ^= a;
            hash ^= b;
            goukei += aa + bb;
            nijou += aa * aa + bb * bb;
        }

        Self {
            orders: vec![],
            nowval: inp.XY.clone(),
            goukei,
            nijou,
            cost: std::f64::MAX,
            turn: 0,
            hash,
        }
    }
    fn action(&mut self, a: usize, b: usize, rng: &mut Xorshift) {
        // eprintln!("a b {} {}", a, b);
        assert!(a != b);
        let n1 = self.nowval[a].0;
        let n2 = self.nowval[a].1;
        let n3 = self.nowval[b].0;
        let n4 = self.nowval[b].1;
        let v1 = (n1 + n3) / 2;
        let v2 = (n2 + n4) / 2;
        self.nowval[a] = (v1, v2);
        self.nowval[b] = (v1, v2);
        self.orders.push((a + 1, b + 1));
        let nn1 = n1 as f64 / keta as f64;
        let nn2 = n2 as f64 / keta as f64;
        let nn3 = n3 as f64 / keta as f64;
        let nn4 = n4 as f64 / keta as f64;
        let vv1 = (nn1 + nn3) / 2.0;
        let vv2 = (nn2 + nn4) / 2.0;
        self.hash ^= n1 ^ n2 ^ n3 ^ n4;

        self.nijou +=
            2.0 * (vv1 * vv1 + vv2 * vv2) - (nn1 * nn1 + nn2 * nn2 + nn3 * nn3 + nn4 * nn4);
        self.calccost(rng);
    }
    fn calccost(&mut self, rng: &mut Xorshift) {
        let std = self.nijou / ((n as f64) * 2.0)
            - (self.goukei as f64 / n as f64) * (self.goukei as f64 / n as f64) / 4.0;
        // eprintln!("std {}", std);
        self.cost = (mokuhyou.abs_diff(self.nowval[0].0) + mokuhyou.abs_diff(self.nowval[0].1))
            as f64
            - 10.0 * std * (50.0 - self.turn as f64) / 50.0;
        // self.cost = (mokuhyou.abs_diff(self.nowval[0].0) + mokuhyou.abs_diff(self.nowval[0].1))
        //     as f64
        //     + rng.rand();
    }
    fn printstate(&self) {
        println!("{}", self.orders.len());
        for &(a, b) in self.orders.iter() {
            println!("{} {}", a, b);
        }
    }
}
// 順序関係を作る。

impl Ord for Board {
    fn cmp(&self, other: &Self) -> Ordering {
        other.partial_cmp(self).unwrap_or(Ordering::Equal)
    }
}

impl PartialEq for Board {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}
impl Eq for Board {} // ここは空でOK
impl PartialOrd for Board {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        other.cost.partial_cmp(&self.cost)
    }
}

fn beam_search(inp: &Input, rng: &mut Xorshift, beam_width: usize, challenge_time: usize) -> Board {
    let mut board = Board::new(inp);
    let mut preheap = BinaryHeap::new();
    let mut nexheap = BinaryHeap::new();
    board.calccost(rng);
    let mut bestboard = board.clone();
    preheap.push(board);
    for turn in 0..50 {
        // eprintln!("turn {}", turn);
        // eprintln!("size {}", preheap.len());
        for __ in 0..beam_width {
            let mut memo = HashSet::new();
            if preheap.is_empty() {
                break;
            }
            // eprintln!("pre");
            let mut preboard = preheap.pop().unwrap();
            preboard.turn = turn;
            for ___ in 0..challenge_time {
                let mut nexboard = preboard.clone();
                let idx1 = rng.randint(1, n - 1);
                let idx2 = rng.randint(idx1 + 1, n);
                nexboard.action(idx1, idx2, rng);
                if !memo.contains(&nexboard.hash) {
                    memo.insert(nexboard.hash);
                    nexheap.push(nexboard);
                }
            }
            for i in 1..n {
                let mut nexboard = preboard.clone();
                nexboard.action(0, i, rng);
                if !memo.contains(&nexboard.hash) {
                    memo.insert(nexboard.hash);
                    nexheap.push(nexboard);
                }
            }
        }
        preheap.clear();
        for _ in 0..beam_width {
            if nexheap.is_empty() {
                break;
            }
            // eprintln!("nex");
            let mut board = nexheap.pop().unwrap();
            if board.cost < bestboard.cost {
                eprintln!("best");
                bestboard = board.clone();
            }
            preheap.push(board);
        }
        nexheap.clear()
    }

    bestboard
}
0