読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

yukicoder : No.238 Mr. K's Another Gift

yukicoder

最近の★3に比べると若干簡単ですが、最近yukicoderの難易度がインフレ傾向にある気もするので箸休めに良いかもしれませんね。
http://yukicoder.me/problems/591

問題

文字列Sが与えられる。
1文字追加してSを回文に出来るか。
出来るならその例を示せ。

解法

Sが元々回文の場合、(文字列長が奇数でも偶数でも)中央の文字を複製すればよい。

そうでない場合、先頭からS[i]!=S[|S|-1-i]となるiを1つ探す。

この場合、S[i]を複製してS[|S|-1-i]の後ろに挿入するか、S[|S|-1-i]を複製してS[i]の前に挿入しないとi文字目の部分が回文にならない。
よって両ケースの文字列を実際に生成してみて、回文判定すればよい。
どちらも回文でないなら解無し。

string S;
int L;

int palin(string SS) {
	int i;
	FOR(i,SS.size()) if(SS[i]!=SS[SS.size()-1-i]) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	if(palin(S)) {
		string T=S.substr(0,L/2)+S[L/2]+S.substr(L/2);
		cout<<T<<endl;
		return;
	}
	
	FOR(i,L) if(S[i]!=S[L-1-i]) {
		string T=S.substr(0,i)+S[L-1-i]+S.substr(i);
		if(palin(T)) {
			cout<<T<<endl;
			return;
		}
		T=S.substr(0,L-1-i+1)+S[i]+S.substr(L-1-i+1);
		if(palin(T)) {
			cout<<T<<endl;
			return;
		}
		break;
	}
	cout<<"NA"<<endl;
}

まとめ

最初回文判定の関数名をparlinと書いてしまった。
palindromeだからrは要らないのね。

広告を非表示にする