結果
問題 |
No.2390 Udon Coupon (Hard)
|
ユーザー |
👑 |
提出日時 | 2023-06-28 15:35:35 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 2,728 bytes |
コンパイル時間 | 13,887 ms |
コンパイル使用メモリ | 378,016 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 01:27:46 |
合計ジャッジ時間 | 13,218 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
// O((A_max)^2)解法 // 入力制約: 0 <= n <= 10^13, 0 < a_i <= 10^5, 0 < b_i, b_max * floor(n / a_min) <= 2^61 fn solve(n: u64, ab: [(u64, u64); 3]) -> u64 { let (a_min, a_max, b_min, b_max) = ab.iter().fold((!0u64, 0u64, !0u64, 0u64), |(a_min, a_max, b_min, b_max), &(a, b)| (a.min(a_min), a.max(a_max), b.min(b_min), b.max(b_max))); assert!(n <= 10_0000_0000_0000); assert!(a_min > 0 && a_max <= 100000 && b_min > 0 && b_max.saturating_mul(n / a_min) <= (1u64 << 61)); let co_solve = |n: u64, ab: [(u64, u64); 3]| -> u64 { let [(ap, bp), (aq, bq), (ar, br)] = ab; // a_p_inv = ceil(2^63 / a_p) = floor((2^63 - 1) / a_p) + 1 let apinv = ((1u64 << 63) - 1) / ap + 1; let (imax, jmax) = (ap * bq, ap * br); let (mut r, mut ibq, mut di) = (0, 0, n); while ibq < imax { let (mut jbr, mut dj) = (0, di); while jbr < jmax { // 準定数を除数とする除算の定数倍高速化 // 0 < a_p <= 10^5, 0 <= d_j <= n <= 10^13 < 2^63/10^5 <= 2^63 / a_p <= ceil(2^63 / a_p) = a_p_inv < ((2^63 / a_p) + 1) // quot = floor((n - (i * a_q + j * a_r)) / a_p) = floor(d / a_p) = floor((d * 2) * ceil(2^63 / a_p) / 2^64) - (0 または 1) let qsim = ((((dj * 2) as u128) * (apinv as u128)) >> 64) as u64; let quot = qsim - u64::from(qsim * ap > dj); debug_assert_eq!(dj / ap, quot); r.chmax(quot * bp + ibq + jbr); if let Some(d) = dj.checked_sub(ar) { dj = d; jbr += br; } else { break; } } if let Some(d) = di.checked_sub(aq) { di = d; ibq += bq; } else { break; } } r }; co_solve(n, [ab[0], ab[1], ab[2]]) .max(co_solve(n, [ab[1], ab[2], ab[0]])) .max(co_solve(n, [ab[2], ab[0], ab[1]])) } fn main() { let mut stdinlock = std::io::stdin().lock(); let mut lines = std::io::BufRead::lines(&mut stdinlock).map_while(Result::ok); let n = lines.next().unwrap().parse::<u64>().unwrap(); let ab = (0..3).map(|_| { let s = lines.next().unwrap(); let mut t = s.split_whitespace(); ( t.next().unwrap().parse::<u64>().unwrap(), t.next().unwrap().parse::<u64>().unwrap(), ) }).collect::<Vec<_>>(); println!("{}", solve(n, [ab[0], ab[1], ab[2]])); } trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); } impl<T: PartialOrd> Change for T { fn chmax(&mut self, x: T) { if *self < x { *self = x; } } fn chmin(&mut self, x: T) { if *self > x { *self = x; } } }