pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #331 (Div. 2) C. Wilbur and Points

強い人のコード見て気づいたけど、問題を取り違えていた。
{(x,y)}が集合に含まれるなら{(0,0)}から{(x,y)}までの長方形領域に含まれるすべての点も集合に含まれるらしい。適当に散らばってると思ってた。適当に散らばってても解けるので、適当に散らばってると思って解説する。

問題概要

  • 点の集合{\{(x_1,y_1),\ldots,(x_n,y_n)\}}が与えられる
  • {(x,y)}が集合に含まれるなら{(0,0)}から{(x,y)}までの長方形領域に含まれるすべての点も集合に含まれる←この解説では無視
  • 次の2つの条件を満たすように点を並び替える
    • 条件1{x_i \le x_j}かつ{y_i \le y_j}ならば{i \le j }
    • 条件2{y_i-x_i=w_i}
  • このような並び替え方が存在するならばその例をひとつ出力し、存在しないならNOと出力せよ

解法

まず{y-x}の値で点を類別する。

{w}{S_w}
{w=1}{(1,2)}
{w=2}{(4,6),(3,5),(1,3),(7,9)}
{w=3}{(5,8),(1,4),(9,12)}
{w=4}{(3,7),(7,11),(11,15)}
{y_i-x_i=w_i}を満たす点{(x,y)}は直線{y=x+w_i}上に存在する。
f:id:pekempey:20151116161103p:plain
図を見ればわかるように、どの2点をとっても順序が定義されている。そのため各集合内では普通にソートができる。

{w}{S_w}
{w=1}{(1,2)}
{w=2}{(1,3),(3,5),(4,6),(7,9)}
{w=3}{(1,4),(5,8),(9,12)}
{w=4}{(3,7),(7,11),(11,15)}

あとは順に当てはめていくだけである。たとえば{w=[3,2,1,2,4,3,2,2,3,4,4]}の場合、解の候補{p_n}

  • {p_1=S_3[1]=(1,2)}
  • {p_2=S_2[1]=(1,3)}
  • {p_3=S_1[1]=(1,4)}
  • {p_4=S_2[2]=(3,5)}
  • {p_5=S_4[2]=(3,7)}
  • {p_6=S_3[1]=(5,8)}
  • {p_7=S_2[3]=(4,6)}
  • {p_8=S_2[4]=(7,9)}
  • {p_9=S_3[3]=(9,12)}
  • {p_{10}=S_4[2]=(7,11)}
  • {p_{11}=S_4[3]=(11,15)}

になる。

このようにして構成した列は解の候補であり、かつこれ以外の候補は作れない。そのため、この候補が条件1を満たせばそのまま出力し、満たさなければNOを出力すればいい。

条件1は{j}番目の点より前に{x_i \ge x_j}かつ{y_i \ge y_j}の点が存在しないと言い換えられる。いま{i}番目の点を見ていて、グラフにはi番目までの点がプロットされている。緑色の領域に点が存在すれば、この候補は条件1を満たさない事がわかる。
f:id:pekempey:20151116153330p:plain

地点{x}における{y}の最大値を持っておいて、{x_i}より右側の範囲に高さ{y_i}以上の値があるかどうかを判定すればいい。これはRMQ。
f:id:pekempey:20151116153339p:plain

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

struct RMQ {
    vector<int> mx;
    int size;
    RMQ(int n) {
        size = 1;
        while (size < n) size *= 2;
        mx.resize(size * 2, -1);
    }
    void update(int k, int v) {
        k += size - 1;
        chmax(mx[k], v);
        while (k > 0) {
            k = (k - 1) / 2;
            mx[k] = max(mx[k * 2 + 1], mx[k * 2 + 2]);
        }
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return -1;
        if (a <= l && r <= b) return mx[k];
        int x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return max(x, y);
    }
    int query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

typedef pair<ll, ll> P;

int main() {
    int n;
    cin >> n;
    vector<ll> x(n), y(n), w(n);
    rep (i, n) scanf("%I64d %I64d", &x[i], &y[i]);
    rep (i, n) scanf("%I64d", &w[i]);
    map<ll, vector<P>> mp;
    rep (i, n) mp[y[i] - x[i]].emplace_back(x[i], y[i]);
    for (auto &kv : mp) {
        sort(kv.second.begin(), kv.second.end());
    }
    vector<P> ans;
    map<ll, int> now;
    rep (i, n) {
        if (now[w[i]] < mp[w[i]].size()) {
            ll ansx, ansy;
            tie(ansx, ansy) = mp[w[i]][now[w[i]]++];
            ans.emplace_back(ansx, ansy);
        }
    }
    if (ans.size() < n) {
        cout << "NO" << endl;
        return 0;
    }
    bool sorted = true;
    RMQ rmq(101010);
    rep (i, n) {
        ll tx = ans[i].first;
        ll ty = ans[i].second;
        ll maxx = rmq.query(tx, 101010);
        if (maxx >= ty) sorted = false;
        rmq.update(tx, ty);
    }
    if (!sorted) {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    rep (i, n) {
        printf("%I64d %I64d\n", ans[i].first, ans[i].second);
    }
    return 0;
}

感想

構築自体はすぐに思いついたけど順序判定に1時間近く悩んでしまった。