diverta 2019 Programming Contest 2 D - Squirrel Merchant 別解

動的計画法は全くわからないので、静的無計画法で解く。 問題

問題(概要)

リスの高橋くんはN個のどんぐりを持っている。

AとB二つの換金所が存在し、それらではどんぐりを金、銀、銅の各資源に相互に変換できる。

レートは換金所によって異なる。

高橋くんはまずAで好きなだけ変換し、次にBで好きなだけ変換し、もう一度Aで変換する。

どんぐりの数は最大何個になるか？

考え方

まず、換金所Aで資源に変えたものを二回目の換金所A訪問時にどんぐりに戻すことはない。

なぜなら、例えば換金所Aでどんぐり→銅に変換して、その後換金所Aで銅→どんぐりに戻しても、レートが変動しないためどんぐりの数は変わらないからである。

よって、Aで得た資源はBでどんぐりに戻し、Bで得た資源はAでどんぐりに戻すことだけを考える。

そこで以下の二つの問題を解く。

1. 高橋くんははじめにN個のどんぐりを持っている。Aで資源に変換し、Bでそれら資源を全てどんぐりに戻す。この時点でのどんぐりの数を最大にせよ。
2. 高橋くんははじめに問題1で最大化された数だけどんぐりMを持っている。Bで資源を変換し、Aでそれら資源を全てどんぐりに戻す。この時点でのどんぐりの数を最大にせよ。

問題1.

二重ループで全探索して得られるどんぐりの最大数を求めればよい。

ここで、一重目のループは換金所Aにてどんぐりを変換して何個の金を得るかで、二重目のループは換金所Aにて残りのどんぐりを変換して何個の銀を得るかである。

残ったどんぐりは、お得(bb > ba)であれば可能な限り銅に変換し、そうでなければどんぐりのままとする。

計算量はO(N^2)である。

問題2

問題1と同じ問題を解けば良いように見える、がMが大きくなるケースがある。

例えばN = 5000、 gb = 5000、 ga = 1みたいな状況だと、M = 5000 * 5000となり、O(M^2)の計算をすることができない。

ここで、もしM > 5000の場合、かならず問題1の過程を経てどんぐりが初期値から増えているので、gb > ga || sb > sa || bb > baである。

ということは、換金所Bにて、資源の少なくともどれか一つについてはどんぐり→資源の変換を行う必要がないことがわかる。

そこで、場合分けを行う。

1. M <= 5000の場合、問題1と同様に解く。
2. M > 5000の場合、1重ループのみを実行する。

分岐2について

たとえばどんぐり→銅の変換を行わないとすると、金銀だけを考えればいいことになる。

これは金を変換する数をループして、残りをもしお得であれば(ga > gb)銀に変換し、そうでなければそのまますべて残せばよいことになる。

これはO(M)のアルゴリズムであり、 M <= 5000 * 5000のため間に合う。

提出コード(Rust)

use std::cmp::*;

#[derive(PartialEq, PartialOrd, Copy, Clone)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

fn main() {
    let mut n = read::<i64>();
    let v = read_vec::<i64>();
    let (ga, sa, ba) = (v[0], v[1], v[2]);
    let v = read_vec::<i64>();
    let (gb, sb, bb) = (v[0], v[1], v[2]);
    // solve question 1
    let mut ans = 0;
    for gi in 0..n + 1 {
        for si in 0..n + 1 {
            if gi * ga + si * sa > n {
                break;
            }
            let mut residual = n - (gi * ga + si * sa);
            if bb > ba {
                residual = (residual / ba) * bb + (residual - (residual / ba) * ba);
            }
            ans = max(ans, gb * gi + sb * si + residual);
        }
    }
    n = ans;

    let order = argsort(&vec![ga / gb, sa / sb, ba / bb]);
    let rates = vec![(gb, ga), (sb, sa), (bb, ba)];
    let (gb, ga) = rates[order[2]];
    let (sb, sa) = rates[order[1]];
    let (bb, ba) = rates[order[0]];

    let max_enable = (n / gb) as i64;
    // solve question 2
    let mut ans = n;
    if n <= 5000 {
        for gi in 0..max_enable + 1 {
            for si in 0..n {
                if gi * gb + si * sb > n {
                    break;
                }
                let mut residual = n - (gi * gb + si * sb);
                if ba > bb {
                    residual = (residual / bb) * ba + (residual - (residual / bb) * bb);
                }
                ans = max(ans, residual + gi * ga + si * sa);
            }
        }
    } else {
        for gi in 0..max_enable + 1 {
            let si = (n - gi * gb) / sb;
            let residual = n - (gi * gb + si * sb);
            ans = max(ans, residual + gi * ga + si * sa);
        }
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn argsort<T: std::cmp::Ord + std::marker::Copy>(v: &Vec<T>) -> Vec<usize> {
    let mut sort_v = Vec::new();
    for i in 0..v.len() {
        sort_v.push((v[i], i));
    }
    sort_v.sort();
    sort_v.iter().map(|x| x.1).collect::<Vec<usize>>()
}

感想

ラスト七分でM > 5000の場合分けを思いついた。諦めない is 大事。

そして提出コード見返すとちょっと嘘解法っぽい気もする。

M > 5000でsa < sbのケースを考えられてない気がするんですよね。

これについては読者の宿題とします(ｷﾘｯ。