ドワンゴからの挑戦状 B - ニコニコレベル
問題
B: ニコニコレベル - 第3回 ドワンゴからの挑戦状 予選 | AtCoder
ニコニコ文字列とは、25 を 0 回以上繰り返した文字列のことをいいます。たとえば 25 や 252525 や空文字列はニコニコ文字列ですが、123 や 225 はニコニコ文字列ではありません。
ある文字列 S がその連続した部分文字列として含む最長のニコニコ文字列の長さを S の ニコニコレベル といいます。 たとえば 52525, 25025, 12151 のニコニコレベルはそれぞれ 4, 2, 0 です。
ニワンゴくんは 0 から 9 の数字と ? からなる文字列 T を持っており、それぞれの ? を好きな数字に置き換えることで、数字のみからなる文字列 T' を作ろうとしています。ニワンゴくんが作ることのできる文字列 T' のニコニコレベルの最大値を求めて下さい。
解法
問題の考察
一見以下のような貪欲法によって解けそう。
- 与えられた文字列を１文字ずつチェック
?の場合、１つ前が２であれば５に、１つ前が５であれば２に変換- ?が無くなった文字列からニコニコレベルを算出
しかし、与えられた文字列が「2???5????」の場合、上記の貪欲法では「252552525」となりニコニコレベルは４。しかし「225252525」とすれば、ニコニコレベルは８となりこれが最大になる。
そこで動的計画法による解答を試みる。
動的計画法を用いた解法
文字列を初めから順番にチェックしていき、i番目をチェックする時を考える。
i番目までのニコニコレベルは、i-1番目の状態に依存する。 例)
i番目が「２」の時 i-1番目が「５」 => i番目のニコニコレベル = i-1番目のニコニコレベル + 1 (25と続くので) i-1番目が「２」 => i番目のニコニコレベル = 0 (22と続くので)
このように、i番目のニコニコレベルはi-1番目の状態から算出することができる。
漸化式を考える。
dp[i][j]と置く。(0 <= i < N, j = 2 or 5)
dp[i][j] := i番目にjを置いた時のニコニコレベル
すると以下のような漸化式が立つ。
また、メモテーブルの埋まり方は以下のようになる。
このテーブルの中で最大値のものが答えとなる。
