SRM671 div1 easy BearCries
考えたこと
- _の配置の組み合わせ数を無視してとりあえず;の方だけ数えてみようとする
- ;でペアを組めるのは_を挟んでるやつだけ
- 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]; } };