Codeforces #277 Div2 C. Palindrome Transformation

CF277に参加。
Dに若干時間を食ったものの、CはFA取れたし上々の出来。
http://codeforces.com/contest/486/problem/C

問題

N文字の文字列Sが与えられる。
初期状態ではP番目の文字にカーソルが当たっている。

この状態において、上下左右キーを１回押すと以下の処理が行われる。

• 左右キーを押すと、文字列中で隣接する文字の位置にカーソルが動く(先頭と末尾は循環しない)
• 上下キーを押すと、カーソル位置の文字が１つ次もしくは前の文字になる。(aとzは循環する)

Sを回文にするのに必要なカーソルの最小処理回数を答えよ。

解法

回文ということはS[i]==S[N-1-i]にするわけだが、両者をそろえるにはS[i]で上下キーを押してもS[N-1-i]で上下キーどちらを押しても回数は同じである。

よって、Pが前半ならSの前半の範囲だけ、Pが後半ならSの後半の範囲だけ動かせばよい。
ここでは簡略化のため、PがSの後半を示すならPを反転し、前半を示すようにした。

まず上下キーの回数を求める。
これはi＜N/2においてS[i]==S[N-1-i]とするための上下キー押下回数の総和を求めるだけである。

次に、S[i]の前半のうち、初期状態でS[i]!=S[N-1-i]だったiの左端Lと右端Rを求める。
カーソルはL～Rの範囲を左右に動く必要がある。
そのためには(R-L)+min(|R-P|,|P-L|)だけ動けばよい。
例外として、初期状態ですでにSが回文の場合は、何もしなくてよい。

int N,P;
string S;
ll ret;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P>>S;
	P--;
	if(P>=N/2) P=N-1-P;

	l=r=-1;
	FOR(i,N/2) if(S[i]!=S[N-1-i]) {
		if(l==-1) l=i;
		r=i;
		j=(26+S[i]-S[N-1-i])%26;
		ret+=min(j,26-j);
	}

	if(l==-1) return _P("0\n");
	cout<<ret + (r-l) + min(abs(r-P),abs(P-l))<<endl;

}

まとめ

これはあっさり。