牛客小白月赛138 B - Is it Palidrome?
- サイト
- NowCoder
- コンテスト
- 牛客小白月赛138
- 問題
- B - Is it Palidrome?
英小文字と ? からなる長さ の文字列 があります。それぞれの ? を好きな英小文字に置き換えます。
- どう置き換えても回文になるなら
certainly - どう置き換えても回文にならないなら
impossible - 回文になる置き換え方とならない置き換え方の両方があるなら
possible
を出力してください( の総和 )。
回文かどうかは、左右対称な位置にある文字のペア ()がすべて等しいかどうかで決まります。そこで、ペアを次の 3 種類に分けます。
- どちらも英小文字で、異なる:どう置き換えてもこのペアは等しくならないので、回文にはなりません。
- 少なくとも一方が
?:?の置き換え方しだいで、等しくすることも異なるものにすることもできます。 - どちらも英小文字で、等しい:どう置き換えてもこのペアは等しいままです。
ペアごとの ? の置き換えは互いに独立に選べるので、答えは次のようになります。
- 異なる英小文字のペアが 1 つでもあれば
impossible - そうでなく、
?を含むペアが 1 つでもあればpossible(すべてのペアを等しくすることも、そのペアだけを異なるものにすることもできる) - どちらでもなければ
certainly
が奇数のときの真ん中の文字はどのペアにも入らないので、? であっても回文かどうかに影響しません。3 つ目のサンプル xy?yx が certainly になるのはこのためです。
計算量は です。
Python
for _ in range(int(input())): N = int(input()) S = input() p = False ng = False for i in range(N//2): if S[i] == "?": p = True continue if S[N-i-1] == "?": p = True continue if S[i] != S[N-i-1]: ng = True continue if ng: print("impossible") elif p: print("possible") else: print("certainly")p は ? を含むペアがあるか、ng は異なる英小文字のペアがあるかを表します。ループを N//2 までにしているので、真ん中の文字は自然に見ないことになります。