TDPC: I – イウィ 解説

これ自力で解けませんでした.TDPC は EDPC よりかなり難しいですね...

既に多くの解説記事がありますが,理解に時間がかかったので,自分が自然だと思う思考回路を書いておきます.

問題ページ: Typical DP Contest: I - イウィ

考察過程

  • DP を「場合分け全探索の高速化」と考える.適切に場合分けして最大値を求めたい.
  • まず思いつくのは,最初にどの iwi を消すかでの場合分け.しかしこれだと上手くいかなそう.例えば iwiwii (サンプル $1$ の入力)から iwi を消した後,iwi が残るが,この $2$ つを合体すればもう $1$ 回 iwi が消せることを考慮するのが難しいため.
  • では,最後にどの iwi を消すかで場合分けするとどうだろう? → 一捻りすると上手く部分問題に帰着できる!

部分問題への帰着

与えられた文字列 $s$ の中に(連続とは限らない)部分列として現れる iwi を固定し,これを最後に消す場合について考えます.

最後に消す iwi のみ明示的に書くと,$s$ は A i B w C i D という形をしています(ABCD は長さ $0$ 以上の文字列).

このとき,$2$ つの部分文字列 $S_1=$A,$S_2=$i B w C i D に対して独立に操作をすることになります.$S_2$ の先頭の i を最後に消すという制約があるためです.

ここで,A空文字列でない場合は,文字列 $s$ を $s = T_1 + T_2$ と $2$ つの非空部分文字列に分割し,(固定した iwi を最後に消すという条件を忘れて)$T_1, T_2$ に対して独立に操作をする場合に含まれることに気づきます.数え上げの問題ではないので,排反に分けなくてもいいことに注意してください.D が非空の場合も同様です.

以上で,AD の少なくとも一方が非空の場合は,サイズの小さい部分問題 $2$ つに帰着できることが分かりました.

次に AD がともに空である場合を考えましょう.つまり $s = $ i B w C i です.

iwi を最後に消すという条件から,BC はそれぞれ単体で完全に消せる必要があります.それが可能かどうかは,やはりサイズの小さい部分問題を解くことで分かり,そのときの操作回数も文字列長から簡単に分かります.

DP テーブルの定義と計算

与えられる文字列 $s$ の長さを $N$ とし,$s$ の $i$ 文字目 $(0 \leq i < N)$ を $s_i$ と書きます.

上で現れた部分問題の形を見ると,$0 \leq l \leq r \leq N$ なる整数 $l, r$ に対し,$\red{\texttt{dp}(l, r)} :=$「部分文字列 $s_l s_{l+1}\cdots s_{r-1}$ に対する操作回数の最大値」と定めるのが良さそうです.問題の答えは $\texttt{dp}(0, N)$ です.

上の考察に基づくと,$\texttt{dp}(l, r)$ は以下のように $r-l$ が小さい順に計算できます.まず,$\texttt{dp}(l, r) \gets 0$ と初期化しておきます.

AD の少なくとも一方が非空の場合

上の考察中の文字列 AD の少なくとも一方が空でない場合は,$i = l+1,l+2\dots,r-1$ に対し,\[ \texttt{dp}(l, r) \gets \max \{ \texttt{dp}(l, r),\ \red{\texttt{dp}(l, i) + \texttt{dp}(i, r)} \} \] と更新することで網羅できます.

AD がともに空の場合

このような場合が発生するためには,$s_l = s_{r-1} = $ i である必要があります.その上で,ある $i = l+1,l+2\dots,r-2$ に対し,$3$ つの条件

  • $s_i = $ w
  • $3\, \texttt{dp}(l+1, i) = l-i-1$(文字列 B が完全に消せる)
  • $3\, \texttt{dp}(i+1, r-1) = r-i-2$(文字列 C が完全に消せる)

を満たすならば \[ \texttt{dp}(l, r) \gets \max \Big\{ \texttt{dp}(l, r),\ \red{\frac{r-l}{3}} \Big\} \] と更新すれば OK です.

AC コード

メモ化再帰で実装しています.計算量は $O(N^3)$ です.

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T &a, const T b) { if (a < b) { a = b; return true; } return false; }

string s;
vector<vector<int>> memo;

int dp(int l, int r) {
  if (memo[l][r] >= 0) return memo[l][r];
  if (l == r) return memo[l][r] = 0;

  int res = 0;
  for (int i = l+1; i < r; ++i) chmax(res, dp(l, i) + dp(i, r));
  
  if (s[l] == 'i' && s[r-1] == 'i') {
    for (int i = l+1; i < r-1; ++i) {
      if (s[i] == 'w' && dp(l+1, i) == i-l-1 && dp(i+1, r-1) == r-i-2) chmax(res, r-l);
    }
  }
  return memo[l][r] = res;
}

int main() {
  cin >> s;
  int n = size(s);
  memo.assign(n+1, vector<int>(n+1, -1));

  int ans = dp(0, n) / 3;
  cout << ans << '\n';
}

教訓

  • 「場合分け全探索」を考えると,DP テーブルと遷移式が自然に生える
  • 前から見て上手くいかないときは後ろから見る(最後に消す iwi に注目)
  • 数え上げではないときは,必ずしも排反に場合分けする必要はない.そうすることで計算量が削減できることもある(排反に分けるために「最後に消す iwi を全通り試す」と考えると,計算量が大変なことになる)

追記: 非 DP $O(N)$ 解法

この記事の公開後に教えてもらいましたが,なんとこの問題は DP を使わずに $O(N)$ で解けます.すごい!

証明は Y.Y. さんのツイートへのリプライをご覧ください.

タイトルとURLをコピーしました