DPって何？【競技プログラミング】

はじめに

• 競技プログラミングを始めて2回目くらいの参加の後、解説動画を見てたら、いきなり当然のように「ディーピーを使うとこんな感じですね〜」とホワイトボードに「dp[??][??]=???」のような説明を始めたけど、全く頭に入ってこなかった。
• まず、dpの意味が分からんかった。wikiで調べて、動的計画法(Dynamic Programming)なのねぇ、と知ったよ。
• 一度、ナップサック問題を解くときに学習したけど、そんな特殊な単品だけ覚えても、応用きかない。
• いちおう、wikiにのってたフィボナッチ数列での例もswiftで書いてみたけど、ナップサック問題もフィボナッチ数列の例も、「同じ計算を繰り返さないで省略する」という形のものだけど、dpって漸化式的な利用の方もあるのでは？と思ったので、整理することとした。

「同じ計算を繰り返さない」（実行済み計算をメモライズ）的な意味のdp

• 以前書いたコードで言えば、フィボナッチ数列の算出がある。以前は、メモライズするするデータを、記憶したかどうかのみを格納するmemsと、記憶したデータを格納したfibsの二つの配列に分けていたけど、何か格好悪いから、一本化するね。これをdpとします。

//　最初にMAX個の箱を用意しておく
let MAX:Int = 93
// var mems = [Bool](repeating: false, count: MAX)
// var fibs = [Int](repeating: 0, count: MAX)
var dp = [Int?](repeating:nil,count:MAX)


// フィボナッチ数列の最初の2項を格納しておく
(dp[0],dp[1]) = (0,1)

//過去に算出済みの場合は計算をサボる
func fib(_ n:Int)->Int{
    var fb:Int = 0
    if(dp[n] == nil) { // 一度計算したら、サボってOK!
        fb = fib(n-1) + fib(n-2)
        dp[n] = fb // -- メモライズ！！！
    } else {
        fb = dp[n]!
    }
    return fb
}

// 計算
print(MAX-1,fib(MAX-1)) // 92 7540113804746346429(7.5e18)

• memsとfibsを使った元のコードは下記の通りだけど、もし、上記のメモライズをしないと、計算量が爆発的に増えて、MAX=40だとpaiza.ioではtimeoutとなる。timeout回避のためMAX=37とし、また、計算回数をカウントする変数cntを導入して計算すると、計算後のcntは24157816となる。メモライズを封印しない場合は、cntは35となる。

//　最初にMAX個の箱を用意しておく
let MAX:Int = 37
var mems = [Bool](repeating: false, count: MAX)
var fibs = [Int](repeating: 0, count: MAX)

// フィボナッチ数列の最初の2項を格納しておく
(fibs[0],fibs[1]) = (0,1)
(mems[0],mems[1]) = (true,true)

var cnt = 0 

// 過去に算出済みの場合は計算をサボる
func fib(_ n:Int)->Int{
    var fb:Int = 0
    if(!mems[n]) {
        fb = fib(n-1) + fib(n-2)
        fibs[n] = fb
        cnt += 1
        // mems[n] = true -- メモライズ封印！！！
    } else {
        fb = fibs[n]
    }
    return fb
}

// 計算
print(MAX-1,fib(MAX-1)) // 36 14930352
print(cnt) // 24157816

• 上記のとおり、メモライズによる計算量削減効果は凄いけど、凄いんだけど...これ、「動的計画法」って言葉とマッチしないよね？計画って感じがしないぜ！

「漸化式を利用する感じ」のdp

• 最近投稿したダブリングで使ったアルゴリズムで下記のように漸化式をつかっている。なお、元記事ではmemsとなっていた配列名はdpに変えたよ。

import Foundation

let (n,k) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)! - 1} //配列のindexに合わせるため-1している。

let lgk = Int(log(Float(k)) / log(Float(2))) + 1 //kの対数は2を底としたときlg(k)で表記されるため

// dpの準備
var dp = [[Int]](repeating:[Int](repeating:-1,count:n),count:lgk)

// 一周目(初期化)
for i in 0..<n {
    dp[0][i] = vs[i]
}

// 二周目以降(遷移)
for j in 1..<lgk {
    for i in 0..<n {
        dp[j][i] = dp[ j-1 ][ dp[j-1][i] ] // -- ※
    }
}

var ans = 0 // 開始位置は0
var j = 0
var temp = k
while temp > 0 {
    if temp & 1 == 1 {ans = dp[j][ans]}
    temp >>= 1
    j += 1
}

print(ans + 1) // 出力用に+1とした。-- 下記入力に対して「2」を出力

///入力
6 727202214173249351 // n=6、k=727202214173249351
6 5 2 5 3 2 // 最小値を1とする前提だから、取り込むときは-1として配列のindexにあわせ、あとで出力するとき+1する。

