第3回 ドワンゴからの挑戦状 予選-B：ニコニコレベル(300)

動的計画法

問題

https://beta.atcoder.jp/contests/dwacon2017-prelims/tasks/dwango2017qual_b

0から9と?で構成される文字列 s が与えられる。?を好きな数字に変えることで25の繰り返しのみで構成される s の部分文字列 s' の最大の長さを求めよ。

考え方

貪欲法ではうまくいなかい。つまり?の手前の文字が2であれば?を5に変え、5であれば?を2に変えるという方法である。サンプル4が反例になっている。

2???5????を貪欲法で変えると252552525となって25のみで構成される最大の部分文字列は2525となる。しかしうまくやると225252525とすることができ、この長さは 8 になる。

貪欲法ではうまくいかないことがわかった。(配る)DPを考える。

dp[i][j] := i 番目までの文字列で、今見ている文字が j (2を0、5を1に対応させておく)。

DPの遷移は以下となる。

(A)今見ている文字列が2の場合
 次の文字が5の場合は、今の2の長さ+1となる。
dp[i+1][0] = 0
dp[i+1][1] = dp[i][0] + 1

(B)今見ている文字列が5の場合
 dp[i+1][0] = dp[i][1] + 1
dp[i+1][1] = -1

(C)今見ている文字列が?の場合
 dp[i+1][0] = dp[i][1] + 1
dp[i+1][1] = dp[i][0] + 1

(D)今見ている文字列が上記以外の場合
 dp[i+1][0] = 0
dp[i+1][1] = -1

また、初期値としては以下となる。なお52となる場合はカウントできないため 5 -> 2 と遷移する場合を加味して dp[0][1] の初期値は -1 としておく。

dp[0][0] = 0
dp[0][1] = -1

求める解は dp[n+1][2] の配列中に存在する最大値である。奇数の場合は252のようになっているので直前の偶数値に切り捨てる。

       char[] s;
        long[][] memo;
        long max = -1;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            char[] s = in.nextString().toCharArray();
            int n = s.length;
            long[][] dp = new long[n+1][2];

            dp[0][0] = 0;
            dp[0][1] = -1;

            for (int i = 0; i < n; i++) {
                if (s[i] == '2') {
                    dp[i+1][0] = 0;
                    dp[i+1][1] = dp[i][0] + 1;
                    continue;
                }

                if (s[i] == '5') {
                    dp[i+1][0] = dp[i][1] + 1;
                    dp[i+1][1] = -1;
                    continue;
                }

                if (s[i] == '?') {
                    dp[i+1][0] = dp[i][1] + 1;
                    dp[i+1][1] = dp[i][0] + 1;
                    continue;
                }

                dp[i+1][0] = 0;
                dp[i+1][1] = -1;
            }

            long ans = 0;
            for (int i = 0; i < n+1; i++) {
                for (int j = 0; j < 2; j++) {
                    ans = max(ans, dp[i][j]);
                }
            }

            out.println(ans/2 * 2);
        }

ポイント

  • DP

類題

D - We Love ABC

雑記