問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次の条件を全て満たすような座標平面上の点の列 $({\rm P}_0, {\rm P}_1, \dots, {\rm P}_N)$ は存在するか? *1

${\rm P}_0=(0,0)$
${\rm P}_1=(A_1, 0)$
${\rm P}_N=(x,y)$
${\rm P}_{i-1}, {\rm P}_{i}$ 間の距離は $A_i$ である. $(1 \leq i \leq N)$
線分 ${\rm P}_{i-1}{\rm P}_i$ と線分 ${\rm P}_i{\rm P}_{i+1}$ の成す角は $90^\circ$ である. $(1 \leq i \leq N-1)$

制約

$2 \leq N \leq 10^3$
$1 \leq A_i \leq 10$
$|x|,|y| \leq 10^4$

解法

線分 ${\rm P}_{i-1}{\rm P}_i$ と線分 ${\rm P}_i{\rm P}_{i+1}$ の成す角は $90^\circ$ であり, ${\rm P}_0=(0,0), {\rm P}_1=(A_1, 0)$ であるから, 線分 ${\rm P}_{i-1}{\rm P}_i$ について次のことがわかる.

$i$ が奇数ならば, 線分 ${\rm P}_{i-1}{\rm P}_i$ は長さ $A_i$ で $x$ 軸に平行である.
$i$ が偶数ならば, 線分 ${\rm P}_{i-1}{\rm P}_i$ は長さ $A_i$ で $y$ 軸に平行である.

また, ${\rm P}_0=(0,0), {\rm P}_1=(A_1, 0)$ で, 今述べた条件を満たすような点列については元で要求されている条件のうち, ${\rm P}_N=(x,y)$ 以外の条件を全て満たす.

このことから, 次の問題に帰着される.

次を満たすような $\sigma_j, \tau_j \in \{1,-1\}$ は存在するか?

$\sigma_1 A_1+\sigma_3 A_3+\dots+\sigma_5 A_5+\dots=x, \quad \sigma_1=1$
$\tau_2 A_2+\tau_4 A_4+\dots+\tau_6 A_6+\dots=y$

上の問題についても $\sigma_1=1$ より, $\sigma_1 A_1$ を移項させることによって, 次のような問題を2回解けば良い.

次を満たすような $\alpha_i \in \{1,-1\}$ は存在するか?

$\alpha_1 B_1+\dots+\alpha_k B_k=M$

動的計画法で解くことにする. ${\rm DP}[i,m ]$ を次のようにして定義する.

$\alpha_1 B_1+\dots+\alpha_i B_i=m$ となる $\alpha_i \in \{1,-1\}$ が存在すれば $\mathbb{T}$ , 存在しなければ $\mathbb{F}$ .

ベースケースは $i=0$ のときで,

${\rm DP}[0,m]=\begin{cases} \mathbb{T} & (m=0) \\ \mathbb{F} & (m \neq 0) \end{cases}$

である.

更新式についても $\alpha_i$ をどちらに割り当てるかを考えることによって,

${\rm DP}[i,m]={\rm DP}[i-1, m-B_i] \lor {\rm DP}[i-1, m+B_i]$

である.

これにより, ${\rm DP}[k,M]$ が結果になる.

このとき, ${\rm DP}[i,m]=\mathbb{T}$ となり得る $(i,m)$ の個数は高々 $2N(B_1+\dots+B_k)+1$ 個である. よって, $m$ を $B_{{\rm sum}}:=B_1+\dots+B_k$ として, $-B_{{\rm sum}} \leq m \leq B_{{\rm sum}}$ の範囲に絞ればよい.