AtCoder Beginner Contest 303 C問題 Dash
問題
提出解答
問題の概要
座標平面上の点 に高橋君がいる. 最初, 高橋君の体力は
である.
また, 座標平面上には 個のアイテムがあり,
番目のアイテムは点
にある.
高橋君はこれから 回行動する.
番目の行動は次のようにして行われる.
- 高橋君がこの瞬間にいる座標を
とする. 体力を
減らして,
の
文字目
に応じて, 以下の点に移動する.
のとき:
に移動する.
のとき:
に移動する.
のとき:
に移動する.
のとき:
に移動する.
- 高橋君の体力が負になったならば, 高橋君は倒れてしまい, 移動を終了する. そうでなく, 移動した先にアイテムがあり, 高橋君の体力が
未満であるならば, 移動した先にあるアイテムを消費して, 体力を
にする.
高橋君は 回の行動を完遂できるか?
制約
.
は
からなる長さ
の文字列.
は全て異なる.
解法
問題文にあるように, 各行動をシミュレーションして, 体力を管理すれば良い. ただし, 移動先にアイテムが存在するかどうかの判定については, 集合などのデータ構造を用いて高速化する必要がある. また, 細かい点について, 以下の点に注意すること.
- 順番どおりにシミュレーションすること.
- 負,
未満の境界に注意すること.
- アイテムを使った場合, その点にあるアイテムは消える.
- 体力が
以上である場合, アイテムを消費しないことに注意する.