Kazun の競プロ記録

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

AtCoder Beginner Contest 303 C問題 Dash

AtCoder ABC ABC303 C問題 300 pts

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

問題

提出解答

問題の概要

座標平面上の点 $(0,0)$ に高橋君がいる. 最初, 高橋君の体力は $H$ である.

また, 座標平面上には $M$ 個のアイテムがあり, $j$ 番目のアイテムは点 $(x_j, y_j)$ にある.

高橋君はこれから $N$ 回行動する. $i$ 番目の行動は次のようにして行われる.

高橋君がこの瞬間にいる座標をとする. 体力を減らして, の文字目に応じて, 以下の点に移動する.
- $S_i={\tt R}$ のとき: $(x+1, y)$ に移動する.
- $S_i={\tt L}$ のとき: $(x-1, y)$ に移動する.
- $S_i={\tt U}$ のとき: $(x, y+1)$ に移動する.
- $S_i={\tt D}$ のとき: $(x, y-1)$ に移動する.
高橋君の体力が負になったならば, 高橋君は倒れてしまい, 移動を終了する. そうでなく, 移動した先にアイテムがあり, 高橋君の体力が $K$ 未満であるならば, 移動した先にあるアイテムを消費して, 体力を $K$ にする.

高橋君は $N$ 回の行動を完遂できるか?

制約

$1 \leq N,M,H,K \leq 2 \times 10^5$ .
$S$ は ${\tt R}, {\tt L}, {\tt U}, {\tt D}$ からなる長さ $N$ の文字列.
$\lvert x_j \rvert, \lvert y_j \rvert \leq 2 \times 10^5$
$(x_1, y_1), \dots, (x_M, y_M)$ は全て異なる.

解法

問題文にあるように, 各行動をシミュレーションして, 体力を管理すれば良い. ただし, 移動先にアイテムが存在するかどうかの判定については, 集合などのデータ構造を用いて高速化する必要がある. また, 細かい点について, 以下の点に注意すること.

順番どおりにシミュレーションすること.
負, $K$ 未満の境界に注意すること.
アイテムを使った場合, その点にあるアイテムは消える.
体力が $K$ 以上である場合, アイテムを消費しないことに注意する.