B. Collecting Packages (Codeforces Round #615 Div. 3)

問題

https://codeforces.com/contest/1294/problem/B

問題概要

座標平面上の0 <= x, y <= 1000かつ(0, 0)以外の位置にn個の点が配置されている。

ここで、原点(0, 0)から右および上のみに移動して、配置されたすべての点を通過することは可能かを判断せよ。

また、通過が可能ならば、x軸方向に1移動することをR、y軸方向に1移動することをUとした文字列で経路を表わせ。ただし取りうる経路のうち辞書順最小のものとする。

考察

RとUを辞書順最小となるように並べる必要があるので、x軸方向への移動を優先する必要があります。なので配置された点をx, yの優先順でソートして、シミュレーションしていけばよいです。c++ならpairに入れてソートするだけです。テストケースは最大100で、nはテストケース全体で1000を超えませんので、それで充分間に合います。

なお、ソート後にy座標が前後していた場合、通過不能となります。（この解法では、xは優先でソートするので前後することはありません）

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int>> v(n);
        int x, y;
        for (int i = 0; i < n; i++) {
            cin >> x >> y;
            v[i] = make_pair(x, y);
        }
        sort(v.begin(), v.end());
        bool ok = true;
        string ans;
        int px = 0;
        int py = 0;
        for (auto w : v) {
            if (w.second < py) {
                ok = false;
                break;
            }
            for (int i = 0; i < w.first - px; i++) ans += "R";
            for (int i = 0; i < w.second - py; i++) ans += "U";
            px = w.first;
            py = w.second;
        }
        cout << (ok ? "YES" : "NO") << endl;
        if (ok) cout << ans << endl;
    }
}