天下一魔力発電 [天下一プログラマーコンテスト2016 予選B : B]

問題

http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_b

'('と')'から成る文字列Sがある。
カーソルは文字列の先頭から始まる。
以下の3つの処理が行えるとき、文字列Sを括弧の対応が取れた状態にする最小手数を答えよ。

1. カーソルを右に動かす
2. カーソルを左に動かす
3. カーソルが指す文字を'('なら')'、')'なら'('にする

2 <= |S| <= 100

S

は偶数

帰納的考察（解説見た）

以下、N = |S|

1. 括弧の対応問題だし cnt[i] は使うんだろうなという感じ
cnt[i] = i文字目までの　「(」の数 - 「)」の数
2. 対応関係が正しいというのは、全てのcnt[i]が0以上でcnt[N-1]==0
3. 頭からこうなるように貪欲にやればいい？
4. だめだった
5. うーんうーん

――壁――

6. 基本を忘れていた
7. 「愚直解を考える」「全部の状態数を考える」
8. 行う処理の中でカーソルを左に動かすのは無駄
9. なので、各文字を変えるかどうかだけ考えればよいので、これで2^n通り
10. これだと多いので、指数オーダを多項式オーダに変えるアレを考える
11. DP!!!!!

dp[i][j][k] = i文字目までで最後に変更したのがj文字目でcntの数がkである最小の変更回数
dp[0][0][0] = 0, 他 = INF
更新式は長いのでソース参照
そんなに難しくないですけど、0 < kという条件をつけているのは、対応関係が正しい条件の1つに全てのcntが0以上というのがあるからです

実装

http://tenka1-2016-qualb.contest.atcoder.jp/submissions/858862

#define INF INT_MAX/2
string S;
//-----------------------------------------------------------------
int dp[101][101][101];
int solve() {
	int N = S.length();
	rep(i, 0, N + 1) rep(j, 0, N + 1) rep(k, 0, N + 1) dp[i][j][k] = INF;
	dp[0][0][0] = 0;
	
	rep(i, 0, N) rep(j, 0, N) rep(k, 0, N + 1) if(dp[i][j][k] != INF){
		if (S[i] == '(') {
			dp[i + 1][j][k + 1] = min(dp[i + 1][j][k + 1], dp[i][j][k]);
			if(0 < k) dp[i + 1][i][k - 1] = min(dp[i + 1][i][k - 1], dp[i][j][k] + 1);
		} else{
			dp[i + 1][i][k + 1] = min(dp[i + 1][i][k + 1], dp[i][j][k] + 1);
			if (0 < k) dp[i + 1][j][k - 1] = min(dp[i + 1][j][k - 1], dp[i][j][k]);
		}
	}

	int ans = INF;
	rep(j, 0, N) ans = min(ans, dp[N][j][0] + j);
	return ans;
}
//-----------------------------------------------------------------
int main() {
	cin >> S;
	cout << solve() << endl;
}