Typical DP Contest I - イウィ - うにゅーん、って感じだ

DPコンですが、深夜にこねくり回してたらDPを使わずに ${ O(N) }$ で通ってしまったので誰か撃墜求む、という感じ。

問題はこちらtdpc.contest.atcoder.jp

で、まぁ私の考えたこととしては、まずこれらが言えます。

文字列sに対し操作の回数の最大値を ${ M(s) }$ とおくと、
・端に"w"があっても変わらない
${ \displaystyle M("w" + s) = M(s + "w") = M(s) }$
・"ww"があると、そこのwは操作により消すことができないので、そこで文字列が分割される
${ \displaystyle M(s + "ww" + t) = M(s) + M(t) }$

上の2つは簡単に言えて、これらを用いると任意の入力に対して、それを両端がiでかつwが連続しない文字列に分解してそれぞれの最大値の和を考えればよくなります。

ここからが重要で、上の分解により生成された両端がiでかつwが連続しない文字列に対し、以下の仮説が立てられます。
文字列sに含まれるiの個数を ${ s_i }$ 、wの個数を ${ s_w }$ とすると、上記を満たすsに対し、
${ \displaystyle M(s) = Min(s_i / 2, s_w) }$