Codeforces ECR #099 : F. String and Operations

コードは短いんだけどね。
https://codeforces.com/contest/1455/problem/F

問題

N文字の文字列Sが与えられる。
これらに対し、計N回の処理を行う。
i回目の処理では、以下のいずれかを行える。

• O: 何もしない
• R: S[i]とS[i+1]をswapする
• L: S[i]とS[i-1]をswapする
• D: S[i]を1つ手前の文字にrotateする
• U: S[i]を1つ後の文字にrotateする

最適な手順を取ったとき、Sから変換できる辞書順最小の文字を求めよ。

解法

dp[i] := Sの先頭i文字にi回処理をして得られる文字列の最小値
とする。
以下の状態遷移の組み合わせで全パターン列挙できる。

• S[i+1]にUかDを適用し、dp[i]の末尾に加えてdp[i+1]を作る。
• S[i+1]にLを適用し、dp[i]の末尾の1文字手前に加えてdp[i+1]を作る。
• S[i+1]とS[i+2]にRDまたはRUの順でdp[i]の末尾に2文字加えてdp[i+2]を作る。
• S[i+1]とS[i+2]にRLの順でdp[i]の末尾に2文字加えてdp[i+2]を作る。

int T,N,K;
string S;
string D[505];

char rot(char a) {
	char b=a+1;
	char c=a-1;
	if(b=='a'+K) b-=K;
	if(c=='a'-1) c+=K;
	return min({a,b,c});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>S;
		for(i=1;i<=N;i++) D[i]=string(i,'z');
		FOR(i,N) {
			D[i+1]=min(D[i+1],D[i]+rot(S[i]));
			if(i) D[i+1]=min(D[i+1],D[i].substr(0,i-1)+S[i]+D[i].back());
			if(i+2<=N) {
				if(i) D[i+2]=min(D[i+2],D[i].substr(0,i-1)+S[i+1]+D[i].back()+S[i]);
				D[i+2]=min(D[i+2],D[i]+rot(S[i+1])+S[i]);
			}
		}
		cout<<D[N]<<endl;
		
	}
}

まとめ

状態遷移のバリエーションが実はすごくシンプルに表せるのが面白い。