Kazun の競プロ記録

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

AtCoder Beginner Contest 266 D問題 Snuke Panic

AtCoder ABC266 ABC D問題 400 pts

問題

提出解答

問題の概要

数直線上に高橋くんがいる. 座標 $0,1,2,3,4$ に穴があいている. あなたは時刻 $0$ に穴 $0$ にいる. そして, あなたは数直線上を速さ $1$ 以下で移動できる.

また, $N$ 匹のモグラが穴からでて, $i$ 番目のモグラは時刻 $T_i$ に穴 $X_i$ から出て, その時刻にその場所にいるとき, そしてその時に限りそのモグラを叩くことができ, 叩くと $A_i$ 点貰える.

最大何点貰えるか?

制約

$1 \leq N \leq 10^5$
$1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^5$
$0 \leq X_i \leq 4$
$1 \leq A_i \leq 10^9$

解法

動的計画法で解く. ${\rm DP}[t,x ]$ で時刻 $t$ で座標 $x$ にいるような移動の方法における得点の最大値とする. そして, $B_{t,x}$ で時刻 $t$ に座標 $x$ からモグラが出ればそのモグラの点数, そうでなければ $0$ とする.

まず, ベースケースとしては $t=0$ のときで

${\rm DP}[0,0]=0, \quad {\rm DP}[0,1]={\rm DP}[0,2]={\rm DP}[0,3]={\rm DP}[0,4]=-\infty$

である.

更新式は時刻 $t$ に座標 $x$ にいるためには時刻 $(t-1)$ の時点で $x-1, x, x+1$ のいずれかにいなければならないので,

$\displaystyle{\rm DP}[t,x]=\max_{\substack{y \in \{x-1,x,x+1\} \\ 0 \leq y \leq 4}} {\rm DP}[t-1,y]+B_{t,x}$

である.

これにより, 求めるべき最終解答は

$\displaystyle \max_{x=0,1,2,3,4} {\rm DP}[T_N,x]$

である. 時間計算量は $O(T_N)$ 時間である.