AtCoder ABC 243 C - Collision 2 (3Q, 茶色, 300 点)

座標ごとに情報を整理するのは頻出！

• 問題へのリンク

問題概要

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;
}