Codeforces #320 Div1 D. LCS Again

D問題にしてはコードが短くて済む。
http://codeforces.com/contest/578/problem/D

問題

N文字の文字列S,Tを考える。
これらはアルファベットの小文字の先頭M種類から構成される。
Sは入力として与えられる。

len(LCS(S,T))=N-1となるようなTは何通りあるか。

解法

EditorialはDPで解いているが、自分はそこで別解として紹介されていたものの方がしっくりきたのでそれを紹介。
まずSと1文字だけ異なるものはN(M-1)通り。

以下のようなTの候補を考える。

• S[0..(L-1)]=T[0..(L-1)]
• S[(R+1)..(N-1)]=T[(R+1)..(N-1)]
• S[L]!=T[L]、S[R]!=T[R]、len(LCS(S[L..R],T[L..R])=R-L

上記LCSの条件を満たすのは以下の何れかの組み合わせである。(ab..pqはある適当な同じ文字列、大文字は可変の小文字１文字)

• S[L..R]=ab..pqでT[L..R]=Xab..p
  • p!=q、X!=aなら良いので、p!=qならXをa以外の(M-1)通り解の候補とできる。
• S[L..R]=ab..pqでT[L..R]=b..pqY
  • a!=b、Y!=qなら良いので、a!=bならYをq以外の(M-1)通り解の候補とできる。

つまり、S[L..R]に対し、頭２文字が不一致なら(M-1)通り、後ろ２文字が不一致なら(M-1)通り答えに加算できる。
このままだとO(N^2)かかるが、まとめると連続する２文字が不一致なら、その２文字を(上記条件を満たす)S[L..R]の接頭辞または接尾辞にすることでTをN*(M-1)通り作成できる。

ただし例外ケースとして、S[L..R]=ababab...と異なる２文字を繰り返す場合、T[L..R]=bababa...と逆順にするケースが上記計算で２回計算されてしまう。
よってS中で異なる２文字の繰り返しとなる部分文字列の数だけ答えを減らす必要がある。
これは簡単なDPでO(N)で処理できる。

ll N,M;
ll ret;

string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>S;
	
	ret += N*(M-1);
	FOR(x,N-1) if(S[x]!=S[x+1]) ret+=N*(M-1);
	
	int cur=0;
	for(x=1;x<N;x++) {
		if(S[x-1]==S[x]) {
			cur=0;
		}
		else {
			if(x>1 && S[x]!=S[x-2]) cur=0;
			cur++;
		}
		ret-=cur;
	}
	
	cout<<ret<<endl;
}

まとめ

考察はややこしいけど、コードは単純。