• 上記コードの意味自体は、過去の投稿を見てね。
• ※印の部分で漸化式となっているので、forループで解ける。
• 漸化式を使うdpは動的計画法って言葉にあってる気がするね。でも、何が「動的」なのかよく分かってないけど。もちろん、英語のdynamicを単純に訳しただけなんだろうけど、対義語で静的計画法があるんだろうか？
• ハノイの塔も、漸化式が作れるから、dpでとけるね。で、ハノイの塔の漸化式の説明をしようと思って、適当な図をネットから拝借しようと思ったけど見つからんかったよ。ドユコト？高校の数学教師はどうやって教えてんの？
• しょうがないから、自分で図を作ったよ。
  
• ハノイの塔のルールは知ってるよね？知らない人は、wikiを見てね。簡単に説明すると、
  • 最初の状態で棒に刺さったn枚の円盤があって、円盤は下層ほど広く、上層ほど狭い。他に円盤が刺さってない棒が２本ある。
  • 各円盤は１枚ずつ円盤から抜いて他の棒に刺さることが出来るけど、自分より狭い円盤の上に乗せてはいけない。
• 上記条件で、左の棒に刺さったn枚の円盤を何回の移動作業で右の棒に全部差し替えられるか？というのがハノイの塔の問題
• で、円盤がn枚の時の解をdp(n)回とすると、上記の図で分かるとおり、下記のように書ける。
  • $dp(n) = ②n-1枚の円盤の山の移動回数 + ③n枚目の円盤の移動回数 + ④n-1枚の円盤の山の移動回数$
    = $②dp(n-1) + ③ 1 + ④dp(n-1)$
    = $2×dp(n-1) + 1$
• ここで、n=1のときは漸化式の答えが無いので、自分で考えると、答えは1だね。
• n=2のときは、漸化式を使うと3になる。頭の中で円盤を移動させても3だね。まあ、上の図で②③④を1回ずつするので3で当然。
• さて、漸化式が出来たから、コードに落とすと

let n = 10

var dp = [Int](repeating:-1,count:n)

// 初期化 円盤1枚の答えをインデックス0に格納
dp[0] = 1

// 遷移
for i in 1..<n {
    dp[i] = 2 * dp[i-1] + 1
}

print(dp[n-1]) // 円盤n枚の答えがインデックスn-1に格納されている。 -- 1023 (n=10)

中間まとめ

• 「同じ計算を繰り返さない」的なdpと、「漸化式を利用する感じ」のdpは、両方とも動的計画法って呼ばれるけど、共通するのは「部分問題」を「メモライズ」するということ。
• 「同じ計算を繰り返さない」的なdpでは、「一度解いた計算」をメモライズし、「漸化式を利用する感じ」のdpでは、「漸化式の一つ前の答え」をメモライズした。
• うむ、動的計画法って名称との違和感は全く消えないけど、dpとは、「部分問題のメモライズ」と理解すればよいのね。
• そして、メモライズのための配列を最初に作っておく必要がある、と。
• 実はハノイの塔は事前に配列を用意しないアルゴリズムを書けるけどね。実際の競技プログラミングのコンテストで解き方を迷わないように、原則的に答えの書き方は一定のフォーマットに沿った方が良いよね。もちろん、計算量がシビアなら、最初に配列を用意しないアルゴリズムの方が高速かも知れんけどね。
• ちなみに、最初に配列を用意しないコードでハノイの塔の解を求めると、次のように書ける。

let n = 10

// 初期化 円盤1枚の答えを変数memに格納
var mem = 1

// 遷移
for _ in 1..<n {
    mem = 2 * mem + 1
}

print(mem) // 1023

• 上記だと、変数memがどんどん上書きされ、メモライズとは言えんからdpじゃないね。まぁ、ハノイの塔レベルの単純な漸化式からなら、上記のコードで十分かな。ダブリングの方は、dpじゃないと厳しいけどね。

少し難しい問題

• AtCoderのABC195のe問題は、dpを使わないと解けない問題で、問題を見ただけでは、そもそも解けるかどうかも分からない上級者向け問題。
  
• どうよこれ。「DPって何？」と思っちゃうような僕と同レベルの同志諸君には解ける気しないでしょ？
• でも、それじゃ悲しいから、ちゃんと考えてみよう。DPを使えば解けると分かっているんだから、考えれば解けるはず。
• dpを使うときのキモは、当然、「何をメモライズするか？」になる。
• 前述のダブリングを振り返ってみると、dp[j][i]をメモライズの配列としていたけど、iが移動前の場所、jを移動回数として、dpを移動先の場所としていた。そして初期化(一周目)と遷移(2周目以降)のforループの形は次のとおり。内側のiのforループで場所iについて「$2^{j-1}$回移動後の場所dp[j-1][i]から更に$2^{j-1}$回移動後の場所」を「場所iから$2^j$回移動後の場所」として記憶している。

// 一周目
for i in 0..<n {
    dp[0][i] = vs[i]
}

// 二周目以降
for j in 1..<lgk {
    for i in 0..<n {
        dp[j][i] = dp[ j-1 ][ dp[j-1][i] ] // -- ※
    }
}

