問題概要

高橋くんは最初、体力は $H$ であり、二次元平面上の座標 $(0, 0)$ にいる。

高橋くんは今から $N$ 回の移動を行う。高橋くんの移動方法は長さ $N$ の文字列 $S$ で表される。1 回の移動は、上下左右のいずれかであり、それぞれ文字 'U'、'D'、'L'、'R' で表されている。

二次元平面上には $M$ 個のアイテムがある。 $i$ 個目のアイテムは座標 $(x_{i}, y_{i})$ に置かれている。

高橋くんは毎回の移動において、次のようになる。

高橋くんは 1 回移動するたびに体力が 1 減少する
ただし、移動先の座標にアイテムがあって
高橋君の体力が $K$ 未満であるとき
アイテムを消費して、高橋くんの体力は $H$ まで回復する
このとき、このアイテムは消えてなくなる

高橋君が一度も体力が 0 未満になることなく、 $N$ 回の移動をすべて終えられるかどうかを判定せよ。

制約

$1 \le N, M, H, K \le 2 \times 10^{5}$

考えたこと

やるべきことは単純明快だ。問題文に書いてある通りのシミュレーションを行えばいい。

ただし、1 つだけ難しいポイントがある。それは、

高橋君が移動した先の座標に、アイテムがあるかどうかを判定する

という部分だ。これについては、set 型 (C++ でも Python3 でも) を使うことで解決する。set の使い方については、解答例を見てしまうのが手っ取り早いと思う。

計算量について注意すると、次のようになる。

要素が set に含まれるかどうかを判定する： $O(\log M)$ (C++ の場合)、 $O(1)$ (Python3 の場合) の計算量でできる
set から特定の要素を削除する： $O(\log M)$ (C++ の場合)、 $O(1)$ (Python3 の場合) の計算量でできる

よって、この問題を解く解答例コード (C++) の計算量は $O(M \log M + N \log M)$ となる。前半の $O(M \log M)$ の部分は、最初に $M$ 個のアイテムを set に挿入するのに要する計算量であり、後半の $O(N \log M)$ の部分は、 $N$ 回の移動をシミュレーションするのに要する計算量である。

同様に、解答例コード (Python3) の計算量は $O(M + N)$ となる。

解答例コード

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, M, H, K;
    string S;
    cin >> N >> M >> H >> K >> S;
    set<pair<int,int>> items;  // アイテムが置いてある座標の集合
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        items.insert({x, y});
    }
    
    // シミュレーションする
    bool res = true;
    int x = 0, y = 0;
    for (int i = 0; i < N; ++i) {
        // 移動する
        if (S[i] == 'R') ++x;
        else if (S[i] == 'L') --x;
        else if (S[i] == 'U') ++y;
        else --y;
        
        // 体力を 1 減らす (0 未満になったら倒れる)
        --H;
        if (H < 0) res = false;

        // アイテムがあって体力が不足していたら回復する
        if (items.count({x, y}) && H < K) {
            H = K;
            items.erase({x, y});  // アイテムを削除する
        }
    }
    
    cout << (res ? "Yes" : "No") << endl;
}

Python3

N, M, H, K = map(int, input().split())
S = input()
items = set(tuple(map(int, input().split())) for _ in range(M))
    
# シミュレーションする
res = True
x, y = 0, 0
for c in S:
    # 移動する
    if c == 'R': x += 1
    elif c == 'L': x -= 1
    elif c == 'U': y += 1
    else: y -= 1

    # 体力を 1 減らす (0 未満になったら倒れる)
    H -= 1
    if H < 0: res = False

    # アイテムがあって体力が不足していたら回復する
    if (x, y) in items and H < K:
        H = K
        items.remove((x, y))  # アイテムを削除する

print("Yes" if res else "No")