パナソニックプログラミングコンテスト2020 : E - Three Substrings

いろいろ慌てすぎたね…。
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e

問題

文字列3つA,B,Cが与えられる。
ただしこれらの一部の文字はマスクされている場合もある。

文字列Sのうち、A,B,Cを部分文字列として含むようなものの最短は何文字か。
ただし、A,B,Cのマスク部分はSと一致しなくてよい。

解法

Sの先頭|A|文字がAに一致し、x文字目から|B|文字がBに一致し、(x+y)文字目から|C|文字がCに一致するようなものが構築できるか高速に判定できれば、x,yを総当たりしてO(|S|^2)程度で答えられることがわかる。
A,B,Cの順番がこうでないこともあり得るので、A,B,Cの並び順は3!通り総当たりしよう。

さて、上記の判定だが、結局

• Aのx文字目から後ろとBが等しいかとうか(マスク部分や同じ位置に文字のない箇所は無視)
• Bのy文字目から後ろとCが等しいかとうか(同上)
• Aのx+y文字目から後ろとCが等しいかとうか(同上)

がそれぞれわかればよく、これは事前に求めれば愚直に行ってもO(|S|^2)で済む。

string A[3];
int X,Y,Z;

int ok[3][4020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0]>>A[1]>>A[2];
	
	int mi=1<<30;
	sort(A,A+3);
	do {
		int X=A[0].size();
		int Y=A[1].size();
		int Z=A[2].size();
		
		FOR(i,4010+1) {
			ok[0][i]=1;
			FOR(x,X) if(x>=i && x-i<Y && A[0][x]!='?' && A[1][x-i]!='?' && A[1][x-i]!=A[0][x]) ok[0][i]=0;
			ok[1][i]=1;
			FOR(x,X) if(x>=i && x-i<Z && A[0][x]!='?' && A[2][x-i]!='?' && A[2][x-i]!=A[0][x]) ok[1][i]=0;
			ok[2][i]=1;
			FOR(x,Y) if(x>=i && x-i<Z && A[1][x]!='?' && A[2][x-i]!='?' && A[2][x-i]!=A[1][x]) ok[2][i]=0;
		}
		FOR(x,2001) FOR(y,2001) {
			if(ok[0][x] && ok[1][x+y] && ok[2][y]) {
				mi=min(mi,max({X,x+Y,x+y+Z}));
			}
		}
		
	} while(next_permutation(A,A+3));
	
	cout<<mi<<endl;
}

まとめ

今回ミスばっかりで残念。