TCO15 Round 2C med:LongSeat

これは難しい…

問題

TopCoder Statistics - Problem Statement

解法

左からどういう順番で座るかを決めて,どの人が座ってどの人が座らないかを決めた時に,そのような座り方があり得るかどうかを判定していく。

制約式は以下のような感じになる。これを牛ゲーに落としこむことによって,それぞれの座り方がありえるのかを求めていく。

左からi番目に座っている人の座る順番をord[i]とする。また,席の一番左端をSとする。

まず座る人の制約は,

d[ord[i]] + w[ord[i]] <= d[ord[i+1]] (隣同士の人との制約)
かつ
S+L >= ord.back + w[ord.back] (席の長さがLであることの制約)

次に,立つ人(幅はWとする)の制約(要するに「座れるような状況がありえない」という状況にならなければならない,ということ)は,立つ人の前に座ってる人の集合subに対して,

sub[0] - S <= w[sub[0]] + W - eps (左端からの制約)
sub[i+1] - sub[i] <= w[sub[i]] + W - eps (i番目の人とi+1番目の人との間の制約)
S+L - sub.back <= w[sub.back] + W - eps (右端と一番右端に座る人との間の制約)

int N;
ll L;
ll W[60];

int V, S;
vector<tuple<int, int, ll> > es;

bool bellman_ford() {
    bool up;
    vector<ll> pot(V, 1LL<<60);
    pot[S] = 0;
    for (int i = 0; i <= V; i++) {
        up = false;
        for (const auto e : es) {
            int u = get<0>(e), v = get<1>(e);
            ll tp = pot[u]+get<2>(e);
            if (tp < pot[v]) {
                pot[v] = tp;
                up = true;
            }
        }
        if (!up) break;
    }
    return !up;
}

bool is_feasible(const vector<int>& ord) {
    const ll M = 1000;

    V = N+1;
    S = N;
    es.clear();

    // Sit Constraints
    if (!ord.empty()) {
        es.emplace_back(ord[0], S, 0);
        for (int i = 0; i < (int)(ord.size()-1); i++) {
            es.emplace_back(ord[i+1], ord[i], -W[ord[i]] * M);
        }
        es.emplace_back(S, ord.back(), (L-W[ord.back()]) * M);
    }

    // Stand Constraints
    for (int k = 0; k < N; k++) {
        if (find(ord.begin(), ord.end(), k) != ord.end()) continue;
        ll w = W[k];

        vector<int> sub;
        for (int o : ord) if (o < k) sub.emplace_back(o);

        if (sub.empty()) {
            // 座れるじゃん
            if (w <= L) return false;
        } else {
            es.emplace_back(S, sub[0], w*M-1);
            for (int i = 0; i < (int)(sub.size()-1); i++) {
                es.emplace_back(sub[i], sub[i+1], (w+W[sub[i]]) * M - 1);
            }
            es.emplace_back(sub.back(), S, (w-L+W[sub.back()]) * M - 1);
        }
    }
    return bellman_ford();
}

class LongSeat {
public:
    vector <string> canSit(int L, vector <int> width) {
        N = width.size();
        for (int i = 0; i < N; i++) W[i] = width[i];
        ::L = L;

        bool b[10][2] = {};
        vector<int> ord(N);
        for (int i = 0; i < N; i++) ord[i] = i;
        do {
            for (int n = 0; n <= N; n++) {
                vector<int> sub(ord.begin(), ord.begin()+n);
                if (is_feasible(sub)) {
                    for (int i = 0; i < N; i++) {
                        if (find(sub.begin(), sub.end(), i) != sub.end()) b[i][1] = true;
                        else b[i][0] = true;
                    }
                }
            }
        } while (next_permutation(ord.begin(), ord.end()));
        vector<string> ans(N);
        const char * str[] = {"???", "Stand", "Sit", "Unsure"};
        for (int i = 0; i < N; i++) ans[i] = str[b[i][1]*2 + b[i][0]];
        return ans;
    }
};