Kazun の競プロ記録

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

AtCoder Beginner Contest 245 C問題 Choose Elements

AtCoder ABC ABC245 C問題 300 pts

問題

提出解答

問題の概要

長さ $N$ の正の整数列 $A=(A_i)_{i=1}^N, B=(B_i)_{i=1}^N$ が与えられる.

以下を満たす非正の整数列 $X=(X_i)_{i=1}^N$ は存在するか?

$X_i=A_i$ または $X_i=B_i$
$|X_{i-1}-X_i| \leq K$

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq K \leq 10^9$
$1 \leq A_i, B_i \leq 10^9$

解法

$X$ を $X_1, X_2, \dots, X_N$ の順で決めていこうとすると, $X_i$ の決定に必要な情報は $X_{i-1}$ だけである. また, $X_{i-1}=A_{i-1}$ か $X_{i-1}=B_{i-1}$ であることから, 次のような動的計画法を建てる事ができる.

${\rm DP}[i][\{A,B\}]:=X_1, \dots, X_i$ まで決定して, $X_i=A_i~(X_i=B_i)$ となるものが存在するか?

ベースケースは $i=1$ のときで, $X_1=A_1, X_1=B_1$ どちらもできるので,

${\rm DP}[1][A]={\rm DP}[1][B]=\mathbb{T}$

である.

また, 遷移式は

${\rm DP}[i][A]=([|A_{i-1}-A_i| \leq K ] \land {\rm DP}[i-1][A]) \lor ([|B_{i-1}-A_i| \leq K ] \land {\rm DP}[i-1][B])$

${\rm DP}[i][B]=([|A_{i-1}-B_i| \leq K ] \land {\rm DP}[i-1][A]) \lor ([|B_{i-1}-B_i| \leq K ] \land {\rm DP}[i-1][B])$

となる.

そして, 最終判定は ${\rm DP}[N][A] \lor {\rm DP}[N][B]$ である.

以上の動的計画法により, 時間計算量 $O(N)$ で判定できた.