はじめに
- 前回、定番の挿入dpの問題を解いたけど、今回は、そもそも挿入dpをやってみようと思った問題に取り組む。
- まぁ、挿入dpじゃなくても解けるみたいだけど、あえて、挿入dpでとくね。
問題
-
>か<のみを用いた長さN-1の文字列Sがあります。数列1...Nをうまいこと並び替えて、文字列Sの各文字を挟み込んで、大小関係「>」「<」が正しく成立する並び替えは何パターンあるか？ - 例えば、N=4、S=<><のとき、以下のとおり、5パターンの並び替えが出来ます。
[1,3,2,4]
[1,4,2,3]
[2,3,1,4]
[2,4,1,3]
[3,4,1,2]
解き方
- コレは、出来上がりの配列の各インデックスを並び替えていくことで解きます。
- と言っても、こんな言葉だけで理解できるわけないよね？具体的に説明します。
- 例えば、出来上がりの配列をAとします。各配列A[0]、A[1]、Ａ[2]､...のインデックスを⓪、①、②、...と考え、この⓪①②...を並び替えていくイメージです。
- あれ？余計に分からなくなった？ゴメンナサイ、ワザと情報を減らして、分かりづらく書いてました。
- 減らしてた情報は、「インデックス⓪①②...に入れる値の大小関係で並び替えを行う。」です。
- 普通は、配列の要素を並べていくのに、インデックスを並べていくのは面白いね。
- じゃあ、最初の例題S=<><を例に考えるよ。挿入dpとして、この⓪①②を順番に並べていこう。繰り返しになるけど、各インデックスに入れる値の大小で並べるよ。「値の小さい方を左側に置く」というルールにしよう。この⓪①②を入れていく配列をBとしておこう。
- 最初は当然[⓪]
- ①は、S[0]="<"より、⓪<①だから、[⓪①]しかないね。
- ②は、S[1]=">"より、①>②だから、[②⓪①]と[⓪②①]の2種類有るね。
- ③は、S[2]="<"より、②<③だから、[②⓪①]から派生して3種類、[⓪②①]から派生して2種類有るね -- (ここ重要！)
- だから、答えは5種類だね。
- この流れで、dpがイケそうな気がしてきた！
- ちなみにB=[②⓪①③]は答えの一つだけど、この時のAは[2 3 1 4]になるよ。これが分からない人は、次項に進んだら駄目だよ。場合の数を求めるだけだから、Aの実際の値を把握する必要はないんだけど、BとAの関係が分かってない人は、次項に進んでもさっぱり分からないと思うよ。
dpの設定
- dp[i][j]として、0...iまでの数列(0はインデックス⓪のことだよ)を並べて、最後に置いた「i」の位置が、左からj番目（0-indexed）とする。
- 例えば、[②⓪③①]も[⓪②③①]も、dp[3][2]で表現されます。
- ちなみに、なんで、dp[i][j]をこのように設定したかは分かるよね？
- 分からない人は、前項の (ここ重要！) をもう一度見てみて。
- 見て分からない人でも、次項のコードを見てくれれば分かるかな。
dpの遷移
dp[0][0]=1 // B[⓪]は1パターンしかないよね
for i in 1..<N {
for j in 0...i {
for t in 0...i {
if S[i-1]=="<" && j<t { // "<"のとき
dp[i][t] += dp[i-1][j]
}
if S[i-1]==">" && j>=t { // ">"のとき
dp[i][t] += dp[i-1][j]
}
}
}
}
for tt in 0..<i {
if S[i-1]=="<" && j>tt { // "<"のとき
dp[i][j] += dp[i-1][tt]
}
if S[i-1]==">" && j<=tt { // ">"のとき
dp[i][j] += dp[i-1][tt]
}
}
- 配る側と貰う側では、jとの大小関係が真逆だね。あと、ループ範囲が
0...jと0..<jの違いがあるのもポイントだね。 - で、実は上記のどちらで提出しても、TLEなんだよね。
- まぁ、配るdpのコードを見て分かるとおり、3重forループになってて$O(N^3)$になるからね。Nの制約は<3000だから、駄目だよね。
- なので、forループを一つ削ります。
貰うdpの高速化
- 貰うdpの方を見て貰うと、同じ作業を繰り返しているのが分かるかな？
- i=3で、
j in 0...3のループを"<"の時に限定してみてみよう- j=0のとき、dp[3][0] += 0
- j=1のとき、dp[3][1] += dp[2][0]
- j=2のとき、dp[3][2] += dp[2][0] + dp[2][1]
- j=3のとき、dp[3][3] += dp[2][0] + dp[2][1] + dp[2][2]
- だから、
for ttループって無駄な作業を繰り返してるって分かるよね。コレは削れる！ - で、こんなん出ました〜
for i in 1..<N {
if S[i-1]=="<"{ // "<"のとき
var sum = 0
for j in 1...i {
sum += dp[i-1][j-1]
dp[i][j] += sum
}
}
if S[i-1]==">"{ // ">"のとき
var sum = 0
for j in (0...i).reversed() {
sum += dp[i-1][j]
dp[i][j] += sum
}
}
}
- ">"の方は、
for jループをお尻(i)から始めているけど、やってることは分かるでしょ。
コード全体
- 条件に
mod 1000000007があるから、コレも追加しているよ。
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))
}
}
let N = Int(readLine()!)!
let S = Array(readLine()!)
let mod = 1000000007
var dp = [[Int]](N,N,0)
dp[0][0]=1 // B[⓪]は1パターンしかないよね
for i in 1..<N {
if S[i-1]=="<"{ // "<"のとき
var sum = 0
for j in 1...i {
sum += dp[i-1][j-1]
dp[i][j] += sum % mod
}
}
if S[i-1]==">"{ // ">"のとき
var sum = 0
for j in (0...i).reversed() {
sum += dp[i-1][j]
dp[i][j] += sum % mod
}
}
}
print(dp[N-1].reduce(0,+) % mod)
- 提出したら、100ms以下でACでした。
さいごに
- 挿入dpの2発目だけど、インデックスを挿入するなんて、ちょっとヒネり過ぎなのかな？
- でも、解いてみたら、ストンと理解できたね。
- 実際のコンテスト中に、forループを3重から2重にする高速化がスムーズに出来る気がしないけど...
- "<"の方の右辺がdp[i-1][j-1]で、">"ではdp[i-1][j]とか、頭が沸騰しそうです