TopCoder SRM 706 Div1 Medium MappingABC、Div2 Hard MappingABC2

方針はあっていたのに詰めが甘かった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14494
https://community.topcoder.com/stat?c=problem_statement&pm=14496

問題

N要素の数列Tが与えられる。
Tに対応して、A,B,Cで構成されるN文字の文字列Sを考える。
ここで、T[i]=T[j]である場合S[i]=S[j]でなければならない。

こうして構成したSのうち、"ABC"を(不連続でもよい)部分文字列として持つのは何通りか。

解法

最も左にあるAの位置Lと最も右にあるCの位置Rを総当たりしよう。
すなわち、S[L]='A', S[R]='C'とし、S[0..(L-1)]に'A'は含まれず、S[(R+1)..(N-1)]に'C'は含まれないとする。
この場合、S[(L+1)..(R-1)]のうち、少なくとも1つ'B'が含まれていれば、条件を満たす文字列が作れる。

よって
mask[i] := 数字iがとりえる文字をbitmask(A,B,Cに1,2,4が対応)
とする解き、L,Rを動かしながらmask[i]は以下のようになる。

• S[L]='A'でなければならないのでmask[T[L]] &= 1
• S[R]='C'でなければならないのでmask[T[L]] &= 4
• x＜LであるS[x]は'A'以外でなければならないので mask[x] &= 6
• x＞RであるS[x]は'C'以外でなければならないので mask[x] &= 3

以下の集合を考える。

• P(L,R) := T[(L+1)...(R-1)]に登場する数値の集合
• Q(L,R) := T[0..(N-1)]に含まれる数値の集合からP(L,R)の各要素を除いたもの

Q(L,R)に含まれる要素xはmask[x]に対応する任意の文字をとれる。
P(L,R)に含まれる要素xはmask[x]に対応する任意の文字をとれるが、すべて'B'以外となることは許されない。

よって、(L,R)に対しを足しこんでいけばよい。
P,Qは合計で最大Nとおりあるが、mask[x]のとる値は0～7しかないのでそれぞれの登場回数だけ管理しておけばよい。
(L,R)のうちRを動かすたびにP(L,R)・Q(L,R)に含まれるmask[x]=iとなる要素の数を更新していけば、全体でO(N^2)で解ける。

class MappingABC {
	public:
	
	int countStrings(vector <int> t) {
		ll mo=1000000007;
		ll pall[8][3030];
		ll pex[8][3030];
		
		int N = t.size();
		int num[3030]={};
		
		int i,j,l,r;
		FOR(i,8) {
			pall[i][0]=pex[i][0]=1;
			FOR(j,3020) {
				pall[i][j+1]=pall[i][j] * __builtin_popcount(i) % mo;
				pex[i][j+1]=pex[i][j] * __builtin_popcount(i&5) % mo;
			}
		}
		
		FORR(r,t) num[r]++;
		ll ret=0;
		int mask[3030];
		
		FOR(l,N) {
			int in[8]={}, out[8]={};
			int tnum[3030]={};
			FOR(i,3020) if(num[i]) mask[i]=7, tnum[i]=num[i];
			FOR(i,l) mask[t[i]] &= 6;
			mask[t[l]] &= 1;
			
			FOR(i,l+1) tnum[t[i]]--;
			FOR(i,3020) if(num[i]) {
				if(tnum[i]==0) out[mask[i]]++;
				else in[mask[i]]++;
			}
			if((mask[t[l]]&1)==0) continue;
			
			for(r=N-1;r>=l+2;r--) {
				in[mask[t[r]]]--;
				
				if(t[l]!=t[r] && (mask[t[r]]&4)) {
					ll in_all=1, in_ex=1, out_all=1;
					FOR(j,8) {
						(in_all *= pall[j][in[j]])%=mo;
						(out_all *= pall[j][out[j]])%=mo;
						(in_ex *= pex[j][in[j]])%=mo;
					}
					
					ret += (in_all-in_ex+mo)*out_all%mo;
				}
				
				tnum[t[r]]--;
				mask[t[r]] &= 3;
				if(tnum[t[r]]) in[mask[t[r]]]++;
				else out[mask[t[r]]]++;
			}
			
		}
		
		return ret % mo;
	}
}

まとめ

もったいないなぁ…。