ferinの競プロ帳

競プロについてのメモ

SRM686 div1 easy BracketSequenceDiv1

考えたこと

  • 開括弧を選んでそれに対応する閉じ括弧のパターンが何通りあるか数えるみたいなので考える
  • 正しい括弧列ならば開括弧の数は(括弧列の長さ/2)になるはず
  • 与えられる括弧列の長さが最大40なのでその半分なら開括弧の選び方を全列挙できる
  • もし開括弧が閉括弧より多ければ文字列を反転すればいい
  • 開括弧に対応させられる閉括弧の数を知りたい
  • 閉括弧について後ろから累積和を取ればいい気持ちになる
  • 後ろの開括弧から試すと (閉括弧の数 - 使った分の閉括弧の数) の積でいける気持ちになる
  • sampleを試すと([)]みたいなのを余計に数えている
  • 次に出て来る種類の違う開括弧までで閉括弧の数を数える
  • ()())) で一番最初の開括弧なら太字の3個みたいな
  • sample4が一生通せない
  • 冷静になって考え直すと([])を数えられてない
  • 開括弧を指定したところで対応した閉括弧の数を高速に数えられる気がしない
    -----解説を見た-----
  • 半分全列挙 or DP
  • 半分全列挙
    • 前半と後半でそれぞれ使う括弧を列挙しておく
    • 前半と後半でマージできるものの数を数える
  • DP
    • dp[l][r] = [l,r)で正しい括弧列の部分文字列の数
    • dp[l][r] = prod(dp[l][x] * dp[x+1][r] | s[l]とs[i]が対応が取れている)

それっぽい解法を思いついた気持ちになって考えてたけど的外れだったらしい
だめな方針なことにもうちょっと早く気づきたかった…
|S| <= 40 で半分全列挙を考えもしなかったのはだめ
半分全列挙はTLギリギリっぽいので思いつけたらDPの方がよさそう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll dp[55][55];
class BracketSequenceDiv1 {
   public:
   long long count(string s)
  {
    ll n = s.size();

    function<ll(ll,ll)> func = [&](ll l, ll r) -> ll {
      if(dp[l][r] >= 0) return dp[l][r];
      if(l==r) return 1;
      ll ret = func(l+1, r);
      FOR(i, l+1, r) {
        if((s[l]=='('&&s[i]==')') || (s[l]=='['&&s[i]==']')) {
          ret += func(l+1,i) * func(i+1, r);
        }
      }
      return dp[l][r] = ret;
    };

    memset(dp, -1, sizeof(dp));
    return func(0, n) - 1;
  }
};