AtCoder ARC #094 : F - Normalization

その性質成り立つのか…。
https://beta.atcoder.jp/contests/arc094/tasks/arc094_d

問題

abcで構成されるN要素の文字列Sがある。
Sのうち連続する2文字が異なるとき、両者をその2文字と異なるものに置き換えることを任意回数繰り返すことを考える。
そうして得られる文字列は何通りか。

解法

Sがもともと全文字同じ場合は変更しようがないので1。
N≦3のときは総当たりする。

この類の問題の定番テクとして、a→0,b→1,c→2と置き換えたとき、処理によって文字列における数値の総和 mod 3は変化しないという特性を用いる。
N≧4の場合、Sが全文字同じでない場合、以下の条件を満たすすべての文字列を生成できる、らしい。

• 上記数値の総和mod 3が等しい
• 最低1か所同じ文字が2文字連続している

よって、「すべての文字列を生成できる」のでまずはSを無視し、各位置にa,b,cが来た場合を分岐させつつ以下の状態に対しDPを行おう。
dp(i, C, last, mod) := 先頭i文字目まで処理したとき、C:同じ文字が連続した箇所があったかどうかの真偽値、last:最後の文字、mod:上記mod値　の状態を満たす組み合わせ数

Sにおける上記mod値をmとすると
dp(N,True,'a',m)+dp(N,True,'b',m)+dp(N,True,'c',m)
が解となる。
ただしSがもともと同じ文字の連続が1個もない場合、その分解に1を加える。

string S;
int N;
ll mo=998244353;
ll dp[202020][2][3][3];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>S;
	N=S.size();
	
	if(N<=7) {
		set<string> T,R;
		T.insert(S);
		while(T.size()) {
			set<string> U;
			FORR(t,T) {
				R.insert(t);
				FOR(i,N-1) {
					if(t[i]!=t[i+1]) {
						string a=t;
						a[i]=a[i+1]='a'+'b'+'c'-a[i]-a[i+1];
						if(R.count(a)==0) {
							U.insert(a);
							R.insert(a);
						}
					}
				}
				
			}
			T=U;
		}
		cout<<R.size()<<endl;
		return;
	}
	
	int cnt[3]={};
	int tot=0;
	FORR(c,S) {
		c-='a';
		cnt[c]++;
		tot+=c;
	}
	
	if(cnt[0]==N || cnt[1]==N || cnt[2]==N) return _P("1\n");
	
	dp[1][0][0][0]=1;
	dp[1][0][1][1]=1;
	dp[1][0][2][2]=1;
	for(i=1;i<N;i++) {
		
		FOR(j,2) FOR(x,3) FOR(y,3) FOR(z,3) {
			(dp[i+1][j|(x==z)][z][(y+z)%3]+=dp[i][j][x][y])%=mo;
		}
	}
	
	ll ret=1;
	FOR(i,3) ret+=dp[N][1][i][tot%3];
	FOR(i,N-1) if(S[i]==S[i+1]) {
		ret--;
		break;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

うーん、こういう微妙に証明が難しそうな問題が苦手。