set をちゃんと使えるかを試す問題!
問題概要
高橋くんは最初、体力は であり、二次元平面上の座標 にいる。
高橋くんは今から 回の移動を行う。高橋くんの移動方法は長さ の文字列 で表される。1 回の移動は、上下左右のいずれかであり、それぞれ文字 'U'、'D'、'L'、'R' で表されている。
二次元平面上には 個のアイテムがある。 個目のアイテムは座標 に置かれている。
高橋くんは毎回の移動において、次のようになる。
- 高橋くんは 1 回移動するたびに体力が 1 減少する
- ただし、移動先の座標にアイテムがあって
- 高橋君の体力が 未満であるとき
- アイテムを消費して、高橋くんの体力は まで回復する
- このとき、このアイテムは消えてなくなる
高橋君が一度も体力が 0 未満になることなく、 回の移動をすべて終えられるかどうかを判定せよ。
制約
考えたこと
やるべきことは単純明快だ。問題文に書いてある通りのシミュレーションを行えばいい。
ただし、1 つだけ難しいポイントがある。それは、
高橋君が移動した先の座標に、アイテムがあるかどうかを判定する
という部分だ。これについては、set
型 (C++ でも Python3 でも) を使うことで解決する。set
の使い方については、解答例を見てしまうのが手っ取り早いと思う。
計算量について注意すると、次のようになる。
- 要素が
set
に含まれるかどうかを判定する: (C++ の場合)、 (Python3 の場合) の計算量でできる set
から特定の要素を削除する: (C++ の場合)、 (Python3 の場合) の計算量でできる
よって、この問題を解く解答例コード (C++) の計算量は となる。前半の の部分は、最初に 個のアイテムを set
に挿入するのに要する計算量であり、後半の の部分は、 回の移動をシミュレーションするのに要する計算量である。
同様に、解答例コード (Python3) の計算量は となる。
解答例コード
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")