【SRM671Div1】BearCries【300point】

問題概要

1つ以上の_を;で挟んだ塊を顔文字と呼ぶ. (例. ;_;, ;__;, ;_________________;, …)

今, ;と_からなる文字列$s$が与えられる. $s$をいくつかの部分文字列に分割したとき, それらが顔文字であるような分割の通り数を$\mathrm{mod}\ 10^9 + 7$で求めよ.

制約

• $1 \leq |s| \leq 200$
• $s$は;と_からなる.

考察

懺悔

えーと, 解けませんでした. 解法ガチャの結果を書きます.

1. 包除原理
   • これはそもそも誤読をしていた…
   • 単なるセミコロンのマッチングだと思ってたので, ;が隣り合ってるものを除いていけばいいねって思ってた
2. 真ん中固定してマッチング
   • アンダーバーの扱いがむずかしすぎる
   • 無駄な時間を過ごした
3. DP
   • $dp[i][j][k] := s_i$までで, ;が$j$個, _が$k$個余るときの通り数とか考えたけど遷移が組めるわけもなく
   • 今思えばそりゃあむりだね
4. 迷子になった

結局

kmjpさんのブログをチラ見した.

;__みたいなやつが何個あるかを状態として持ってDPすればいい. こういうの自力で思いつきたい.

定義

$dp[i][j][k] := s_i$までで, ;が$j$個, ;__が$k$個余るときの通り数
($dp[0][0][0] = 1$でそれ以外は$0$に初期化).

• $s_i$が;のとき
  1. セミコロンをさらに余らせる : $dp[i + 1][j + 1][k] \leftarrow dp[i][j][k]$
  2. ;__に結合して顔文字を作る : $dp[i + 1][j][k - 1] \leftarrow dp[i][j][k] \times k$
• $s_i$が_のとき
  1. セミコロンに結合する : $dp[i + 1][j][k] \leftarrow dp[i][j][k] \times k$
  2. ;__に結合する : $dp[i + 1][j - 1][k - 1] \leftarrow dp[i][j][k] \times j$

$dp[|s|][0][0]$が求めたい通り数.

反省

人力で$s$を左から走査することを考えればよかった.

そうすれば顔文字を左側から構築するイメージが湧いて, ;__ってまとめられたかも.

どんな問題でも一回自分でやってみるのはやっぱり重要.

提出コード(C++🔆)

const int MOD = (int)1e9 + 7;
const int MAX = 200;
struct BearCries {
    string message;
    ll dp[MAX + 10][MAX + 10][MAX + 10];
    int count(string _message) {
        message = _message;
        dp[0][0][0] = 1;
        REP(i, MAX) REP(j, MAX) REP(k, MAX) {
            if (message[i] == ';') {
                (dp[i + 1][j + 1][k] += dp[i][j][k]) %= MOD;
                (dp[i + 1][j][k - 1] += dp[i][j][k] * k) %= MOD;
            } else {
                (dp[i + 1][j][k] += dp[i][j][k] * k) %= MOD;
                (dp[i + 1][j - 1][k + 1] += dp[i][j][k] * j) %= MOD;
            }
        }
        return dp[(int)message.size()][0][0];
    }
};