kmjp's blog

競技プログラミング参加記です

SoundHound Programming Contest 2018 Masters Tournament 本戦 : E - Hash Swapping

平方分割はサイズ設定が割と難しい。
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e

問題

M個のN文字の文字列が与えられる。
また文字列におけるローリングハッシュの計算式が与えられる。

以下のクエリに順次答えよ。

  • 2つの文字列において、同じ位置の部分文字列をswapする
  • 指定された文字列の部分文字列のハッシュ値を答える。

解法

いわゆる平方分割で解く。
文字列をD文字ずつのブロックに分け、ブロック毎のハッシュ値を計算しておこう。
前者のクエリに対し、ブロック全体がswap対象となる部分は文字列だけでなくブロックのハッシュ値もswapすればいいので、ハッシュ値の再計算はO(D)で済む。
後者のハッシュ値計算もO(D+N/D)で済むので、Dを300~500程度にしておくとどうにか解ける。

const int DI=300;
int N,M,Q;
string S[21][700];
ll phash[21][700];

ll p10[201010];
ll mo=1000000007;


void update(int cur,int id) {
	ll ret=0;
	for(int i=(int)S[cur][id].size()-1;i>=0;i--) ret=(ret*1000000+S[cur][id][i])%mo;
	phash[cur][id]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,200010) p10[i+1]=p10[i]*1000000%mo;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>s;
		FOR(x,N) S[i][x/DI].push_back(s[x]-'a'+1);
		FOR(x,N/DI+2) update(i,x);
	}
	cin>>Q;
	while(Q--) {
		int T,X,Y,L,R;
		cin>>T>>X>>Y>>L>>R;
		X--,Y--,L--;
		if(T==1) {
			if(L%DI) {
				while(L%DI && L<R) swap(S[X][L/DI][L%DI],S[Y][L/DI][L%DI]), L++;
				update(X,(L-1)/DI);
				update(Y,(L-1)/DI);
			}
			if(R%DI) {
				while(R%DI && L<R) R--, swap(S[X][R/DI][R%DI],S[Y][R/DI][R%DI]);
				update(X,R/DI);
				update(Y,R/DI);
			}
			while(L<R) {
				swap(S[X][L/DI],S[Y][L/DI]);
				swap(phash[X][L/DI],phash[Y][L/DI]);
				L+=DI;
			}
		}
		else {
			ll ret=0;
			int len=0;
			while(L%DI && L<R) (ret+=p10[len]*S[X][L/DI][L%DI])%=mo, len++, L++;
			while(L+DI<=R) (ret+=p10[len]*phash[X][L/DI])%=mo, len+=DI, L+=DI;
			while(L<R) (ret+=p10[len]*S[X][L/DI][L%DI])%=mo, len++, L++;
			cout<<ret<<endl;
		}
	}
	
	
}

まとめ

5秒かかったので割と怖い。