Typical DP Contest I - イウィ

問題概要

i と w からなる文字列 $s (|s| \leq 300)$ から iwi を削除し残った文字列を連結する操作を繰り返す。

最大何回操作できるか答えよ。

解法概要

$\mathit{dp}_{i, j} := i$ 文字目 (ソースコードでは 0-indexed) から始まる j 文字の部分文字列に対して最大何回操作できるか

を求める。

$j \% 3 \neq 0$ について $\mathit{dp}_{i, j}$ を求めようとするとややこしいので，$j \% 3 = 0$ についてのみ考え，全体での操作回数は$j \% 3 = 0$ についての場合からうまいこと計算する。

消せるパターンを考えてみると，

iwi そのもの
(消える文字列)(消える文字列)
i(消える文字列)wi
iw(消える文字列)i
i(消える文字列)w(消える文字列)i

がある。iwiは，それぞれの文字の間に0文字の文字列があると考えると一番最後のパターンになるので，全部で 4 パターンということになる。これを短い部分文字列から順に計算していく。ここでは，長さが3の倍数の文字列だけ考えれば良い。また，1回の操作で3文字消えることを考えると，(消える文字列) は $\mathit{dp}_{i, j} = \frac{j}{3}$ であるような文字列である。遷移の詳細はソースコードを見た方が早い。

上記の計算では，完全に消せる部分文字列については正しい操作回数が求められるが全体の最大操作回数が求まっているとは限らない。そのため，最後に別の DP で全体の最大操作回数を求める必要がある。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();

    vector<vector<int>> dp(n, vector<int>(n+1, 0));
    for(int j=3;j<=n;j+=3) {
        for(int i=0;i+j<=n;++i) {
            // (消せる)(消せる) の形
            for(int k=i+1;k<i+j;++k) {
                if(dp[i][k-i] * 3 == k-i && dp[k][i+j-k] * 3 == i+j-k) {
                    dp[i][j] = max(dp[i][j], dp[i][k-i] + dp[k][i+j-k]);
                }
            }
            // i(消せる)wi の形
            if((s[i] == 'i') && (dp[i+1][j-3] * 3 == j-3) && (s[i+j-2] == 'w') && (s[i+j-1] == 'i')) {
                dp[i][j] = max(dp[i][j], dp[i+1][j-3]+1);
            }
            // iw(消せる)i の形
            if((s[i] == 'i') && (s[i+1] == 'w') && (dp[i+2][j-3] * 3 == j-3) && (s[i+j-1] == 'i')) {
                dp[i][j] = max(dp[i][j], dp[i+2][j-3]+1);
            }
            // i(消せる)w(消せる)i の形
            for(int j1=0;j1<=j-3;j1+=3) {
                int j2 = j-3-j1;
                if((s[i] == 'i') && (dp[i+1][j1] * 3 == j1) && (s[i+j1+1] == 'w') && (dp[i+j1+2][j2] * 3 == j2) && (s[i+j-1] == 'i')) {
                    dp[i][j] = max(dp[i][j], dp[i+1][j1] + dp[i+j1+2][j2]);
                }
            }
        }
    }

    vector<int> cnt(n+1, 0);
    for(int i=0;i<n;++i) {
        for(int j=0;i+j<=n;++j) {
            cnt[i+j] = max(cnt[i+j], cnt[i] + dp[i][j]);
        }
        cnt[i+1] = max(cnt[i+1], cnt[i]);
    }

    cout << cnt[n] << endl;
}

所感

解いてるときは四苦八苦したのに終わってみると簡単に見えてしまう