TDPC I - イウィ

考え方

ABCで言うと、難しめD問題級。
または、ARCのA問題級。
この問題を作った人は $O(|s|^3)$ の動的計画法を意図していたのかもしれない。
しかし、この問題を解くのにそれは全く必要なく、少しの考察で簡単に解けてしまう。

まず、文字列中に "ww" という部分があった場合について考える。
これらの 'w' は、絶対に "iwi" を作ることはできない。
よって、この部分で区切って考えてしまってもよい。
同様に、先頭や末尾の 'w' も削除して考えてしまってよい。

よって、これらによって区切られたブロックごとに最大削除数を考えて合計すればよい。
このとき、$1$ つのブロック内の文字列は、両端が 'i' で、かつ 'w' の連続がないものになっている。

この場合、このブロックからの最大削除回数は、以下の貪欲法で非常に簡単に求まる。

'w' で区切られた 'i' の個数を数えて数列にする。
"iwi" を取り除くというのは、連続する $2$ つの正の数を合体して $2$ を引く操作になる。
そして、これは以下のような貪欲法に従うと、数列の長さが $1$ になるか、総和が $1$ 以下になるまで続けられる。
なぜなら、$1$ 同士を合体して $0$ ができない限り、合体不可能な隣接ペアは発生しないからである。

• $1$ も $2$ 以上も数列のどこかに存在する場合、片方だけ $1$ であるペアを合体する
• $2$ 以上しかない場合は、任意の箇所を合体する
• $1$ しかなくなってしまった場合は、前から順にペアを作って合体する

つまり、各ブロックからは、どちらかの文字の個数が足りなくなるまで削除を続ける方法が存在する。
よって、'w' の個数と、'i' の個数の半分との、小さい方がそのブロックの答えである。

実装は、方針に応じて文字列の先頭や末尾に "ww" を番兵としておくとやりやすい。

計算量は $O(|s|)$。

入力例2での動作

入力を受け取る。

s: iwiwwwiiiwiwiwiiwii

中央の "www" は "iwi" の削除に使えない境界となる。
先頭・末尾に余分な 'w' があれば、同様に除いて考える。
削除に関係する非空ブロックは次の $2$ つになる。

iwi
iiiwiwiwiiwii

最初のブロックには 'i' が $2$ 個、'w' が $1$ 個ある。
したがって、このブロックから削除できる "iwi" の最大個数は $\min(1,\lfloor 2/2\rfloor)=1$ である。

次のブロックには 'i' が $9$ 個、'w' が $4$ 個ある。
したがって、このブロックから削除できる "iwi" の最大個数は $\min(4,\lfloor 9/2\rfloor)=4$ である。

よって、削除できる "iwi" の最大個数は $1+4=5$ となる。

注意点

特になし。

別解

特になし。