問題概要

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