srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SRM 688 div2 easy ParenthesesDiv2Medium

問題

問題概要

カッコの文字列が与えられる。カッコが対応する形に変更する。ただし変更できる文字の数は、((文字数)/2)+1まで。

解法

動的計画法で解いた。変更できる文字の数に制限があるので、最小の数で対応づけができるものを求めた。dp[i][j] := i番目までみて、'('がj個多い時の変更した最小回数 として、ループで値を埋めていった。注意することは漸化式を立てるときに、j=0の時だけ場合分けしなければならない。j=0の時に、次に、')'を置くと、j=-1となり、カッコが対応しなくなるから。
これで最小値は求まるが、どこの位置を変更したかも求めなければならない。そのため経路復元用に、back[i][j] := i番目まで見て、'('がj個多いときにどちらをつかったか、0なら'(' 1なら')' としてどちらを選んだかを記憶しておく。復元用配列は、dp配列と同じようにとればよい。backを逆方向にたどり、どちらを使ったかをメモし、そこからどのような文字列をつくったか求め、元の位置と異なっている箇所が変更した箇所となる。

ミス

もともと対応しているカッコを除外して、そのほかの部分を変える解法。だいぶ楽に書けるみたい。

pekempey.hatenablog.com

コード

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//dp[i][j] := i番目までみて、'('がj個多い時の変更した最小回数
int dp[55][30];
//back[i][j] := i番目まで見て、'('がj個多いときにどちらをつかったか、0なら'(' 1なら')'
int back[55][30];
class ParenthesesDiv2Medium{
public:
    vector <int> correct(string s){
        rep(i, 55)rep(j, 30) dp[i][j] = INF;
        dp[0][0] = 0;
        for (int i = 0; i < s.size(); ++i){
            for (int j = 0; j <= s.size() / 2; ++j){
                if(j == 0){//'('のみしかおけない
                    if(s[i] == '('){
                        if(dp[i][j] < dp[i + 1][j + 1]){
                            dp[i + 1][j + 1] = dp[i][j];
                            back[i + 1][j + 1] = 0;
                        }
                    }else{
                        if(dp[i][j] + 1 < dp[i + 1][j + 1]){
                            dp[i + 1][j + 1] = dp[i][j] + 1;
                            back[i + 1][j + 1] = 0;
                        }
                    }
                }else{
                    if(s[i] == '('){
                        //'('をおく
                        if(dp[i][j] < dp[i + 1][j + 1]){
                            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
                            back[i + 1][j + 1] = 0;
                        }
                        //')'をおく
                        if(dp[i][j] + 1 < dp[i + 1][j - 1]){
                            dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + 1);
                            back[i + 1][j - 1] = 1;
                        }
                    }else{
                        //'('をおく
                        if(dp[i][j] + 1 < dp[i + 1][j + 1]){
                            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
                            back[i + 1][j + 1] = 0;
                        }
                        //')'をおく
                        if(dp[i][j] < dp[i + 1][j - 1]){
                            dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j]);
                            back[i + 1][j - 1] = 1;
                        }
                    }
                }
            }
        }

        //復元
        vector<int> ans;
        int now = 0;
        for (int i = s.size(); i > 0; --i){
            if(back[i][now] == 0){
                ans.push_back(0);
                now--;
            }else{
                ans.push_back(1);
                now++;
            }
        }
        reverse(ans.begin(), ans.end());
        string tmp = "";
        rep(i, ans.size()){
            if(ans[i] == 0) tmp += '(';
            else tmp += ')';
        }
        vector<int> ret;
        rep(i, s.size()){
            if(s[i] != tmp[i]){
                ret.push_back(i);
            }
        }
        return ret;
    }
};