教育的なdp問題【競技プログラミング】

はじめに

• 典型的なdp問題を解いて、dpの感覚を掴もうと思う。

問題

• 典型９０問の008からです。
• ある文字列Sから、順番を保ったまま7文字を抜き出して、T = "atcoder"を作る方法は何通りあるか？
  • 例は以下のとおり。
  • S = "atcoder" からは、１とおり。
  • S = "atcodre" からは、０とおり。
  • S = "atcoderatcoder" からは、8とおり。
  • S = "aattccooddeerr" からは、128とおり。$(=2^7)$

dpの方針

• 基本形は、dp[i][??] (??は何かの状態を表す指標)になる。
• 今回においては、iは当然、文字列Sの何文字目まで進んだかを意味して、dp[N][??]が最終的な答えになるようなイメージかな。
• 具体的に考えれば、dp[i][j](i in 0..<N , j in 0..<7)として、これを、Sの「i-1」文字目まで取捨選択終わった時点で、Tの「j-1」文字目までを選択し終えているときの、場合の数とする。
• つまり、dp[i][j]の数値が算出済みである状態で、S[i]、T[j]の文字に着目している場面、と言うこと。
• この方針に沿ってコードを書くと以下のとおり。

extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

// dp準備
var dp = [[Int]](N+1,T.count+1,0) // 省略記法でのイニシャライザ。要素数 N+1 がキモだね。

// 初期化
dp[0][0] = 1

// 遷移
for i in 0..<N {
    for j in 0...T.count{

        // Sの文字列を進むとき、Tの文字列T[j]をS[i]から選ばない決定をした場合の遷移
        dp[i+1][j] += dp[i][j] // iのみ遷移

        // Sの文字列を進むとき、Tの文字列を選ぶときの遷移
        if j<T.count && S[i] == T[j] {
            dp[i+1][j+1] += dp[i][j] // iもjも遷移
        }
    }
}

• 上記dpを使った本問の答えは、当然dp[N][7]となる。
• 本問の制約は、$N≦10^5$だから、上記の計算量O(7･N)だと余裕です。30ms未満でACでした。

おわりに

• まだ、この手の問題で､解法がパッと思いつかない。dpについては、数をこなすしかないのかな。