Typical DP Contest：I - イウィ

問題

https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi

制約

  • |S| \le 300

考え方

制約的に O(N^3) で間に合う。文字列の問題は

文字列の問題は何となくrec(0,n)という再帰関数を呼び出したら答えが求まるようなイメージがあります。

という考え方もあるよう。

さて区間 [l, r) の文字列について最大の iwi の数について考えていく。考え方としてはある区間を考えて消せる区間の場合は消していく。という方針となる。

rec(l, r) = max(rec(l, k) + rec(k, r)) については自明だと思う。

ある区間 l, r) の文字列が全て消える場合は以下の条件を満たすことである。

  1. 文字列の長さが 3 の倍数
  2. 両端が i である
  3. 両端の i と中にある w との間にある文字列がすべて消える

上記を満たす場合のみすべての文字が消えるのでその処理をすればよい。

Submission #3925893 - Typical DP Contest

どこに着目して考察するべきだったか

基本的に全探索なんだと思う。iwiを構成できる全パターンの場合にiwiを足していくイメージでどれだけ伸ばせるかというイメージだが...。

何がバグっていたか

得た知見

類題

Typical DP Contest