• ABC195のe問題についてdp[j][i]を考えると、dpを高橋君の勝利判定(true:勝ち/false:負け)として、jはラウンド数（配列を使うので、問題文上の第1ラウンドは第0インデックスラウンドとなる。以降の説明は、インデックスラウンドでの説明とする）とするのが良さげ。じゃあ、iはどうすれば良いんだろう？jラウンド開始時の「何かの状態」としなきゃいけないのは分かるけど･･･
• そもそも、勝利条件は何だったろうか？「7で割り切れるかどうか？」が勝利条件だったので、jラウンド目開始時に対戦相手または自分(以下「プレーヤー」または「jラウンドプレーヤー」と呼ぶ)に渡す数値の状態とするのが妥当だよね。
• 数値の状態として、最低限の情報は、7で割り切れるかどうかに繋がる情報として、(mod7)で表現する数字とするのが妥当だろう。全ての数字は7つの状態のみに区分される。
• 上記より、dp[j][i]は、jラウンド開始時(=j-1ラウンド終了後)にプレイヤーにi(mod7)を渡す(j-1ランド終了時の数値がiである)場合に、高橋君が勝利するかどうか(true/false)をメモライズする配列となる。
• あとは、dpの初期化と遷移の式を考える必要があるけど、プレイヤーが高橋君と青木君の2人いるので、各プレーヤーに応じてdpの遷移の式を書き分ける必要がある。
• そもそも、初期化の式を考えないといけないけど、これは、勝利条件はラウンドN-1(インデックス表示)後に確定するものであり、確実に言えるのはdp[N][0]=true、dp[N][0以外]=false。なお、dp[N][0]とは、N-1ラウンド終了後にプレイヤーに渡す値が7で割り切れる数字であると言うことなので、当然、trueとなる。
• ここから分かるのは、forループの外側と、プレイヤー毎に分かれたif文は以下のような形になるということ。

//dpの準備
var dp = [[Bool]](repeating:[Bool](repeating:false,count:7),count:N+1)

//初期化
dp[N][0] = true

//遷移
for j in (0..<N).reverse {

    dp[j][?] = dp[j+1][??] ....... // ※遷移の式

}

• さて、お次は遷移の式をどのように書くかだけど、ラウンドjでプレーヤーに渡す時の数値がnum(mod7)のとき、ラウンドjでプレーヤーが数値kを選択したとき、ラウンドj+1で次のプレーヤに渡される数値は、当然「$(10×num+k)\%7$」となる。ちなみにkの選択肢は、「Sj」(j in 0..<N)か「0」の二択
• ただし、どちらをkを渡すかは、プレーヤーが高橋君か青木君かで戦略が変わってくる。
• 7の倍数にしたい高橋君の場合、dp[N][0]=true,dp[N][1]=false,...,dp[N][6]=falseがスタートとなるが、i(mod7)の遷移について着目すると、ラウンドjでの高橋君の戦略による勝利(true)の伝播はこのようになる
  • ラウンドjのプレーヤーが高橋君の場合(高橋君はSjか0を選べる)
    • dp[j][i] = dp[j+1][(10 * i + Sj) % 7] || dp[j+1][(10 * i + 0) % 7]
  • ラウンドjのプレーヤーが青木君の場合(青木君は邪魔をしたいが、Sjと0が合同(mod7)で、dp[j][(10 * i + Sj) % 7]もdp[j][(10 * i + 0) % 7]もtrueの時は邪魔できない)
    • dp[j][i] = dp[j+1][(10 * i + Sj) % 7] && dp[j+1][(10 * i + 0) % 7]
• 上記を元に、遷移の式をコードにすると、

//整数入力
let N = Int(readLine()!)!

//n桁数値から各桁数値配列化 
let S = Array(readLine()!).map{Int(String($0))!}

//文字列から各文字配列化 
let X = Array(readLine()!) // 要素はCharacter型

//dpの準備
var dp = [[Bool]](repeating:[Bool](repeating:false,count:7),count:N+1)

//初期化
dp[N][0] = true

// 遷移
for j in (0..<N).reversed() {
    for i in 0..<7 { 
        if X[j] == "T" {
            dp[j][i] = dp[j+1][(10*i + S[j]) % 7] || dp[j+1][10*i % 7] // 高橋君の場合
        } else {
            dp[j][i] = dp[j+1][(10*i + S[j]) % 7] && dp[j+1][10*i % 7] // 青木君の場合
        }
    }
}

//開始時点のdp[0][0]まで、高橋君の勝利(true)が伝播しているか確認
print(dp[0][0] ? "Takahashi" : "Aoki" )

• 提出したら、ACで30ms程度でいけた。正直言って、途中から解説を見ながら、解いたから、自力で解いたとは言えないのよね。難しすぎ。こういう問題を『桁DP』と読んで、一つのジャンルを築いてるっぽいね。

おわりに

• うーむ、dpについては、もう少し修行が必要だなぁ。
• 自力でABC195のe問題のdp設定が思いつけるようになるまで、道は遠そうです。

追記

• AtCoderで、dpのみを集めたコンテストがあるのを見つけた！

• 次は、これにチャレンジだね