Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 155 A問題 ST and TS Palindrome

AtCoder ARC155 ARC A問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ N の英小文字 S が与えられる. S \oplus X, X \oplus S ( \oplus の定義は後述の解答にて) が回分になるような長さ K の英小文字列は存在するか?

T 個のマルチケース

制約

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • T 個の N の総和は 2 \times 10^5 以下である.

解法

文字列 A,B に対して, 以下のように定義する.

  • A \oplus B で A,B をこの順に連結させた文字列
  • \overline{A} で A を反転させた文字列
  • \lvert A \rvert に対して, A を反転させた文字列
  • 1 \leq l \leq r \leq \lvert A \rvert に対して, A[l:r ] で A の l 文字目から r 文字目を取り出した文字列

S \oplus X が回分であることから, X の先頭 \min(N,K) 文字が \overline{S} の先頭 \min(N,K) 文字と一致する. 同様にして, X \oplus S が回分であるから, X の末尾 \min(N,K) 文字が \overline{S} の末尾 \min(N,K) 文字と一致する.

このことによって, K \leq 2N ならば, X の必要条件が一意に定まる.

K \gt 2N のとき, 次のようにして同値変形をする.

\begin{align*} & \exists X ~{\rm s.t.}~\lvert X \rvert=K, \begin{cases} S \oplus X=\overline{S \oplus X} \\ X \oplus S=\overline{X \oplus S} \end{cases} \\ & \iff \exists X ~{\rm s.t.}~\lvert X \rvert=K, \begin{cases} S \oplus X=\overline{X} \oplus \overline{S} \\ X \oplus S=\overline{S} \oplus \overline{X} \end{cases} \\ & \iff \exists Y~{\rm s.t.}~\lvert Y \rvert=K-2N, \begin{cases} S \oplus \overline{S} \oplus Y \oplus \overline{S}=S \oplus \overline{Y} \oplus S \oplus \overline{S} \\ \overline{S} \oplus Y \oplus \overline{S} \oplus S=\overline{S} \oplus S \oplus \overline{Y} \oplus S \end{cases} \\ & \iff \exists Y~{\rm s.t.}~\lvert Y \rvert=K-2N, \begin{cases} \overline{S} \oplus Y =\overline{Y} \oplus S \\ Y \oplus \overline{S}=S \oplus \overline{Y} \end{cases} \\ & \iff \exists Z~{\rm s.t.}~\lvert Z \rvert=K-2N, \begin{cases} \overline{S} \oplus \overline{Z} =Z \oplus S \\ \overline{Z} \oplus \overline{S}=S \oplus Z \end{cases} \\ & \iff \exists Z~{\rm s.t.}~\lvert Z \rvert=K-2N, \begin{cases} Z \oplus S=\overline{S} \oplus \overline{Z} \\ S \oplus Z=\overline{Z} \oplus \overline{S} \end{cases} \\ & \iff \exists Z~{\rm s.t.}~\lvert Z \rvert=K-2N, \begin{cases} Z \oplus S=\overline{Z \oplus S} \\ S \oplus Z=\overline{S \oplus Z} \end{cases} \\ & \iff \exists Z~{\rm s.t.}~\lvert Z \rvert=K-2N, \begin{cases} S \oplus Z=\overline{S \oplus Z} \\ Z \oplus S=\overline{Z \oplus S} \end{cases} \\ \end{align*}

であるから, K を K \mod{2N} に置き換えても同値性が保たれる.

よって, K \leq 2N の場合を解けば良く, これは O(N) 時間で判定することができる.