天下一プログラマーコンテスト2016予選B-天下一魔力発電(400)

概要

偶数長'(', ')'からのみなる列(size <= 100)が与えられる。すべての '(' が対応する ')' を持つとき、それをいい状態という。
今カーソルは一番左を指している。コスト１を使って、次の操作のうちのいずれかを行える。

カーソルを左右に動かす(動かせるなら)。
カーソルの指してる文字を変更する。'(' -> ')' とか ')' -> '(' である。

良い状態にするには最小でコストいくつかかるか？

ACするまで

1. 明らかに、カーソルを左に戻すのは無駄なので、やらなくていい。ひとまず、どこまでカーソルを進めるかを全探索。
2. ある場所Xより向こうをすべて変更しないとき、左からX-1までをつじつまがあうように変更する最小コストをDPで求められそう。
3. 求めた。しかし、WAWAWA

4. つじつまがあうという条件の判定で、右を見て()の数を判断するだけというのは実をいうとできない！
5. そもそも、DPでどこで最後に変更を加えたか？を追加すれば、DPをするだけでいい状態になっているかどうかを簡単に確かめられる。
6.AC

考察

カーソルを動かすのにコストがかかることから、最終的にどこまで変更を加えるか、というのを決めていれば、変更を加える箇所を見るだけでいいとまずわかる。
というわけで、ひとまず次のようなDPテーブルを立てた。

dp[i][j] := i文字目まで見て、'(' - ')'の数がjになってる時の最小コスト。

更新式は難しく、今の見てる場所と同じかっこにするならコスト0、そうでなければコスト1である。

Xまでカーソルを動かすということにして、X+1以降の'(' - ')'を求め、それをYすると、dp[X + 1][-Y] + Xが答えとなる。(X+1らへんはインデックスなどでずれる。-Yは、後半 '(' の数が ')' より少ないときにのみ正となり、その分だけ左で置き換えをする。その結果にXまでのカーソルのコスト分を足す)

しかし、これには一つの問題がある。

実は、()列が整合取れてるかどうかは、始点からみて、常に'(' - ')' >= 0が成り立つかどうかであるが、これは()列の途中から見始めても一概には判断できない。つまり、()が整合取れてるかどうかは'(' - ')' >= 0が常に満たされるで判断する場合は、絶対に一番最初から見ないといけないのである。

さて、一番最初から見るようにするDP配列を考えてみる。
一番最初から見るときに、先ほどのものと違うのは、「どこどこまでカーソルを動かしたか？」という情報がさきほどのDP配列ではわからない点である。先ほどはXまでカーソルを進めるものとしてその都度DP配列を計算していた。しかし、前から見ていくとなれば、この情報を持つ必要がある。

dp[i][j][k] := i文字目まで見て、'(' - ')'がjであり、最後に変更を加えたのはk文字目であるときの最小コスト。

これの具体的な遷移も簡単である。詳細はソースコードを参照。

ACソースコード：

Submission #8681872 - 天下一プログラマーコンテスト2016予選B