結果

問題 No.2390 Udon Coupon (Hard)
コンテスト
ユーザー 👑 Mizar
提出日時 2023-08-04 13:17:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 5,299 bytes
コンパイル時間 12,427 ms
コンパイル使用メモリ 401,500 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-14 10:12:25
合計ジャッジ時間 14,213 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

// O((A_max)^2)解法
// 入力制約: 0 <= n <= 10^13, 0 < a_i < 2^15, 0 <= b_i, b_max * floor(n / a_min) <= 2^61
pub fn solve(
    n: u64,
    mut a1: u64,
    mut b1: u64,
    mut a2: u64,
    mut b2: u64,
    mut a3: u64,
    mut b3: u64,
) -> u64 {
    // 最大効率の割引が 1番(a1,b1) となるように交換
    if a2 * b1 < a1 * b2 {
        core::mem::swap(&mut a1, &mut a2);
        core::mem::swap(&mut b1, &mut b2);
    }
    if a3 * b1 < a1 * b3 {
        core::mem::swap(&mut a1, &mut a3);
        core::mem::swap(&mut b1, &mut b3);
    }
    // ゼロ除算例外によるpanicコード生成(wasmバイナリサイズが10000bytes以上に増える)の抑止
    if a1 == 0 {
        return 0;
    }
    // 準定数を除数とする除算の定数倍高速化
    // a1inv = ceil(2^34 / a1) = floor((2^34 - 1) / a1) + 1
    // 2^32 / a1 <= a1inv < 2^32 / a1 + 1
    let a1inv = ((1u64 << 34) - 1) / a1 + 1;
    let (a1b2, a1b3) = (a1 * b2, a1 * b3);
    // c1min: 1番(a1,b1) の割引の最低使用回数
    // c1min = max(floor(n / a1) - (a2 + a3), 0)
    let c1min = (n / a1).saturating_sub(a2 + a3);
    // n - c1min * a1: うどん札を c1min 回使用した時の残り枚数
    let (mut r, mut p, mut s) = (0, 0, n - c1min * a1);
    // 2番・3番の割引使用回数 c2, c3 が 0 <= c2,c3 < a1 の範囲で最大割引額を全探索
    // p: 2番目を c2 回使用した場合の割引額
    // s: 1番目を c1min 回、2番目を c2 回使用した場合のうどん札残り枚数
    while p < a1b2 {
        let (mut q, mut t) = (0, s);
        // q: 3番目を c3 回使用した場合の割引額
        // t: 1番目を c1min 回、2番目を c2 回、3番目を c3 回使用した場合のうどん札残り枚数
        while q < a1b3 {
            // 準定数を除数とする除算の定数倍高速化
            // 0 < {a1,a2,a3} <= 2000, 0 <= t < 2000*(2*2000+1)
            // a1 * t < 2^34 --> quot = floor(ceil(2^34 / a1) * t / 2^34) = floor(t / a1)
            let quot = t * a1inv >> 34;
            debug_assert_eq!(t / a1, quot);
            r.chmax(quot * b1 + p + q);
            t = match t.checked_sub(a3) {
                Some(t) => t,
                None => break,
            };
            q += b3;
        }
        s = match s.checked_sub(a2) {
            Some(s) => s,
            None => break,
        };
        p += b2;
    }
    // r: うどん札を n - c1min * a1 枚持っていた場合の最大割引額
    // r + c1min * b1: うどん札を n 枚持っていた場合の最大割引額
    r + c1min * b1
}

fn main() {
    #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
    #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
    let mut stdinlock = std::io::stdin().lock();
    let mut lines = std::io::BufRead::lines(&mut stdinlock).map_while(Result::ok);
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initial"));
    let n = lines.next().unwrap().parse::<u64>().unwrap();
    let mut ab = [(0u64, 0u64); 3];
    for e in ab.iter_mut() {
        let s = lines.next().unwrap();
        let mut t = s.split_whitespace();
        *e = (
            t.next().unwrap().parse::<u64>().unwrap(),
            t.next().unwrap().parse::<u64>().unwrap(),
        );
    }
    let [(a1, b1), (a2, b2), (a3, b3)] = ab;
    println!("{}", solve(n, a1, b1, a2, b2, a3, b3));
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "output"));

    // Execution Time.
    #[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); };
}

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

#[cfg(test)]
mod tests {
    use crate::solve;
    #[test]
    fn sample() {
        // 01_sample_01
        assert_eq!(solve(16, 3, 90, 5, 100, 10, 390), 570);
        // 01_sample_02
        assert_eq!(solve(50, 80, 800000, 90, 900000, 100, 1000000), 0);
        // 01_sample_03
        assert_eq!(
            solve(1000000000000, 1300, 800000, 1700, 900000, 2000, 1000000),
            615384615200000
        );
    }
    #[test]
    fn killer() {
        // 06_killer_15
        assert_eq!(
            solve(7066707559, 1870, 982556, 1931, 980792, 1957, 999999),
            3713066717075
        );
        // 06_killer_16
        assert_eq!(
            solve(6513797687, 1816, 993333, 1875, 988809, 1913, 999999),
            3562978311024
        );
        // 06_killer_17
        assert_eq!(
            solve(6186832959, 1799, 990454, 1842, 984815, 1867, 999999),
            3406210181876
        );
        // 06_killer_18
        assert_eq!(
            solve(6788528330, 1833, 985582, 1910, 989146, 1939, 999999),
            3650109095581
        );
        // 06_killer_19
        assert_eq!(
            solve(6503471505, 1843, 991882, 1869, 997268, 1888, 999999),
            3500095060313
        );
    }
    #[test]
    fn challenge() {
        // 98_challenge01
        assert_eq!(solve(5, 4, 100, 3, 74, 9, 1), 100);
    }
}
0