注意
本記事では Shortest Balanced Walk の問題文および公式解説の内容を前提としています．
定義，概要
入力されたグラフ上のウォークに対し，そのウォークが通った辺に書かれた文字を通過順に並べてできる括弧列のことを，そのウォークに対応する括弧列と呼びます．
括弧列の ネスト を，その括弧列に含まれる ( の個数から ) の個数を引いた値とします．
括弧列の 最高ネスト ，最低ネスト を，その括弧列の接頭辞のネストの最大値，最小値とします．
ウォークに対応する括弧列のネスト，最高ネスト，最低ネストをそれぞれ単にウォークのネスト，最高ネスト，最低ネストと呼びます．
良いウォーク を問題文の通りに定めます．
上の用語を用いれば，頂点 1 1 1 N N N 0 0 0
明らかに良いウォークの長さは偶数です．
ウォーク W W W W W W ∣ W ∣ |W| ∣ W ∣
本記事では次の解法を扱います（公式解説に倣って 解法 2 と呼びます）．
解法 2
d p v , s \mathrm{dp} _ {v, s} dp v , s 1 1 1 v v v s s s
この DP テーブルを初期値 d p 1 , 0 = 0 \mathrm{dp} _ {1, 0} = 0 dp 1 , 0 = 0 d p N , 0 \mathrm{dp} _ {N, 0} dp N , 0
ただしネスト s s s 0 ≤ s ≤ S 0 \le s \le S 0 ≤ s ≤ S O ( S M ) O(SM) O ( S M )
特に S S S S = N − 2 S = N - 2 S = N − 2 AC を得られることが紹介されています．
この解法 2 に関して，本記事では次の2点を証明します．
解法 2 で S = N − 2 S = N - 2 S = N − 2
解法 2 で S = 2 N − 1 S = 2N - 1 S = 2 N − 1
また有向グラフが与えられる場合についても述べます．
S = N − 2 S = N - 2 S = N − 2 5 ≤ N ≤ 200 5 \le N \le 200 5 ≤ N ≤ 200 S ≥ 2 N − 6 S \ge 2 N - 6 S ≥ 2 N − 6
頂点 2 , 1 , N , N − 1 , … , 6 , 5 2, 1, N, N-1, \dots, 6, 5 2 , 1 , N , N − 1 , … , 6 , 5 5 , 4 , 3 5, 4, 3 5 , 4 , 3 3 3 3 2 2 2 1 1 1 ( が書かれています．
証明
良いウォークの長さは偶数ですが 1 1 1 N N N 1 1 1 3 3 3 1 1 1 1 1 1 N N N
1 → N → N − 1 → ⋯ → 6 → 5 → 4 → 3 → 5 → 6 → ⋯ → N − 1 → N \begin{aligned}
1& \to N \\
& \to N-1 \to \dots \to 6 \to 5 \\
& \to 4 \to 3 \to 5 \\
& \to 6 \to \dots \to N - 1 \to N
\end{aligned}
1 → N → N − 1 → ⋯ → 6 → 5 → 4 → 3 → 5 → 6 → ⋯ → N − 1 → N
です．このウォークのネストは − ( 2 N − 6 ) -(2 N - 6) − ( 2 N − 6 ) 1 1 1 2 2 2 N − 3 N-3 N − 3
1 ( → 2 → 1 ) N − 3 → N → N − 1 → ⋯ → 6 → 5 → 4 → 3 → 5 → 6 → ⋯ → N − 1 → N \begin{aligned}
1& (\to 2 \to 1)^{N-3} \to N \\
& \to N-1 \to \dots \to 6 \to 5 \\
& \to 4 \to 3 \to 5 \\
& \to 6 \to \dots \to N - 1 \to N
\end{aligned}
1 ( → 2 → 1 ) N − 3 → N → N − 1 → ⋯ → 6 → 5 → 4 → 3 → 5 → 6 → ⋯ → N − 1 → N
が最短の良いウォークです．このウォークは 3 3 3 2 N − 6 2 N - 6 2 N − 6 S ≥ 2 N − 6 S \ge 2 N - 6 S ≥ 2 N − 6 □ \square □
S = 2 N − 1 S = 2N - 1 S = 2 N − 1 制約を満たす任意の入力において，実際に良いウォークが存在するならば，任意の最短の良いウォークに対し，その最高ネストは 2 N − 1 2 N - 1 2 N − 1
証明
制約を満たし，かつ良いウォークが存在する任意の単純連結無向グラフ G G G
頂点 1 1 1 ( が書かれた辺が存在する（この辺を e 1 e_1 e 1
頂点 N N N ) が書かれた辺が存在する（この辺を e N e_N e N
さて，G G G G ′ G' G ′
頂点集合：{ ( v , 0 ) ∣ 1 ≤ v ≤ N } ∪ { ( v , 1 ) ∣ 1 ≤ v ≤ N } \lbrace \, (v, 0) \, | \, 1 \le v \le N \, \rbrace \cup \lbrace \, (v, 1) \, | \, 1 \le v \le N \, \rbrace { ( v , 0 ) ∣ 1 ≤ v ≤ N } ∪ { ( v , 1 ) ∣ 1 ≤ v ≤ N }
辺集合：{ { ( u i , 0 ) , ( v i , 1 ) } ∣ 1 ≤ i ≤ M } ∪ { { ( u i , 1 ) , ( v i , 0 ) } ∣ 1 ≤ i ≤ M } \lbrace \, \lbrace (u_i, 0), (v_i, 1) \rbrace \, | \, 1 \le i \le M \, \rbrace \cup \lbrace \, \lbrace (u_i, 1), (v_i, 0) \rbrace \, | \, 1 \le i \le M \, \rbrace { {( u i , 0 ) , ( v i , 1 )} ∣ 1 ≤ i ≤ M } ∪ { {( u i , 1 ) , ( v i , 0 )} ∣ 1 ≤ i ≤ M }
仮定から G ′ G' G ′ ( 1 , 0 ) (1, 0) ( 1 , 0 ) ( N , 0 ) (N, 0) ( N , 0 ) パス P ′ P' P ′ P ′ P' P ′ 2 N − 1 2 N - 1 2 N − 1 2 N − 2 2 N - 2 2 N − 2
P ′ P' P ′ 1 1 1 G G G P P P P P P 2 N − 2 2 N - 2 2 N − 2
P P P p p p m m m P P P e 1 e_1 e 1 ⌈ − m / 2 ⌉ \lceil -m / 2 \rceil ⌈ − m /2 ⌉ m ≤ 0 m \le 0 m ≤ 0 0 0 0 P P P e N e_N e N p / 2 + ⌈ − m / 2 ⌉ p/2 + \lceil -m / 2 \rceil p /2 + ⌈ − m /2 ⌉ 0 0 0 W W W
∣ W ∣ = ∣ P ∣ + 2 ⌈ − m 2 ⌉ + 2 ( p 2 + ⌈ − m 2 ⌉ ) = ∣ P ∣ + 4 ⌈ − m 2 ⌉ + p |W| = |P| + 2 \left\lceil \frac{-m}{2} \right\rceil + 2 \left( \frac{p}{2} + \left\lceil \frac{-m}{2} \right\rceil \right)
= |P| + 4 \left\lceil \frac{-m}{2} \right\rceil + p
∣ W ∣ = ∣ P ∣ + 2 ⌈ 2 − m ⌉ + 2 ( 2 p + ⌈ 2 − m ⌉ ) = ∣ P ∣ + 4 ⌈ 2 − m ⌉ + p
です．ここで
∣ P ∣ ≥ ∣ 0 − m ∣ + ∣ m − p ∣ = − 2 m + p (1) |P| \ge |0 - m| + |m - p| = -2 m + p \tag{1}
∣ P ∣ ≥ ∣0 − m ∣ + ∣ m − p ∣ = − 2 m + p ( 1 )
および ∣ P ∣ ≤ 2 N − 2 |P| \le 2 N - 2 ∣ P ∣ ≤ 2 N − 2
∣ W ∣ = ∣ P ∣ + 4 ⌈ − m 2 ⌉ + p ≤ ∣ P ∣ + 4 ( − m + 1 2 ) + p = ∣ P ∣ − 2 m + p + 2 ≤ 2 ∣ P ∣ + 2 ≤ 4 N − 2. (2) \begin{aligned}
|W|
&= |P| + 4 \left\lceil \frac{-m}{2} \right\rceil + p \\
&\le |P| + 4 \left( \frac{-m + 1}{2} \right) + p \\
&= |P| - 2 m + p + 2 \\
&\le 2|P| + 2 \\
&\le 4N - 2. \\
\end{aligned} \tag{2}
∣ W ∣ = ∣ P ∣ + 4 ⌈ 2 − m ⌉ + p ≤ ∣ P ∣ + 4 ( 2 − m + 1 ) + p = ∣ P ∣ − 2 m + p + 2 ≤ 2∣ P ∣ + 2 ≤ 4 N − 2. ( 2 )
以上で長さが 4 N − 2 4 N - 2 4 N − 2
最短の良いウォーク W ⋆ W^\star W ⋆ ∣ W ⋆ ∣ ≤ ∣ W ∣ ≤ 4 N − 2 |W^\star| \le |W| \le 4N-2 ∣ W ⋆ ∣ ≤ ∣ W ∣ ≤ 4 N − 2 W ⋆ W^\star W ⋆ ∣ W ⋆ ∣ / 2 |W^\star|/2 ∣ W ⋆ ∣/2 2 N − 1 2 N - 1 2 N − 1 □ \square □
なお，より詳細な観察により S = 2 N − 2 S = 2 N - 2 S = 2 N − 2 S ≥ 2 N − 1 S \ge 2 N - 1 S ≥ 2 N − 1
証明
記号等は上の証明ブロックから引き継ぎます．
N = 2 N = 2 N = 2 G G G N ≥ 3 N \ge 3 N ≥ 3
∣ W ∣ = 4 N − 2 |W| = 4 N - 2 ∣ W ∣ = 4 N − 2 ( 2 ) (2) ( 2 )
m m m ∣ P ∣ = p − 2 m |P| = p - 2 m ∣ P ∣ = p − 2 m ∣ P ∣ = 2 N − 2 |P| = 2N - 2 ∣ P ∣ = 2 N − 2
が全て成り立ちます．
∣ P ′ ∣ = 2 N − 2 |P'| = 2N - 2 ∣ P ′ ∣ = 2 N − 2 P ′ P' P ′ G ′ G' G ′ 1 1 1 ( v , 1 ) (v, 1) ( v , 1 )
ところで G G G e 1 = { 1 , a } e_1 = \lbrace 1, a \rbrace e 1 = { 1 , a } G ′ G' G ′ e 1 ′ = { ( 1 , 0 ) , ( a , 1 ) } e_1' = \lbrace (1, 0), (a, 1) \rbrace e 1 ′ = {( 1 , 0 ) , ( a , 1 )} ( a , 1 ) (a, 1) ( a , 1 ) P ′ P' P ′ P ′ P' P ′ e 1 ′ e_1' e 1 ′ P ′ P' P ′ ( 1 , 0 ) (1, 0) ( 1 , 0 )
同様に，G G G e N = { b , N } e_N = \lbrace b, N \rbrace e N = { b , N } G ′ G' G ′ e N ′ = { ( b , 1 ) , ( N , 0 ) } e_N' = \lbrace (b, 1), (N, 0) \rbrace e N ′ = {( b , 1 ) , ( N , 0 )} ( b , 1 ) (b, 1) ( b , 1 ) P ′ P' P ′ P ′ P' P ′ ( N , 0 ) (N, 0) ( N , 0 )
以上より P ′ P' P ′ ( a , 1 ) , ( b , 1 ) (a, 1), (b, 1) ( a , 1 ) , ( b , 1 ) P ′ P' P ′ ( a , 1 ) , ( b , 1 ) (a, 1), (b, 1) ( a , 1 ) , ( b , 1 ) a = b a = b a = b e 1 ′ , e N ′ e_1', e_N' e 1 ′ , e N ′ ( 1 , 0 ) (1, 0) ( 1 , 0 ) ( N , 0 ) (N, 0) ( N , 0 ) 2 2 2 P ′ P' P ′
すなわち P P P ( であるか，または末尾が ) です．
一方 ∣ P ∣ = p − 2 m |P| = p - 2 m ∣ P ∣ = p − 2 m ( 1 ) (1) ( 1 ) P P P
) ⋯ ) ⏟ − m ( ⋯ ( ⏟ p − m \underbrace{\texttt{)} \dotsb \texttt{)}}_{-m} \underbrace{\texttt{(} \dotsb \texttt{(}}_{p - m}
− m ) ⋯ ) p − m ( ⋯ (
となります．ここで m m m p p p ) も ( も 1 1 1
したがって ∣ W ∣ = 4 N − 2 |W| = 4 N - 2 ∣ W ∣ = 4 N − 2 ∣ W ∣ |W| ∣ W ∣ ∣ W ∣ ≤ 4 N − 4 |W| \le 4 N - 4 ∣ W ∣ ≤ 4 N − 4 2 N − 2 2 N - 2 2 N − 2 □ \square □
（余談）有向グラフが与えられる場合
ここでは次のような入力制約を考えています．
入力の ( u i , v i , c i ) (u_i, v_i, c_i) ( u i , v i , c i ) c i c_i c i u i u_i u i v i v_i v i
u i , v i ∈ [ 1 , N ] u_i, v_i \in [1, N] u i , v i ∈ [ 1 , N ] u i ≠ v i u_i \ne v_i u i = v i i ≠ j → ( u i , v i ) ≠ ( u j , v j ) i \ne j \to (u_i, v_i) \ne (u_j, v_j) i = j → ( u i , v i ) = ( u j , v j ) 1 1 1 N N N
必要性
k ≥ 3 , N = 2 k + 1 k \ge 3, N = 2k + 1 k ≥ 3 , N = 2 k + 1 S ≥ k ( k + 1 ) = ( N 2 − 1 ) / 4 S \ge k(k + 1) = (N^2-1)/4 S ≥ k ( k + 1 ) = ( N 2 − 1 ) /4
つまり頂点 1 , 2 , … , k 1, 2, \dots, k 1 , 2 , … , k k k k k + 1 , k + 2 , … , N k+1, k+2, \dots, N k + 1 , k + 2 , … , N ( k + 1 ) (k+1) ( k + 1 ) 1 1 1 k + 1 k+1 k + 1 e e e
証明
良いウォークは k k k x x x e e e ( k + 1 ) (k+1) ( k + 1 ) N N N ( k + 1 ) (k+1) ( k + 1 ) y y y x = 0 x = 0 x = 0 ) から始まってしまうので x ≥ 1 x \ge 1 x ≥ 1 0 0 0
k x = 1 + k + ( k + 1 ) y kx = 1 + k + (k+1)y
k x = 1 + k + ( k + 1 ) y
です．この方程式の整数解は
( x , y ) = ( ( k + 1 ) i , k i − 1 ) ( i ∈ Z ) (x, y) = ((k + 1)i, ki - 1) \quad (i \in \mathbb{Z})
( x , y ) = (( k + 1 ) i , k i − 1 ) ( i ∈ Z )
で，特に x ≥ 1 , y ≥ 0 x \ge 1, y \ge 0 x ≥ 1 , y ≥ 0
( x , y ) = ( k + 1 , k − 1 ) (x, y) = (k + 1, k - 1)
( x , y ) = ( k + 1 , k − 1 )
です．このとき最高ネストは
k x = k ( k + 1 ) = N 2 − 1 4 kx = k (k + 1) = \frac{N^2 - 1}{4}
k x = k ( k + 1 ) = 4 N 2 − 1
です．
十分性
S = N 2 S = N^2 S = N 2
証明
最短の良いウォーク W W W W W W
1 = w 0 → w 1 → ⋯ → w L = N 1 = w_0 \to w_1 \to \dots \to w_L = N
1 = w 0 → w 1 → ⋯ → w L = N
とします．W W W s s s
[ 0 , L ] ⊇ [ l 1 , r 1 ] ⊋ [ l 2 , r 2 ] ⊋ ⋯ ⊋ [ l s , r s ] = [ l s , l s + 2 ] [0, L] \supseteq [l_1, r_1] \supsetneq [l_2, r_2] \supsetneq \dots \supsetneq [l_s, r_s] = [l_s, l_s + 2]
[ 0 , L ] ⊇ [ l 1 , r 1 ] ⊋ [ l 2 , r 2 ] ⊋ ⋯ ⊋ [ l s , r s ] = [ l s , l s + 2 ]
であって，任意の i i i W W W l i + 1 l_i + 1 l i + 1 ( と r i r_i r i ) が対応しているものを取ることができます．
このとき，( w l i , w r i ) = ( w l j , w r j ) , 1 ≤ i < j ≤ s (w_{l_i}, w_{r_i}) = (w_{l_j}, w_{r_j}), 1 \le i < j \le s ( w l i , w r i ) = ( w l j , w r j ) , 1 ≤ i < j ≤ s i , j i, j i , j [ l i , r i ] [l_i, r_i] [ l i , r i ] [ l j , r j ] [l_j, r_j] [ l j , r j ] W W W W W W W W W
したがって頂点の組 ( w l i , w r i ) (w_{l_i}, w_{r_i}) ( w l i , w r i ) N 2 N^2 N 2 s ≤ N 2 s \le N^2 s ≤ N 2 S = N 2 S = N^2 S = N 2 □ \square □