AtCoder Regular Contest 155 A問題メモ

AtCoder Regular Contest 155

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