ECR150-F Monocarp and a Strategic Game

問題

https://codeforces.com/contest/1841/problem/F (diff: 2700)

街には人間、オーク、エルフ、ドワーフのつの種族が住む予定だ。始め街には誰もいない。

個の移住プランが与えられる。個目の移住プランは人間、オーク、エルフ、ドワーフがそれぞれ人移住しようとしている。あなたはこの人達を全員受け入れるか拒否するかを決定する。

街の幸福度をとする。幸福度としてありうる最大値を求めよ。

制約

• 
• (他も同様)
• TL1秒

解法

これ と同じ問題なので、これの解説に書いてある通りのことをすると通る。

想定解法 とは異なるようだ。

実装

今回は想定解法の方で実装してみた

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
using namespace zawa;

using Point = std::pair<long long, long long>;
using Polygon = std::vector<Point>;

std::ostream& operator<<(std::ostream& os, const Point& P) {
    os << '(' << P.first << ',' << P.second << ')';
    return os;
}

int Quadrant(const Point& P) {
    if (P.first == 0 and P.second == 0) return 0;
    if (P.first > 0 and P.second >= 0) return 1;
    if (P.first <= 0 and P.second > 0) return 2;
    if (P.first < 0 and P.second <= 0) return 3;
    if (P.first >= 0 and P.second < 0) return 4;
    assert(false);
    return -1;
}

long long Dot(const Point& P, const Point& Q) {
    return P.first * Q.second - P.second * Q.first;
}

void Rotate(Polygon& P) {
    int min{}; 
    for (int i{} ; i < (int)P.size() ; i++) {
        if (P[min].second > P[i].second) {
            min = i;
        }
        else if (P[min].second == P[i].second and P[min].first > P[i].first) {
            min = i;
        }
    }
    Polygon res(P.size());
    for (int i{} ; i < (int)P.size() ; i++) {
        res[i] = P[i + min >= (int)P.size() ? i + min - (int)P.size() : i + min];
    }
    P = std::move(res);
}

Point operator+(const Point& L, const Point& R) {
    return Point{ L.first + R.first, L.second + R.second };
}
Point operator-(const Point& L, const Point& R) {
    return Point{ L.first - R.first, L.second - R.second };
}

// ミンコフスキー和
Polygon operator+(const Polygon& L, const Polygon& R) {
    std::vector<Point> SL(L.size()), SR(R.size());
    for (int i{} ; i < (int)L.size() ; i++) {
        SL[i] = L[i + 1 == (int)L.size() ? 0 : i + 1] - L[i];
    }
    for (int i{} ; i < (int)R.size() ; i++) {
        SR[i] = R[i + 1 == (int)R.size() ? 0 : i + 1] - R[i];
    }
    Polygon res;
    res.reserve(L.size() + R.size());
    int i{}, j{};
    while (i < (int)SL.size() or j < (int)SR.size()) {
        res.push_back(L[i % SL.size()] + R[j % SR.size()]);
        if (j == (int)SR.size()) {
            i++;
        }
        else if (i == (int)SL.size()) {
            j++;
        }
        else if (Quadrant(SL[i % SL.size()]) < Quadrant(SR[j % SR.size()])) {
            i++;
        }
        else if (Quadrant(SL[i % SL.size()]) > Quadrant(SR[j % SR.size()])) {
            j++;
        }
        else if (Dot(SL[i % SL.size()], SR[j % SR.size()]) > 0) {
            i++;
        }
        else if (Dot(SL[i % SL.size()], SR[j % SR.size()]) < 0) {
            j++;
        }
        else {
            i++; j++;
        }
    }
    Rotate(res);
    return res;
}


int main() {
    SetFastIO();

    int n; std::cin >> n;
    std::vector<Polygon> P(n);
    for (int i{} ; i < n ; i++) {
        P[i].emplace_back(0LL, 0LL);
        long long a, b, c, d; std::cin >> a >> b >> c >> d;
        P[i].emplace_back(a - b, c - d);
        Rotate(P[i]);
    }

    auto rec{[&](auto rec, int l, int r) -> Polygon {
        if (l + 1 == r) return P[l];
        int m{(l + r) / 2};
        return rec(rec, l, m) + rec(rec, m, r);
    }};
    auto M{rec(rec, 0, n)};
    long double ans{};
    for (auto [x, y] : M) {
        ans = std::max(ans, (long double)x * x + (long double)y * y);
    }
    SetPrecision(12);
    std::cout << ans << '\n';
}

感想

• TL1秒怖すぎ。