うにゅーん、って感じだ

SRM highest:1910. C#を書きます.

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)
}

つまり、両端がiでかつwが連続しない文字列は、適切な順番で操作を行っていくことによりwがなくなるもしくはiが1個以下になるまで操作ができる、というものです。めっちゃびっくり。

その方針で書いたのがこちらtdpc.contest.atcoder.jp

なるほど通ってしまった……。

自分でも反例を考えたのですが思いつかず。誰かつよいひとに正しいのかどうか判定してほしさがある。


なんだかんだ一晩で3問通し 10問/20問。ただ、後半はマジで解ける気がしない。

ナップザックもうまく解けたので記事書くかも