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

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

ARC 019 B - こだわりの名前(2015/06/02)

問題

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


回答

Submission #418631 - AtCoder Regular Contest 019 | AtCoder


回文でない名前をつくってその組み合わせがどれくらいあるのかという問題.
まず,回文であるかどうかを確認する.

回文の場合
  • 文字列長が奇数

ABCBAのようなものの場合,真ん中のCはどう変えても回文になる.
しかし,それ以外の変更であればOK.pythonでかくならこう.

res += 25 * (len(name) - 1)
  • 文字列長が偶数

ABBAのようなもの.どこを変えても回文にはなりえない.

res += 25 * (len(name))
回文でない場合
  • 1つ文字を変えると回分になる可能性がある文

これが非常にめんどくさい.ABBCAがそれに当たる.
1文字目,3文字目,5文字目は25通りだが,2文字目,4文字目は24通り.
よって,この計算式で求める.

res += 25 * (len(name) - 2) + 24 * 2
  • それ以外の文

普通にどれでも置き換えできる.

res += 25 * len(name)

と,この4つの場合分けでOK.
わかりづらいですが,最初の変数kailengthは回文になる可能性があるかどうかを判断する変数です.
kailengthが0ならば回文,1ならば1文字変えれば回文になるように計算してます.
これにより,上記の分岐が可能になります.

というわけで,回答コードは以下のようになりました.
(公式の解説を読んでいないので,もしかしたらもっとスマートな解があるのかもしれません)

name = input()
kailength = 0
for i in range(len(name) // 2):
    if name[i] != name[-i-1]:
        kailength += 1
res = 0
if kailength == 1:
    res += 25 * (len(name) - 2) + 24 * 2
else:
    if kailength == 0 and len(name) % 2 == 1:
        res += 25 * (len(name) - 1)
    else:
        res += 25 * len(name)
 
print(res)