Kazun の競プロ記録

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

AtCoder Beginner Contest 289 D問題 Step Up Robot

AtCoder ABC289 ABC 400 pts D問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

無限に続く階段がある. 一番下は $0$ 段目で, それ以降は $k$ 段目の1段上は $(k+1)$ 段目と呼ばれている.

最初, $0$ 段目にいる.

以下の行動を繰り返し行う事ができる.

$k$ 段目にいるとき, $1$ 以上 $N$ 以下の整数 $i$ を選び, $(k+A_i)$ 段目に一回でジャンプする.

ただし, $B_1, \dots, B_M$ 段目にはモチが設置されており, モチが設置されている段に登ると, それ以降の移動は不可能になってしまう.

$X$ 段目ちょうどに移動することは可能か?

制約

$1 \leq N \leq 10$
$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq B_1 \lt B_2 \lt \dots \lt B_M \lt X \leq 10^5$

解法

$k=0,1,2 \dots, X$ に対して, $k$ 段目にモチがあるならば $C_k=1$ , そうでなければ $C_k=0$ とする.

動的計画法で解く. $k=0,1,2, \dots, X$ に対して, ${\rm DP}[k]$ で $k$ 段目に登る方法が存在するならば ${\rm DP}[k]=\mathbb{T}$ , 存在しないならば ${\rm DP}[k]=\mathbb{F}$ とする.

ベースケースは $k=0$ のときで, ${\rm DP}[0]=\mathbb{T}$ である.

更新式については直前の行動について場合分けをすることによって,

$\displaystyle {\rm DP}[k]=\bigvee_{\substack{1 \leq i \leq N \\ C_{k-A_i}=0}} {\rm DP}[k-A_i]$

となる.

これにより, 求めるべきは ${\rm DP}[X]$ である. 更新式が各 $k$ に対して, $O(K)$ 時間であるから, 全体では $O(M+NX)$ 時間で求める事ができる.