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

AtCoder Regular Contest 019:こだわりの名前

問題

文字列 s が与えられる。
s を一文字だけ変更した文字列 t を作る。しかし t が回文にならないようにしなければならない。
そのような変更の仕方は何通りあるか求める。

解法

length(s) == 1 ならばどのように文字を変更しても回文になってしまうので、そのような変更の仕方は0通りとなる。

s が既に回文ならば1文字変更すると回文でなくなるのでそのような変更の仕方は 25 \times length(s) となる。
しかし、length(s) が奇数で回文の時には、真ん中の文字を他の文字に変更しても回文になってしまうので注意が必要。f:id:Matchald:20160608115224p:plain

あとは、s が回文でない状態を考えれば良い。
s を1文字変更して回文になってしまうのは1つのペアのみが違う文字の時である。2ペア以上違う文字ならばどのように文字を1文字変更しても回文にはならない。
f:id:Matchald:20160608122328p:plain

C++のコード

#include<iostream>
#include<string>
#include<algorithm>

// 文字列 s が回文かどうかの判定
bool isPalindrome(std::string s) {
	std::string rev = s;
	std::reverse(rev.begin(), rev.end());

	return rev == s;
}

// 何ペア違うところがあるか
int changeCharNo(std::string s) {
	int start = 0, end = s.length() - 1, count = 0;
	while (start <= end) {
		if (s[start] != s[end]) count++;
		start++;
		end--;
	}
	return count;
}


int main() {
	std::string s;

	std::cin >> s;

	if (s.length() == 1) {
		std::cout << 0 << std::endl;
		return 0;
	}

	if (isPalindrome(s)) {
		long long ans = 25 * s.length();
		if (s.length() % 2 == 1) ans -= 25;
		std::cout << ans << std::endl;
		return 0;
	}

	long long ans;
	if (changeCharNo(s) == 1) {
		ans = 24 * 2 + (s.length() - 2) * 25;
	} else {
		ans = 25 * s.length();
	}

	std::cout << ans << std::endl;
	return 0;
}