AtCoder Regular Contest 155 A問題メモ

A - ST and TS Palindrome

問題

長さ $N$ の文字列 $S$ と整数 $K$ が与えられる
$S$ に対し、以下のような文字列 $S'$ を作れるか判定せよ
- 長さは $K$
- $SS'$ が回文になる
- $S'S$ が回文になる
$T$ ケース与えられるので、それぞれについて判定せよ
1つの入力に含まれる $N$ の総和 $\le 2 \times 10^5$
$1 \le K \le 10^{18}$

解法

$S'$ に自由度はなく、自動的に決まっていく。

SS'が回文になるためには、

[  S  ][                  S'                   ]

Sを逆にした文字列をZとして、末尾 N 文字が決まる

[  S  ][                  S'                   ]
       [                                 [  Z  ]

さらにS'Sも回文になるので先頭 N 文字も決まる

[                  S'                   ][  S  ]
[  Z  ]                                 ]

このとき、答えが存在するなら以下の2つが回文となるのだが、

SS' = [  S  ][  Z  ][            R            ][  Z  ]
S'S = [  Z  ][            R            ][  Z  ][  S  ]

両端から長さ $N$ を切り取ってみると、当然内側も回文となる。

             [  Z  ][            R            ]
             [            R            ][  Z  ]

さらにそれぞれひっくり返すと

             [            Я           ][  S  ]
             [  S  ][            Я           ]

この2つが回文となるような [ Я ] が存在することになる（ [ Я ] を新たな $S'$ とした問題になる）。

逆に、このような [ Я ] を構築することができれば、[ Z ][ R ][ Z ] を元の問題の $S'$ とすることができる。

つまり、長さ $2N$ 縮めた問題と、元の問題の答えは一致する。

これを繰り返すと、$K$ は $2N$ で割ったあまりにできて、そこまで短くなったら、実際に試しても $O(N)$ なので、十分高速。

SS'が回文 という条件から考えると、S' = [  S  ][  Z  ] から末尾 K 文字を取ったもの
S'Sが回文 という条件から考えると、S' = [  Z  ][  S  ] から先頭 K 文字を取ったもの

この2つが一致し、また、それぞれが回文になるかをチェックすればよい。

Python3

def is_palindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            return False
    return True


def solve(n, k, s):
    z = s[::-1]
    k %= 2 * n
    if k == 0:
        k = 2 * n
    szk = (s + z)[-k:]
    zsk = (z + s)[:k]
    return szk == zsk and is_palindrome(s + szk) and is_palindrome(zsk + s)


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    s = input()
    print('Yes' if solve(n, k, s) else 'No')

目次

AtCoder Regular Contest 155 A問題メモ

A - ST and TS Palindrome

問題

解法