Codeforces Beta Round #17 C. Balance

Codeforces

本番で解けなかったシリーズ。

Balance

問題の概要

  • 文字a, b, cからなる、長さ150以下の文字列sが与えられる
  • 文字1つを隣接するどちらかのものと同じにする操作を何回か加える
  • s中のa, b, cそれぞれの数の差が高々1になるような文字列は何種類作れる？


解法

  • あまりに分からなかったのでTutorialを参照しました。
  • 結局のところ、操作によって作れる文字列は
    • sの文字列を先頭から順に0個以上並べ、sと同じ長さにする
    • つまり，s[0]*s[1]* … s[N-1]* で表せる長さNの文字列
  • なので、sの先頭から文字を使っていき[aの個数][bの個数][cの個数]でDP
    • [pos][a][b][c] : pos番目の文字を少なくとも1回使って[a][b][c]とする文字列の種類数
    • 次に使う文字は現在地から最も近い場所のものを使う事で重複カウントをなくす
    • s上で同じ文字が続く場所は重複カウントしないように1文字にまとめておく
    • 条件を満たすとき各文字の個数は(N+2)/3を越えないので、この分でループ
  • 全体でO(N^4)だけど，1/27になるので何とか間に合う
  • メモリも[150][51][51][51]で確保して76Mbyte程度で，許容範囲内
#include <iostream>
#include <string>

using namespace std;

const int MOD = 51123987;
const int INF = 1000000;

int main(){
    int N;
    static int dp[150][51][51][51];
    while(cin >> N){
        string s; cin >> s;
        string t; t += s[0];
        for(int i=0;i<s.size();i++)
            if(t[t.size()-1] != s[i]) t += s[i];
        memset(dp, 0, sizeof(dp));
        dp[0][0][0][0] = 1;
        int up = (s.size()+2)/3;
        for(int i=0;i<t.size();i++){
            int p[3] = {INF, INF, INF};
            for(int j=i;j<t.size();j++)
                p[t[j]-'a'] = min(p[t[j]-'a'], j);
            for(int a=0;a<=up;a++){
                for(int b=0;b<=up;b++){
                    for(int c=0;c<=up;c++){
                        if(p[0]!=INF&&a+1<=up)
                            dp[p[0]][a+1][b][c] = (dp[p[0]][a+1][b][c]+dp[i][a][b][c])%MOD;
                        if(p[1]!=INF&&b+1<=up)
                            dp[p[1]][a][b+1][c] = (dp[p[1]][a][b+1][c]+dp[i][a][b][c])%MOD;
                        if(p[2]!=INF&&c+1<=up)
                            dp[p[2]][a][b][c+1] = (dp[p[2]][a][b][c+1]+dp[i][a][b][c])%MOD;
                    }
                }
            }
        }
        long long ans = 0;
        for(int i=0;i<t.size();i++){
            for(int a=up-1;a<=up;a++)
                for(int b=up-1;b<=up;b++)a
                    for(int c=up-1;c<=up;c++)
                        if(a+b+c==s.size()) ans = (ans + dp[i][a][b][c])%MOD;
        }
        printf("%d\n", (int)ans);
    }
}