🔖

ABC240 C - Jumping Takahashiのメモ

2022/11/11に公開

AtCoder

競プロ

動的計画法

tech

DP入門的な問題として教えてもらって解きました。

簡単な経過

最初にこの問題を見たときは全然わからず、解説を見てもわからず、解説ACする気にもなれませんでした。
ショックだったのでアルゴ式で一からDPについて勉強していき、そろそろ解けるかなーと思って再挑戦し、めでたく解くことができたということになります。

アルゴ式で勉強していた時のあれこれも記録しようかと思ったのですが、なんかもうあまり覚えていなかったのでとりあえずこの問題についてだけ書いておきますｗ

考察と実装

実はアルゴ式でだいたい同じような問題を解いた後に解いたので、ほとんど苦労せずに解けました。

まあ考察というか、一種のパターンがあるのでそれを覚えていて、当てはめて解くことができたという感じなのですが。

DPでは問題を分割して考えます。最終的に欲しい答えは座標Xに到達可能かどうかですが、まずはその途中の場所に到達可能かどうかを一つ一つ見ていきます。到達というか、ジャンプ後にその場に存在することができるかどうかと言ったほうがいいでしょうか。
知りたいのは「存在できるかどうか」なので、booleanで保持すればいいです。添字を座標に見立てた配列を定義し、それぞれの場所に存在できるかどうかを記録します。その場に存在するかどうかをジャンプごとに記録したいため、二次元配列となります。

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

    // その場所に存在することができるかどうかのフラグを情報として持つDP表
    // 配るためN+1
    // Xを超える場合は確実にNoなのでそれ以上は見なくていい（1-indexedにするためX+1）
    val dp = List(n+1) { BooleanArray(x+1) }
    // 初期位置
    dp[0][0] = true

    // i+1にアクセスするためNまでは見てはいけない（N+1の配列なので末尾の添字はN）
    for(i in 0 until n) {
        // ジャンプしないということはできないためXまでは見なくていい
        for(j in 0 until x) {
            // 存在することができない場所ならスキップ
            if(!dp[i][j]) {
                continue
            }

            val a = ab[i][0]
            val b = ab[i][1]

            // 範囲外を参照しないようにする。X+1の配列なのでXまでは範囲内
            if(j + a<= x) {
                dp[i+1][j + a] = true
            }
            if(j + b <= x) {
                dp[i+1][j + b] = true
            }
        }
    }
    if(dp[n][x]) {
        println("Yes")
    } else {
        println("No")
    }
}

やることとしては、二次元表を全て走査して、trueだった場合は次のジャンプで到達できる位置（A分進んだ場所とB分進んだ場所）をtrueにします。最初（あえて言えば0回ジャンプした後）は座標0にいますので、dp[0][0]をtrueで初期化します。

配列の大きさについてです。二次元配列なので縦と横で考えられますが、横から考えると、X+1でいいです。後ろにジャンプすることはないため、ひとたびXを超えたら確実に答えはNoとなりますので、無視していいです。なので、添字の最大値がXとなるサイズにします。最初は座標0にいますので、0がある分で+1になります。

縦は、N+1になります。縦はジャンプの回数ですが、初期状態として0回ジャンプした時の値も保持するので、0回目の分で+1になります。

あとは範囲外を参照しないように考慮して実装すればOKです。

最初は0にいるのでそこだけがtrue、1回目のジャンプの後はAまたはBにいるはずなのでそれらがtrueに、2回目は最初のAから見て今回のAまたはB分進んだ位置と、最初のBから見て今回のAまたはB分進んだ位置ののべ4箇所に存在できるのでそれらを全てtrueにします。同じ位置に到達する可能性もあるので実際に4箇所がtrueになるとは限りませんが、それは特に気にする必要はありません。
そんな感じでジャンプのたびにtrueとなる箇所が増えていきます。最終的にN回のジャンプの後に到達する可能性がある場所が全てtrueになります。その中で、Xの位置がtrueならYes、falseならNoになるというわけです。

感想

二次元DPの問題としてはかなり簡単な部類なのだろうと思いますが、最初は全然わからなかったので解けてよかったです。最初はなぜ二次元になるのかわからなかったし、なぜAとかBを添字に足すのかもわかりませんでした。
前提知識（というか考え方）を知らなかったので、わかるはずもなかったという感じです。わからない場合は、最初からやればいいんですね。

DPを最初からやる教材として、アルゴ式はなかなか良かったです。最初は2問目の問題の時点で躓いたので大変でしたし、脳が悲鳴を上げましたが、最終的には理解できてアハ体験が得られました。

みんなアルゴ式やろう！
https://algo-method.com/courses/7

簡単な経過

考察と実装

感想

Discussion