SRM 671 Div1 Easy - BearCries

問題

TopCoder Statistics - Problem Statement

問題概要

;_;とか;___;みたいな泣いている顔文字(両端がセミコロンで間に1つ以上のアンダーバー)をcrying emoticonと呼ぶ。文字列が与えられる時、いくつかの部分列に分解(連続でなくて良い)して、それぞれがcrying emoticonになっているようにするような文字列の分け方は何通りあるか、で割った余りを答えよ。

• 

アイデア

DPによる解法を考える。

まず、文字列内の;は、emoticonの先頭であるか、終端であるかのどちらかであると想定できる。また、_は、既に開かれているemoticonのどれかに割り当てられる必要がある。最終的に開かれている;があってはならないのも明らかにわかる。また、既に_を1つ以上割り当てられたemoticonとまだ1つも割り当てられていないemoticonも区別する必要がある。

そこで、文字列を、文字目に注目しながら前から順に見ていき、それぞれ何に割り当てるかを決めていくことにしてみる。既に開かれているemoticonのうち、_を1つも持っていない物の数を、既に1個以上持っている物の数をと表す。すると、以下のようになる：

• が;のとき

これを開いているものとして割り当てるなら、a+=1。逆に、閉じているものとして割り当てるなら、個の中から1つを選んで区間を閉じれば良いので、b-=1。

• が_のとき

どの開いたemoticonに割り当てるかを考える。まだ_を1つも持っていない個のうちの1つに割り当てるとすれば、a-=1,b+=1となり、既に1つ以上割り当てられている個のうちの1つに割り当てるならば、に変化はない。

これを再帰によって前からメモ化しながら調べていけば良い。この再帰が終わる(となる)時に、は共に0になっていることが正しいemoticonの構成条件になる。また、emoticon1つには最低でも3文字必要なので、の上限は200/3程度になる。これでメモ化再帰を試みる。

乗算が入るので、計算途中はlong型にしておかないとオーバーフローしてしまうので注意が必要。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

const long mod=1e9+7;

class BearCries {
    public:
    string s;
    long dp[201][70][70];

    long rec(int now, int a, int b){
      if(dp[now][a][b]>=0) return dp[now][a][b];

      if(now==s.size()) return (a==0)&&(b==0);

      long ret=0;
      if(s[now]==';'){
        //区間を開く
        if(a<69){
          ret+=rec(now+1,a+1,b);
          ret%=mod;
        }
        //区間を閉じる
        if(b>0 && b<69){
          ret+=b*rec(now+1,a,b-1);
          ret%=mod;
        }
      }
      else{
        //まだ1つもアンダーバーを持っていないのに割り当てる
        if(a>0 && b<69){
          ret+=a*rec(now+1,a-1,b+1);
          ret%=mod;
        }
        //すでに1つ以上持っているのに割り当てる
        if(b>0 && b<69){
          ret+=b*rec(now+1,a,b);
          ret%=mod;
        }
      }

      return dp[now][a][b]=ret%mod;
    }

    int count(string message) {
      s=message;
      memset(dp,-1,sizeof(dp));
      long ret=rec(0,0,0);
      return (int)ret;
    }
};