【精進3】ARC076-E

広告で見るゲームの話

問題

E - Connected?
$R \times C$の長方形の内部または周上に$1$から$N$までの番号がつけられた点が$2$個ずつ配置されている。長方形から出ず、互いに交わらないようにして同じ番号同士の点を曲線で結ぶことができるか？

解法

長方形の内部の点を、他の点と被らないように内部の好きな位置に移動しても結べるかどうかは変わらない。同じ数字の点の一方を他方に十分近づければ他の番号の組と干渉せず曲線で結べる。従って自由に動かせない、両方周上にある組のみ考えれば良い。隣り合った同じ数字の組をpopしていって空にできるとき結ぶことができる。 これは括弧列がvalidかどうか判定する問題と同様に長方形の周上をぐるりと回りながらstackで管理することで判定できる。
なおITFPC2023Eでも出されてるそう。

#include "template.hpp"
void solve() {
    LL(h, w, n);
    vector<P> u, r, d, l;
    auto in = [&](ll x, ll y, ll num) {
        if(x == 0) {
            u.push_back({y, num});
        } else if(y == w) {
            r.push_back({x, num});
        } else if(x == h) {
            d.push_back({y, num});
        } else {
            assert(y == 0);
            l.push_back({x, num});
        }
    };
    rep(i, n) {
        LL(x, y, X, Y);
        if((0 < x and x < h) and (0 < y and y < w))
            continue;
        if((0 < X and X < h) and (0 < Y and Y < w))
            continue;
        in(x, y, i);
        in(X, Y, i);
    }
    stack<ll> st;
    auto st_in = [&st](ll num) {
        if(st.size() and st.top() == num) {
            st.pop();
        } else {
            st.push(num);
        }
    };
    sort(all(u));
    sort(all(r));
    sort(rbegin(d), rend(d));
    sort(rbegin(l), rend(l));
    for(auto i : u)
        st_in(i.second);
    for(auto i : r)
        st_in(i.second);
    for(auto i : d)
        st_in(i.second);
    for(auto i : l)
        st_in(i.second);
    print((st.size() ? "NO" : "YES"));
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}