roiti46's blog

主に競プロ問題の解説を載せてます

Topcoder SRM671 Div1 Easy: BearCries

MedよりもEasyの方が難しいような

問題

";_;" や ";_______;" のような長さ1以上のアンダースコアを囲んだ顔文字を考える。渡された文字列を1つ以上の顔文字に分解したい。分解の仕方は何通りあるか答えよ。

解法

ここの解説と提出コードを参考に(というよりほとんど写経)しています。
DPで解いていく。dp[位置][余っている";"の個数][余っている";_..."の個数]=(分解の仕方の数)としてdp表を更新していけばO(N3)で解ける。

ll mod = 1000000007;
ll dp[205][205][205];

class BearCries {
public:
  void add(ll &a, ll b) {
    a += b;
    a %= mod;
  }

  int count(string message) {
    int n = message.size();
    rep(i, 205) rep(j, 205) rep(k, 205) dp[i][j][k] = 0;
    dp[0][0][0] = 1;

    rep(i, n) rep(single, n) rep(ready, n) {
      if (dp[i][single][ready] == 0) continue;
      ll x = dp[i][single][ready];
      if (message[i] == ';') 
        //シングルの";"を1つ増やす
        add(dp[i + 1][single + 1][ready], x);
        //";_..."を1つ消費して顔文字を完成させる
        if (ready > 0) add(dp[i + 1][single][ready - 1], ready * x);
      }
      else {
        //";_.."から1つ選んで +"_"
        if (ready > 0)  add(dp[i + 1][single][ready], ready * x);
        //シングルの";"の1つを";_"にする
        if (single > 0) add(dp[i + 1][single - 1][ready + 1], single * x);
      }
    }

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

まとめ

このDPは今の自分じゃ書き下せないなあ