概要
公式解説の手法が派手でびっくりしました。
かなり簡単に解けるので、書いておきます。
解法
問題文で与えられる数列を逆順に並べたものを $A$ とすると、問題は次のように言い換えられます。
数列 $A$ が与えられる。文字列 $S$ に対する Z アルゴリズムの出力が $A$ に一致するような $S$ が存在するかどうか判定せよ。
というわけで、Z アルゴリズムを観察することで解きましょう。
Z アルゴリズムによる計算結果は、$O(N)$ 回の文字比較により決定されます。そこで、Z アルゴリズムの計算をなぞりながら、$A$ が出力されるためには「この文字とこの文字は一致しているべき」「異なっているべき」を決定することができます。
本問題を解く上では、Z アルゴリズムの仕組みをよく理解していて自力で書ける必要すらありません。適当な既存実装を見ながら、その通りの結果を再現できるような $S$ の条件をリストアップしていけばよいです。（この問題ではそうというだけで、上を目指すのであればアルゴリズムの仕組みを理解しておくことは有益だと思います。）
Z アルゴリズムの実装
ちょっとこの問題に合わせていじっています。以下が実装例です。
def Z_algorithm(S):
N = len(S)
Z = [0] * N
Z[0] = N
i, j = 1, 0
while i < N:
while i + j < N:
if S[j] == S[i+j]:
j += 1
else:
break
Z[i] = j
if j == 0:
i += 1
continue
k = 1
while i + k < N and k + Z[k] < j:
Z[i + k] = Z[k]
k += 1
i += k
j -= k
return ZZ アルゴリズムの逆問題の実装
def Z_inv(Z):
N = len(Z)
if Z[0] != N:
return False
EQ = [] # 一致を要請する添字対
NEQ = [] # 不一致を要請する添字対
i, j = 1, 0
while i < N:
while i + j < N:
# j += 1 を実行したいかどうか
if Z[i] != j:
EQ.append((j, i + j))
else:
NEQ.append((j, i + j))
break
if Z[i] != j:
return False
if j == 0:
i += 1
continue
k = 1
while i + k < N and k + Z[k] < j:
if Z[i + k] != Z[k]:
return False
k += 1
i += k
j -= k
"""
以下、
i, j in EQ に対して S[i] == S[j] であり、
i, j in NEQ に対して S[i] != S[j] であるような
文字列 S が存在するかを判定する
""""Z アルゴリズムの実装をたどりながら、文字比較による条件分岐を行うところでは、欲しい出力が得られるための比較結果を条件として追加します。$Z[i]$ に値を書き込むところでは、正しい値になっていなかったら文字列の非存在が判定できます。
Z アルゴリズムをなぞって $S[i] = S[j]$ あるいは $S[i]\neq S[j]$ の形の条件をリストアップするところは、Z アルゴリズムと同様、線形時間で行えます。最後に Disjoint Set Union を使って判定を行えばよく、本問題は全体として $O(N\alpha(N))$ 時間で解くことができます。
コメント
Z アルゴリズムについて何も知らなくても良いというわけではなくて、$Z[i]$ は一度確定したら上書きされないという程度のことは必要ですね。計算結果の途中で使われるものが、$S$ の文字の比較と出力される値しかないところがポイントです。
公式解説の手法も高度で面白かったので、そちらも見てみると面白いと思います。
