TopCoder SRM 528 Div1 Medium SPartition

問題

'o'または'x'からなる、長さが偶数の文字列が与えられる。
この文字列をちょうど等しい二つの部分文字列にわける。

そのような分け方は何通りあるか、求めよ。

制約条件

文字列の長さ≦40

方針

dp[pos][diffの長さ][diff]を、文字列をposまで見て、
長さの差が(diffの長さ)であり、差の内容をビットで表したものがdiffになるような状態の数とする。

i番目の文字について、

• 長いほうの文字列の末尾に加える
• 短いほうの文字列の先頭と一致している場合、差を一文字減らす

のような状態遷移ができる。

配列で持つと実際には遷移しない状態に大量のメモリを食われてしまい、MLEするので、
(diffの長さ,diff)の部分をmapにする。

ソースコード

最大ケース5msくらい。

int n;
map<pi,ll> dp[2]; //メモリ節約のためにmapは最後から二つだけもっておくようにする

class SPartition {
  public:
  long long getCount(string s) {
    rep(i,2)dp[i].clear();
    n=s.size();
    dp[0][mp(0,0)]=1;
    int cur=0,next=1;
    rep(i,n){
      dp[next].clear();
      if(dp[cur][mp(0,0)])dp[next][mp(1,s[i]=='o')]+=dp[cur][mp(0,0)]*2;
//いままでの文字列が等しいとき、次の一文字をどちらに加えるか2通り
      
      fr(j,dp[cur]){
        int d=j->first.first, mask=j->first.second;
        if(d==0)continue;
        if((mask&1)==(s[i]=='o'))dp[next][mp(d-1,mask>>1)]+=j->second;
        if(d+1<=n-i-1)dp[next][mp(d+1,mask^(s[i]=='o')<<d)]+=j->second;
      }
      swap(cur,next);
    }
    return dp[cur][mp(0,0)];
  }