結果
問題 | No.5020 Averaging |
ユーザー | nephrologist |
提出日時 | 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 |
ソースコード
#![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 }