📐

Rustで動的計画法：Dequeue

2023/04/20に公開

Rust

AtCoder

動的計画法

tech

はじめに

動的計画法を実装してみて、Rustの勉強をやってみる。問題としてはEducational DP Contestという動的計画法の練習を目的としたコンテストのものを使用。

https://atcoder.jp/contests/dp/

AからZまで問題が設定されているが、今回はLのDeque。交互に数値を取っていって、点数を競い合うゲーム。

利用したライブラリ

標準入力からデータを読み取る部分はproconioを利用。

久々にchmaxを使うかな？と思ったが、maxしか要らなかったので、std::cmp::maxを使用。

完成したコード

実装というより、アルゴリズムの方が難しくなってきている。

dqueue_2.rs

use proconio::input;

fn main(){
    input!(
        n: usize,
        queue: [i64; n]
    );
    let mut dp: Vec<Vec<i64>>  = Vec::with_capacity(n);
    for i in 0..n {
        let mut row = vec![0i64; i + 1];
        row[i] = queue[i];
        dp.push(row);
    }

    for i in 1..n {
        for j in (0..i).rev() {
            dp[i][j] = max(queue[i] - dp[i - 1][j], queue[j] - dp[i][j + 1]);
        }
    }
    println!("{}", dp[n-1][0]);
}

アルゴリズム

まず、「太郎君は $X-Y$ を最大化しようとし、次郎君は $X-Y$ を最小化しようとします。」のところを、「太郎君のスコアを $X-Y$ 、次郎君のスコアを $Y-X$ とし、2人はスコアを最大化しようとします。」と読み替える。ゲームとしてはこちらの方が自然な気はする。太郎君のスコアと次郎君のスコアは符合が異なるだけで、絶対値は等しい。つまり $X-Y = -(Y-X)$ ．

dp[i][j]を $j$ から $i (\geq j)$ までの数列が残っている状況で、数値を取る順番の人が取得できるスコアの最大値とする。つまり太郎君の順の時はdp[i][j]には $X-Y$ が入り、次郎君の順の時はdp[i][j]には $Y-X$ が入る。dp[i][i]は $i$ 番目の数値しか残っていないことを意味するため、ここからのスコアの最大値はqueue[i]となる（初期値）。

dp[i][j]の状態からの遷移は $j$ 番目の数値をとるか、 $i$ 番目の数値を取るかの2択で、その後相手が取得できるスコアの最大値はそれぞれdp[i][j+1]とdp[i-1][j]となる。相手はスコアを最大にする手を選択するので、dp[i][j]の値は取った数値から、遷移先の相手の点数の最大値を引いたものである。言い方を変えると、転移先の点数に-1をかけたもの（符号を変えたもの）が自分のスコアになるので、それに今取った数値を足すと、この状態での自分のスコアになる。これの最大化をはかるので、最大値を選べばいい。

dp[N-1][0]が、開始状態（ $N$ 個の数値が残っている状態）であり、先攻は必ず太郎君なので、この値が $X - Y$ となる。ちょっと騙された感じに聞こえるが、これで問題ない。

下三角行列の表現方法

dp[i][j]の添え字は $i \geq j$ を満たす必要があるので、下三角行列となる。上三角部分は使われないので勿体無い。上記のコードでは2次元行列を表現するため、ベクタのベクタを作成する時に必要な分だけを確保しようとしている。つまりdp[0]には長さ1のベクタが入ってるが、dp[n-1]には、長さ $n$ のベクタが入っている。

これで問題ないとは思うが、他の表現方法と比較をしてみたい。

富豪的表現手法

ケチケチせずに $N\times N$ の行列を用意してしまう方法。メモリはいっぱい使うと思うが、シンプルな書き方。

dqueue_2.rs

    let mut dp = vec![vec![0i64; n]; n];
    for i in 0..n {
        dp[i][i] = queue[i];
    }

1次元での表現手法

昔こんな風に実装していたなぁという記憶をたどりつつ実装した。1次元配列を用意して2次元空間をそこにマッピングする。各行の要素の数が差分1の等差数列なのでマッピングはすぐできる。

dqueue_3.rs

let pos = |i:usize, j:usize| { i * (i + 1) / 2 + j };
let mut dp = vec![0i64; pos(n, 0)];
for i in 0..n {
    dp[pos(i,i)] = queue[i];
}

パフォーマンス

処理時間の測定

$N$ を100から1000まで変化させた時の処理時間の測定結果。そんなに差があるわけではないが、富豪的表現（#2）が少し遅い。#1とそんなに差は無いんじゃないかと思っていたので意外ではある。ただ、ほぼ初期化処理の差なので、計算処理に差はないと思われる。1次元の表現方法では、マッピングの計算の分遅いかな？と思っていたが一番速かった。添え字のチェックなどはさぼっているので、そのせいもあるかも知れない。

メモリ量の測定

Heapメモリの量を見るためにdhatを使った。ドキュメントにあるようにすれば、profilerのライフタイム終了時にメモリの利用量がでてくる。

https://docs.rs/dhat/latest/dhat/

それぞれの方式での、 $N=1000$ の時のメモリ利用量は以下のようになる。予想通り富豪的にやるとメモリを倍使ってしまう。64bit(8bytes)の値を $1000\times 1000$ の行列として保持するので、8M bytes必要というのは計算通り。
古典的な1次元にマッピングするのが、速度/メモリ的に一番良さそうではあるが、読みやすさや汎用性から#1のアプローチも悪くないとは思う。

	memory	allocation
#1	4,057,366 bytes	1,011 blocks
#2	8,053,415 bytes	1,011 blocks
#3	4,033,408 bytes	11 blocks