Codeforces ECR #110 : F. String Distance

ECRの最終問にしてはコードは短め。
https://codeforces.com/contest/1535/problem/F

問題

同じ長さの文字列a,bに対し、f(a,b)は以下を意味する。

• aまたはbのどちらかの部分文字列を選び、その中を昇順にソートする。f(a,b)は、両者が一致するまでの操作回数。
• ただし、どうやってもaとbが一致できないケースはf(a,b)=1337とする。

文字列集合Sが与えられる。Sの異なる要素対(a,b)におけるf(a,b)の総和を求めよ。

解法

sorted(a)!=sorted(b)な(a,b)におけるf(a,b)が1337確定である。
a!=bかつsorted(a)=sorted(b)の場合、少なくともa,b全体のソートをすればaとbが一致するので、f(a,b)が2以下なのは確定する。

そこで、まず各文字列をソートし、その時点で一致しない文字列対(a,b)はf(a,b)=1337として計上する。
一致する文字列対(a,b)はf(a,b)=2としていったん計上し、その後f(a,b)=1となるケースを差し引こう。
これは|a|の大きさで分岐させる。

• |a|=|b|≦20の場合
  • Gを、入力の文字列のうちソートしたらaと同じになる文字列の集合とする。
  • aの部分列のソートを総当たりし、G内にそれが含まれていたら1引こう。
• |a|=|b|＞20の場合
  • 文字列対(a,b)を総当たりしよう。まず、両者共通するprefix・suffixを取り除く。
  • 残る文字列が、a,bいずれかが昇順であればf(a,b)=1で済むので1引こう。

int N,len;
string S[202020];
string T[202020];

map<string,vector<string>> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>S[i];
		len=S[i].size();
		T[i]=S[i];
		sort(ALL(T[i]));
		ret+=1337*i;
		ret-=1335*M[T[i]].size();
		M[T[i]].push_back(S[i]);
	}
	
	FORR2(a,V,M) {
		sort(ALL(V));
		
		if(len<=20) {
			set<string> G;
			FORR(v,V) G.insert(v);
			FORR(v,V) {
				FOR(y,len) FOR(x,y) {
					string w=v;
					sort(w.begin()+x,w.begin()+y+1);
					if(w[x]==v[x]) continue;
					if(w[y]==v[y]) continue;
					if(G.count(w)) ret--;
				}
			}
		}
		else {
			FOR(j,V.size()) FOR(i,j) {
				x=0;
				y=len-1;
				while(V[i][x]==V[j][x]) x++;
				while(V[i][y]==V[j][y]) y--;
				for(k=x;k<y;k++) if(V[i][k]>V[i][k+1]) break;
				if(k==y) ret--;
			}
		}
		
	}
	cout<<ret<<endl;
}

まとめ

重そうだと思ったけど、意外に時間かからないな。