Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

コイン問題で嵌ったので反省文を書きます

コイン問題とは

コイン問題というのは、「ある金額を作るのに最小のコイン数」を求めなさいという問題です。日本の貨幣はうまく設計されているため貪欲法で自明ですが、一般に拡張するとDPが必要になります。

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_A

f:id:akiradeveloper529:20190307140251j:plain

DPの初歩的な問題だと思いますが、盛大に嵌って半日溶かしたのでしっかりと反省しておきます。もしかしたら他の人にとってもDPの理解に役立つかも。

最初の解答

私の初期の解答がこれです。

fn solve() {
    input! {
        N: usize, M: usize,
        C: [usize; M],
    }

    let mut dp = vec![vec![None; N+1]; M+1];
    dp[0][0] = Some(0);
    for i in 1..M+1 {
        for j in 0..N+1 {
            let mut k = 0;
            let coin = C[i-1];
            while j >= k*coin {
                if dp[i-1][j-k*coin].is_some() {
                    dp[i][j] = Some(min(dp[i][j].unwrap_or(1<<30), dp[i-1][j-k*coin].unwrap()+k));
                }
                k += 1;
            }
        }
    }

    println!("{}", dp[M][N].unwrap());
}

方針としては、

  1. i番目までのコインを使ってj円を作る時の最小個数を考える。もし、何らかの最小個数がi番目まででj円を成し遂げていた経路の場合、その最小をとっているはずだから
  2. d[i+1][j]はmin(d[i][jd[i], [j-k*coin[i+1]]+k for all k)である

これは、(少なくともTLEするまでは)正しい答えを出しましたが、TLEします。はじめにその理由を考えます。

TLEをアドホックに修正しましょう

計算の伝搬を図に書くと無駄な計算があることがわかります。

f:id:akiradeveloper529:20190202120423j:plain

図において、青線で書いた伝搬は、赤線の伝搬で満たしてるように見えます。そこで以下のように計算を減らしてみます。

f:id:akiradeveloper529:20190202120553j:plain

while j >= k*coin && k < 2

しかしこれでも間違っています。

最終解

上の修正の間違いは、cの計算では青を使いたいのに、bの計算をした時には赤が計算されて、それが青に逆伝搬していないことです。したがって最終解としては、1次元のDPテーブルを使って、計算結果をin-placeに伝搬することです。

    let mut dp = vec![None; N+1];
    dp[0] = Some(0);
    for i in 1..M+1 {
        for j in 0..N+1 {
            let coin = C[i-1];
            if j >= coin {
                if dp[j-coin].is_some() {
                    dp[j] = Some(min(dp[j].unwrap_or(1<<30), dp[j-coin].unwrap()+1));
                }
            }
        }
    }

これでACします。10回くらい提出してすいませんでした。

勘違いの原因は何か?

私の勘違いの原因は、「DPテーブルは大は小を兼ねる」「DPテーブルを2次元にすることはメモリ消費量だけの問題であり、in-placeな更新をなくすことでわかりやすさが増すだけである」と考えていたことです。でも実際には「1次元のDPテーブルを使わないと解けない問題が存在する」ということがわかりました。DPは図に書くとわかりやすくなりますね。