座標ごとに情報を整理するのは頻出!
問題概要
x-y 座標平面上に 人がいる。それぞれ座標 の位置にいて、左右いずれかを向いている(各人が左右どちらを向いているかは文字列 で与えられる)。
各人が、その位置から、向いている方向に向かって全員同じ速度で歩き出す。
衝突が発生するかどうかを判定せよ。
制約
考えたこと
まず、初期状態の y 座標が異なる人同士が衝突することはないし、誰も移動によって y 座標は変化しないことに着目しよう。よって、y 座標ごとに独立に解いて良い(実装上は map
を用いて y 座標ごとにデータを整理しよう)。
よって、次の問題が解ければよい。
何人かがいて、それぞれ x 座標が の地点にいて、左右どちらかを向いている。
その方向に移動するとき、衝突が起こるかどうかを判定せよ。
まず、 座標が小さい順に並び替えよう。そして、 座標が小さい順に L
と R
を並び替えよう。そうすると、さらに次の問題になる。
L
と R
からなる文字列 が与えられる。
この文字列中の 2 文字であって、左側が R
で右側が L
であるものが存在するとき、衝突するという。衝突するかどうかを判定せよ。
この問題を愚直に、全文字ペアについて試すと TLE してしまう。実は隣接する文字だけ調べれば良い。具体的には、次のように整理できる。
- 隣接する 2 文字で "RL" であるものがあるとき:衝突する(これは自明)
- 隣接する 2 文字で "RL" であるものが存在しないとき:
- 文字列 は "LLL...LRR...R" という形になる
- この場合は衝突は起こらない
よって、隣接する 2 文字のみ調べれば良いことがわかった。
最後に全体の計算量を考える。y 座標を整理するのに map
を使用したり、y 座標ごとに x 座標順にソートしたりする処理があることから、全体の計算量は となる。
コード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> X(N), Y(N); for (int i = 0; i < N; i++) cin >> X[i] >> Y[i]; string S; cin >> S; // Y 座標ごとに整理する map<int, vector<pair<int, char>>> data; for (int i = 0; i < N; i++) { data[Y[i]].emplace_back(X[i], S[i]); } bool res = false; for (auto [Y, vec] : data) { // X 座標が小さい順に並べて、"RL" の並びがあるかどうかを check sort(vec.begin(), vec.end()); for (int i = 0; i+1 < vec.size(); i++) { if (vec[i].second == 'R' && vec[i+1].second == 'L') { res = true; } } } cout << (res ? "Yes" : "No") << endl; }