Typical DP Contest I - イウィ

http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

問題概要

iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。

|S| <= 300

解法

区間DPをする。dp(l, r) = Sの連続部分文字列S[l..r]に対して行える最大操作回数とおく。

まず区間の長さが3以下の場合は自明で、その区間に対応する部分文字列がiwiなら1でそれ以外なら0である。これら初期値をもとに区間を伸ばしながらDPを更新していく。更新は以下の2パターンを考えるとわかりやすいかもしれない。

(1) 独立に消せる形

iwiiwiのような形の文字列は左右のiwiを独立に消せる。ゆえにdpの更新では左の区間と右の区間の値を単純に足せばいい。実装は区間内の区切り位置を全探索する形でやればok

(2) 連鎖が起きる形

iwiwiiのような文字列では真ん中のiwiを消すと外側のiw iがくっついてそれも消せるようになる。重要なのはこうした連鎖が必ず「中が全部消せる→外にiwiが残ったのでそれも消せる」という流れで起きることである。ここで中が全部消せるかどうかはそれまでのdpの値を見ればわかる（例えば長さの6の区間のdp値が2ならその区間は全消しできる）。ゆえに外側の長さが合計で3, 中の長さが区間の長さ-3になるような区切りを全部みてこういう形になっているかどうか判定すればよい。

以上でO(N³)で答えが出る。

感想

できてしまうとなんかそんなに難しく見えないんだけどやってる最中はすごく難しく感じたし結局解説を見た

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto dp = new int[][](N + 1, N + 1);

    foreach (len; 3..N+1) {
        foreach (l; 0..N-len+1) {
            int r = l + len;
            int nlen = len - 3;
            foreach (a; l..r)
                dp[l][r] = max(dp[l][r], dp[l][a] + dp[a][r]);
            foreach (a; l..l+len-nlen+1) {
                int b = a + nlen;
                if ((b - a) % 3 == 0 && dp[a][b] == (b - a) / 3)
                    dp[l][r] = max(dp[l][r], dp[a][b] + (S[l..a] ~ S[b..r] == "iwi"));
            }
        }
    }

    dp[0][N].writeln;
}