kmjp's blog

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

Codeforces ECR #153 : E. Fast Travel Text Editor

これは面倒だけど難しくはないな…。
https://codeforces.com/contest/1860/problem/E

問題

アルファベット小文字N文字の文字列Sが与えられる。
ここで文字と文字の間のどこかにカーソルがある。
カーソルに対し、1回の移動で以下を行える。

  • 1文字左にカーソルを動かす
  • 1文字右にカーソルを動かす
  • 両隣の文字の対が一致する、別の場所のカーソルを動かす

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

  • カーソルの初期位置と終了位置が与えられるので、最小移動回数を求めよ。

解法

両隣の文字の組み合わせは26*26通りある。
そこでN+(26*26)頂点のグラフを考え、26*26点それぞれから(N+(26*26))点への距離をあらかじめ求めておこう。

各クエリについて、3つ目の手法を使わない場合と、26*26点のうちどこか1か所を使うケースを総当たりすればよい。

int N,M;
string S;
vector<pair<int,int>> E[26*26+50505];
int D[26*26][26*26+50505];
int V[50505+26*26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FORR(c,S) c-='a';
	
	
	FOR(i,N-1) {
		V[i]=N+26*S[i]+S[i+1];
		E[i].push_back({V[i],1});
		E[V[i]].push_back({i,0});
		E[i].push_back({i+1,1});
		E[i+1].push_back({i,1});
	}
	
	FOR(x,26*26) {
		FOR(y,26*26+N) D[x][y]=1<<20;
		deque<int> Q;
		D[x][N+x]=0;
		Q.push_back(N+x);
		while(Q.size()) {
			int cur=Q.front();
			Q.pop_front();
			FORR2(e,c,E[cur]) if(chmin(D[x][e],D[x][cur]+c)) {
				if(c==0) Q.push_front(e);
				else Q.push_back(e);
			}
		}
	}
	
	cin>>M;
	while(M--) {
		int F,T;
		cin>>F>>T;
		F--,T--;
		int ret=abs(T-F);
		FOR(i,26*26) ret=min(ret,D[i][F]+D[i][T]+1);
		cout<<ret<<endl;
		
		
		
	}
	
}

まとめ

そこまで難しくないけど、本番解いてないな…。