Shortest Balanced Walk

解説

解法 $1$

空文字列に以下の $2$ 種類の操作を $0$ 回以上繰り返し行うことで任意の正しいかっこ列を作ることができます。

• 先頭に (、末尾に ) を加える
• 先頭か末尾に空でない正しいかっこ列を連結する

これを利用して、次のように $\text{dp}$ を定義します。

• $\text{dp}_{u,v} \coloneqq$ 頂点 $u$ を始点、頂点 $v$ を終点とする良いウォークの長さとしてありえる値の最小値

まず $\text{dp}_{u,v}=\begin{cases}0 & u=v\\\infty & u \ne v\end{cases}$ と初期化します。

$\text{dp}_{u,v}$ から、次のように遷移できます。

• 頂点 $u$ と頂点 $u'$ の間に ( が書かれた辺があり、頂点 $v$ と 頂点 $v'$ の間に ) が書かれた辺があるとき、$\text{dp}_{u',v'}=\min(\text{dp}_{u',v'},\text{dp}_{u,v}+2)$

• $u' \ne u$ を満たす $u'$ について、$\text{dp}_{u',v}=\min(\text{dp}_{u',v},\text{dp}_{u',u}+\text{dp}_{u,v})$

• $v' \ne v$ を満たす $v'$ について、$\text{dp}_{u,v'}=\min(\text{dp}_{u,v'},\text{dp}_{u,v}+\text{dp}_{v,v'})$

これらの遷移を、確定した $\text{dp}$ の値が小さい順に処理することで、ダイクストラ法と同様に最小値を求めることができます。

最終的に、 $\text{dp}_{1,N}$ がこの問題の答えです。 $\text{dp}_{1,N}=\infty$ の場合、良いウォークは存在しません。

計算量は、 $\text{dp}$ の遷移に優先度付きキューを用いることで $O((N^3+M^2)\log(N^3+M^2))$ になります。

解答例 (C++)

解答例 (Python)

解法 $2$

かっこ列の 深さ を、かっこ列に含まれる ( の数から ) の数を引いたものと定義します。

かっこ列 $X$ が正しいかっこ列であることは以下の両方が成り立つことと同値です。

• $X$ の任意の接頭辞 $Y$ について、 $Y$ の深さは $0$ 以上
• $X$ の深さは $0$

これを利用して、次のように $\text{dp}$ を定義します。

• $\text{dp}_{v,s}\coloneqq$ 頂点 $1$ を始点、頂点 $v$ を終点とし、変換後の数列の総和が $s$ となるウォークの最短長

まず、 $\text{dp}_{v,s} = \begin{cases}0 & (v,s)=(1,0)\\\infty&(v,s)\ne(1,0)\end{cases}$ と初期化します。

$\text{dp}_{v,s}$ から、次のように遷移できます。

• 頂点 $u,v$ の間に ( が書かれた辺があるとき、$\text{dp}_{u,s+1}=\min(\text{dp}_{u,s+1},\text{dp}_{v,s}+1)$
• $s \gt 0$ かつ、頂点 $u,v$ の間に ) が書かれた辺があるとき、$\text{dp}_{u,s-1}=\min(\text{dp}_{u,s-1},\text{dp}_{v,s}+1)$

最終的に、 $\text{dp}_{N,0}$ がこの問題の答えです。$\text{dp}_{1,N}=\infty$ の場合、良いウォークは存在しません。

ウォークに対応するかっこ列の深さは大きくなり続けることがあるため、上限 $S$ を設定して遷移を打ち切る必要があります。

$S \geq N-2$ で十分な可能性があるとしていましたが、以下の記事で $S=N-2$ が正当ではなく、 $S=2N-1$ が正当であることの証明を公開してくださいました。ありがとうございます。

Shortest Balanced Walk 解法 2 の正当性 (by wasd314)

証明の概要

良いウォークが存在するならば、以下が成り立ちます。

• 頂点 $1$ を始点、頂点 $N$ を終点とする偶数長のウォークが存在する
• 頂点 $1$ を端点としてラベル ( を持つ辺がある
• 頂点 $N$ を端点としてラベル ) を持つ辺がある

逆に、これらが成り立つとき、偶数長のウォークの先頭と末尾に辺を追加して良いウォークを構成することができます。そのようにして構成される良いウォークの長さを見積もると $4N-2$ 以下になるので、 $S=2N-1$ で十分です。

計算量は $O(SM)$ です。

解答例 (C++)

解答例 (Python)