結果
| 問題 | No.173 カードゲーム（Medium） |
| コンテスト | |
| ユーザー |
 cologne
|
| 提出日時 | 2026-02-05 17:42:11 |
| 言語 | Rust (1.93.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 1,508 ms / 3,000 ms |
| コード長 | 7,579 bytes |
| 記録 | |
| コンパイル時間 | 2,317 ms |
| コンパイル使用メモリ | 222,276 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2026-02-05 17:42:25 |
| 合計ジャッジ時間 | 13,216 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
コンパイルメッセージ
warning: trait `SmallInt` is never used
--> src/main.rs:9:15
|
9 | pub trait SmallInt {
| ^^^^^^^^
|
= note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default
warning: methods `sample_range`, `sample_uniform`, and `next_bool` are never used
--> src/main.rs:93:16
|
57 | impl SplitMix64 {
| --------------- methods in this implementation
...
93 | pub fn sample_range<T: SmallInt, R: RangeBounds<T>>(&mut self, rng: R) -> T {
| ^^^^^^^^^^^^
...
110 | pub fn sample_uniform(&mut self, rng: Range<f64>) -> f64 {
| ^^^^^^^^^^^^^^
...
116 | pub fn next_bool(&mut self, p_true: f64) -> bool {
| ^^^^^^^^^
ソースコード
use fio::*;
use std::cmp::Reverse;
mod rng {
use std::ops::{
Bound::{Excluded, Included, Unbounded},
Range, RangeBounds,
};
pub trait SmallInt {
fn rng_size_u64<T: RangeBounds<Self>>(rng: &T) -> Option<u64>;
fn pick_nth<T: RangeBounds<Self>>(rng: &T, nth: u64) -> Self;
}
macro_rules! small_int {
($($SelfT:ty)*) => {
$(impl SmallInt for $SelfT {
fn rng_size_u64<T:RangeBounds<Self>>(rng: &T) -> Option<u64> {
let start_inclusive = match rng.start_bound() {
Included(x) => *x,
Excluded(x) => if *x != Self::MAX { x+1 } else {return Some(0)},
Unbounded => Self::MIN,
};
let end_inclusive = match rng.end_bound() {
Included(x) => *x,
Excluded(x) => if *x != Self::MIN { x-1 } else { return Some(0); },
Unbounded => Self::MAX,
};
if start_inclusive > end_inclusive {
Some(0u64)
} else {
(end_inclusive as u64).wrapping_sub(start_inclusive as u64).checked_add(1)
}
}
fn pick_nth<T: RangeBounds<Self>>(rng: &T, nth: u64) -> Self {
(match rng.start_bound() {
Included(x) => ((*x) as u64) + nth,
Excluded(x) => ((*x) as u64).wrapping_add(nth).wrapping_sub(1),
Unbounded => (Self::MIN as u64) + nth,
}) as Self
}
})*
}
}
small_int!(i8 i16 i32 i64 u8 u16 u32 u64);
#[cfg(any(
target_pointer_width = "16",
target_pointer_width = "32",
target_pointer_width = "64"
))]
small_int!(usize isize);
pub struct SplitMix64 {
x: u64,
}
impl SplitMix64 {
pub fn new(seed: u64) -> Self {
Self { x: seed }
}
pub fn next(&mut self) -> u64 {
self.x = self.x.wrapping_add(0x9e3779b97f4a7c15);
let mut z = self.x;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
z ^ (z >> 31)
}
#[cold]
fn _cold_sample(&mut self, n: u64, mut m: u128, mut l: u64) -> u64 {
let t = n.wrapping_neg() % n;
while l < t {
m = (self.next() as u128) * (n as u128);
l = m as u64;
}
(m >> 64) as u64
}
/// Generate number from range from 0..n, i.e. from 0 to n, including 0 and excluding n.
pub fn sample(&mut self, n: u64) -> u64 {
assert_ne!(n, 0, "Cannot sample from empty range");
// Lemire
let m = (self.next() as u128) * (n as u128);
let l = m as u64;
if l < n {
return self._cold_sample(n, m, l);
}
(m >> 64) as u64
}
/// Uniformly sample from range
pub fn sample_range<T: SmallInt, R: RangeBounds<T>>(&mut self, rng: R) -> T {
let nth = match T::rng_size_u64(&rng) {
None => self.next(),
Some(v) => self.sample(v),
};
T::pick_nth(&rng, nth)
}
/// All values that can be generated are form of n * eps/2, for 0.0..1.0
pub fn next_f64(&mut self) -> f64 {
let sig = 1u64 << f64::MANTISSA_DIGITS;
let val = self.sample(sig) as f64;
val / sig as f64
}
/// Uniformly sample from uniform distribution. Only accept standard Range<f64>.
/// All values that can be generated are form of n * eps/2, for 0.0..1.0
pub fn sample_uniform(&mut self, rng: Range<f64>) -> f64 {
let p = self.next_f64();
rng.start * p + rng.end * (1.0 - p)
}
/// Returns true of probability p
pub fn next_bool(&mut self, p_true: f64) -> bool {
assert!((0.0..=1.0).contains(&p_true));
self.next_f64() < p_true
}
}
}
fn main() {
let [n, pa, pb] = read_tuple::<String, 3>();
let n: usize = n.parse().unwrap();
let (pa, pb): (f64, f64) = (pa.parse().unwrap(), pb.parse().unwrap());
let mut a = read_vec::<u16>();
let mut b = read_vec::<u16>();
a.sort_unstable_by_key(|x| Reverse(*x));
b.sort_unstable_by_key(|x| Reverse(*x));
let mut rng = rng::SplitMix64::new(0x1723);
let find_idx = |n: usize, p: f64, v: f64| -> usize {
if v < p {
n - 1
} else {
let v = (v - p) / (1.0 - p);
(v * (n - 1) as f64) as usize
}
};
const ROUND: i32 = 2_000_000;
let mut ans = 0;
let cutoff = a.iter().sum::<u16>() + b.iter().sum::<u16>();
for _ in 0..ROUND {
let mut a = a.clone();
let mut b = b.clone();
let mut a_win = 0;
let mut b_win = 0;
for i in 0..n {
let sa = find_idx(n - i, pa, rng.next_f64());
let sb = find_idx(n - i, pb, rng.next_f64());
if a[sa] > b[sb] {
a_win += a[sa] + b[sb];
} else {
b_win += a[sa] + b[sb];
}
a.remove(sa);
b.remove(sb);
if a_win >= cutoff / 2 + 1 || b_win >= (cutoff + 1) / 2 {
break;
}
}
if a_win > b_win {
ans += 1
}
}
println!("{:.7}", ans as f64 / ROUND as f64);
}
mod fio {
use std::{
cell::RefCell,
convert::TryInto,
fmt::Debug,
io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
str::FromStr,
};
thread_local! {
pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
#[allow(dead_code)]
pub fn read<T: FromStr>() -> T
where
<T as FromStr>::Err: Debug,
{
read_line().parse().unwrap()
}
#[allow(dead_code)]
pub fn read_vec<T: FromStr>() -> Vec<T>
where
<T as FromStr>::Err: Debug,
{
read_line()
.split_whitespace()
.map(|x| x.parse().unwrap())
.collect()
}
#[allow(dead_code)]
pub fn read_tuple<T, const N: usize>() -> [T; N]
where
T: FromStr + Debug,
<T as FromStr>::Err: Debug,
{
read_vec::<T>().try_into().unwrap()
}
/// whitespace at the end of the line is ignored
pub fn read_line() -> String {
let mut s = String::new();
STDIN.with(|cell| {
cell.borrow_mut().read_line(&mut s).unwrap();
});
String::from_str(s.trim_end()).unwrap()
}
}
#[macro_export]
macro_rules! print {
($($t:tt)*) => {
fio::STDOUT.with(|cell|{
use std::io::Write;
write!(cell.borrow_mut(), $($t)*).unwrap()
})};
}
#[macro_export]
macro_rules! println {
($($t:tt)*) => {
fio::STDOUT.with(|cell| {
use std::io::Write;
writeln!(cell.borrow_mut(), $($t)*).unwrap()
})
};
}
#[macro_export]
macro_rules! flush {
() => {
fio::STDOUT.with(|cell| {
use std::io::Write;
cell.borrow_mut().flush().unwrap()
});
};
}