👌

SESNIC C - Syntax Sugarのメモ

2022/11/15に公開

競プロ

動的計画法

tech

お勧めされたので解いてみました。AtCoderではなく有志コンテストの問題です。

考察

いくつ選ぶとかは決まっておらず、正答を得るためにいくつ選ぶことになるのか不明なので、一つの解法としてはbit全探索が考えられます。ただ全パターン試すとなると、Xを超えたらそれ以上選ばないとかの考慮なしだとすると $O(2^N)$ になります。Nは最大1000なのでダメそうです。
こういう場合はDPです。やはりDP‥‥!! DPは全てを解決する‥‥!!

前回DPを使う問題を解いていますが、大枠はこれとそんなに変わりません。

これを書いている時点ではまだ解説を読んでいないので最適なやり方ではない可能性がありますが、とりあえず自分が実装した方法を書いていきます。

DPテーブルは二次元配列になります。砂糖の種類が行、食べた砂糖の重さの合計が列、その重さになる場合に必要な最低金額が値の表形式のデータとなります。

基本的には「もらう」DPの発想で考えています。二次元表を走査して表を埋めていくわけですが、前回のJumping Takahashiの問題と同様に考えると、その時点で注目している重さに到達するためには、注目している砂糖の重さを引いた分の重さに既に到達している必要があります。そのため表の埋め方の基本としては、注目している砂糖の一つ前の砂糖を食べた時に到達する可能性のある重さに、今回注目している砂糖の重さを足した重さのところに値を入れればいいということになります。
今はもらうDPで考えているため、実装としては逆に今回注目している砂糖の重さを引いた重さのところに値があったら、注目している位置に値を設定します。引いた位置の値が0ならスルーします。

Jumping Takahashiと違うのは、複数のパターンで同じ重さに到達した場合の考慮です。Jumping Takahashiではbooleanで管理していたので、かち合っても同じ値なので特に気にしなくてよかったのですが、今回の問題では数値を管理するので別の値になることがほとんどです。
この場合はどうすればいいかというと、今回は最小金額を求めたいので、小さいほうの数値を採用して大きいほうは捨ててしまって問題ないです。
~~最初はなぜか足してしまう実装をしてバグらせてました~~

あと、これだけだともらう元が今回の行に引き継がれていないので、もらうついでに引き継ぐ実装もします。

これで実装できるかというとまだダメです。これだけだと、初めて食べる砂糖が今回注目している砂糖だった場合の考慮が抜けています。なので、その行を処理する際の最初の処理としてそこを埋めてしまいます。

これでもまだ足りません。一度埋まった重さは次の行にも引き継がないといけません。なのでその実装も入れます。

ここまで来れば表が埋まります。あとは、最終行のX以上の重さの中での最小値を求めればそれが答えです。（初期値の0は除外して考えます）
砂糖の重さはXちょうどでなくてもよくて、超えている分にはいくらでもいいので、最小値を探索する必要があります。これは線形探索で問題ありません。
なお、全ての砂糖を食べてもXに到達しない場合もあります。その場合はここで答えが見つからないことになります。これが-1を出力するケースに該当します。

実装

import kotlin.math.min

fun main() {
    val (n, x) = readLine()!!.split(" ").map { it.toInt() }
    val mv = List(n) {
        readLine()!!.split(" ").map { it.toInt() }
    }

    // 縦が種類、横が重さの合計、値が価格（横の長さは適当）
    val width = 10000
    val dp = List(n) { IntArray(width) }
    // 起点として一つ目の砂糖の値で初期化
    dp[0][mv[0][0]] = mv[0][1]

    // もらう元がない0番目は見ない
    for(i in 1 until n) {
        val (m, v) = mv[i]

        // 最初に食べる砂糖が今回の砂糖だった場合のために埋める
        dp[i][m] = v
        for(j in 0 until width) {
            // 基本は、価格が0じゃないものがあったらそこから貰う
            if(j >= m && dp[i-1][j-m] != 0) {
                // この時点だともらう元が今回の行に引き継がれていないので引き継ぐ
                // 既に他からもらって埋まっている場合も考慮して小さい方を採用する
                if(dp[i][j-m] == 0) {
                    dp[i][j-m] = dp[i-1][j-m]
                } else {
                    dp[i][j-m] = min(dp[i][j-m], dp[i-1][j-m])
                }

                // 今回の砂糖を食べることによって到達する重さの分を埋める
                // ただし既に埋まっていて、埋まっている値のほうが小さいなら上書きしない
                if(dp[i][j] == 0) {
                    dp[i][j] = dp[i-1][j-m] + v
                } else {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-m] + v)
                }

                // 今回埋めた値を引き継ぐ
                if(i != n - 1) {
                    dp[i+1][j-m] = dp[i][j-m]
                    dp[i+1][j] = dp[i][j]
                }
            }
        }
    }

    // X以上の重さの中で最小値を探索する
    val list = dp[n-1].toList().subList(x, width).filter { it != 0 }
    println(list.minOrNull() ?: -1)
}

DPテーブルの横の長さは、重さを足していっても超えない、かつ現実的な実行時間で処理できる必要があります。本当はちゃんと計算して求めるべきなのですが、これは適当に選んでしまっています…
行数はNです。起点を一つ目の砂糖を食べた場合の値にしているので、+1にはなりません。
0行目は初期化の際に埋めているのでループでは見なくていいです。
列を走査する際、配列の範囲外を参照しないようにチェックが必要です。行については1つ前を参照しますが、1から始めているので範囲外を参照するおそれはありません。

解説を読んで

読んで、と言いつつちょっと時間がなくてちゃんと読み解けてないのですが、だいぶ違う考え方で解いているというのはわかりました。まあ0で初期化するよりも大きな値で初期化するほうがたしかに良いですね。まあ詳細な理解についてはまた今度…
だいぶ違うことやってたとしても、解けたので嬉しいです。

考察

実装

解説を読んで

Discussion