SRM671 div1 easy BearCries - ferinの競プロ帳

考えたこと

_の配置の組み合わせ数を無視してとりあえず;の方だけ数えてみようとする
;でペアを組めるのは_を挟んでるやつだけ
i番目を始点, j番目を終点とできるなら辺i→jを張るみたいなグラフを考える
DAGのマッチングに落ちたと思ったけどマッチングが何通りあるか求めないといけない
マッチングが何通りあるか求めることになりそう（これ可能か…？）
できたとしても_の配置を組み込むの不可能では？
DPしたくなる
;を使った位置を覚えるbitDPとかしたくなるけど制約的に論外
dp[i番目][;がj個] みたいなDPを考える
遷移とかまるで出来る気がしない
-----解説を見た-----
dp[i番目][まだを含まない;の数][もうを含んだ;の数] でDP
遷移はコードのコメントを見てください

DPの状態を3次元で取るのがなぜか頭から抜け落ちていた
状態を思いついても遷移ができずに終わっていた気もする
DPの状態数の削減として順番込O(N!) → 順番なしO(2^N) → 使った個数O(N) みたいな感じがよく見かける気がする
対応を取る感じのDPなら始点の数, 対応の取れたペアの数, 位置あたりを持つのは鉄板っぽい

似た雰囲気を感じた問題
B - 天下一魔力発電

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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

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

ll dp[205][105][105];
class BearCries {
   public:
   int count(string message)
  {
    int n = message.size();
    memset(dp, 0, sizeof(dp));

    // dp[i番目][_がない開いた顔文字][_がある開いた顔文字]
    dp[0][0][0] = 1;
    REP(i, n) REP(j, 101) REP(k, 101) {
      if(!dp[i][j][k]) continue;
      if(message[i] == '_') {
        // _を含ませる _はj個あるので選び方はj通り
        if(j) (dp[i+1][j-1][k+1] += dp[i][j][k]*j) %= MOD;
        // すでに_含んだやつに今の_を付け加えるのはk通り
        if(k) (dp[i+1][j][k] += dp[i][j][k]*k) %= MOD;
      } else if(message[i] == ';') {
        // すでに_を含んだやつから1つ選んで閉じる k通り
        if(k) (dp[i+1][j][k-1] += dp[i][j][k]*k) %= MOD;
        // _を含まない開いた顔文字を増やす 1通り
        (dp[i+1][j+1][k] += dp[i][j][k]) %= MOD;
      }
    }

    return dp[n][0][0];
  }
};