Rustコトハジメ

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

動的計画法でOptionを使うとわかりやすい説

DPではDPテーブルの初期状態を決める必要があります。それはふつう、漸化式から求まるのですが、下のナップザック問題を解くDPの場合、dp[0]=0が初期状態ですね。

そしてこの場合、C++など他の言語では他のマスを-1など意味のない値で初期化すると思います。しかし、そういうコードを読むと、私には少しわかりにくいと感じますし、バグりやすいと思います。

以下のコードでは、値が決まってるということを強調するために初期値だけをSomeとして、他をNoneとしました。

fn solve() {
    input! {
        N: usize, W: usize,
        X: [(usize,usize); N],
    };

    let mut dp = vec![None; W+1];
    dp[0] = Some(0);
    
    for i in 0..N {
        let (v,w) = X[i];
        for j in (0..W+1).rev() {
            if dp[j].is_none() {
                continue;
            }
            if j+w <= W {
                dp[j+w] = Some(max(dp[j+w].unwrap_or(0), dp[j].unwrap()+v));
            }
        }
    }

    let mut max = 0;
    for v in &dp {
        max = std::cmp::max(max, v.unwrap_or(0));
    }
    println!("{}", max);
}

こうすると、Someのところ以外からは計算が続かないことが明らかになりますし、is_noneでガードしてるところでもこのことを強調出来ます。Noneのところの初期値は、「比較の便宜上」0にしてもいいから0にするということがunwrap_orのところからわかります。

dpテーブルをすべて0で初期化する方法もあると思いますが、そうなるとOptionを使うことの良さがなお際立ちます。

競技プログラマは短くてシンプルなコードを書くことを好む傾向がありそうなので、こういうコードは嫌う人が多そうなイメージがありますが、私は良いと思うので、今やっているDP修業では一貫して使っていこうと思います。

ただ、Rustはこういう現代的なパーツが揃っていて良い反面、インデックスにusize型を強要されることが競プロでは少し不利になってくると感じています。例えばこのコードであれば、商品の重さと価値は別にu32でもいいですし、むしろusizeにするのは不自然ですが、そうしないとjがusizeでwがu32なので足し算するのに明示的なキャストが必要になり、コードがごちゃごちゃしてきます。また、-1で最後の要素にアクセスするということも出来ないので、これも不利になることがあります。バグのないソフトウェアを作るためには仕方がないことだとは思いますが、競プロ向けに緩和モードを導入してくれたらよいなと思います。