2020-10-14

AtCoder ARC 105 C - Camels and Bridge (青色, 500 点)

AtCoder AtCoder500点 ARC-C 最短路問題牛ゲー双対性最長路問題順列の最適化問題 DP 差分制約系グラフデータ構造テク：前処理指数探索系問題ある値を固定して考える青色diff 区間固定長区間が制約条件を持ちながら左右に移動する問題必要条件を列挙したら十分条件になる条件の言い換え累積max 数直線上のN点の問題個人的要復習 max(pi-pj,0) 【問題集】最短路問題思わず解きたくなる興味深い良問隣接2要素に制約や目的関数のある問題

難しかった

問題へのリンク

問題概要

体重が $w_{1}, \dots, w_{N}$ であるような $N$ 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可能である場合は -1 を出力せよ。

正の整数 $(l, v)$ の組が $M$ 組与えられる (橋と呼ぶ)
そのすべての組に対して、
ラクダの隊列のうちの、どの長さ $l$ の区間をとっても、その内部 (両端含まない) に含まれるラクダの重さの合計値が $v$ 以下である

制約

$1 \le N \le 8$
$1 \le M \le 10^{5}$

考えたこと

$N \le 8$ という制約がすべてを物語っているものの、こういう指数探索系問題は苦手。。。

そしてどう考えても、 $N$ 頭のラクダの並びの順序を $N!$ 通り固定して試す問題だと言えそう。なので、ラクダの並びを固定したときに、条件を満たすように各ラクダ間の長さを調節する問題だと言える。

なお、ラクダの体重の最大値 >= 橋の耐荷重の最小値となる場合は不可能なので -1 を返す。それ以外の場合はひとまず実行可能である。

ラクダの並びを固定したときの、条件の言い換え

ラクダの順序を固定して、各ラクダ i の位置を x[ i ] とおく。このとき、各条件は次のように言い換えることができる。

任意のラクダ i とラクダ j にペアについて、
固定した並びにおいて、ラクダ i, j の間隔にいるラクダの集合を bit とし、それらのラクダの重さの合計を W(bit) とする
$M$ 組の橋のうち、重さの耐荷重が W(bit) 未満であるようなものの中での長さの最大値を dist(bit) (どの橋の加重も W(bit) 以上の場合は 0) としたとき、
x[ j ] - x[ i ] >= dist(bit) が成立する

なお、dist(bit) の値はあらかじめ前処理しておけばよい。前処理は $O(2^{N}M)$ でできる。

DP へ

一列に並べたときのラクダの番号を 1, 2, ..., N と振り直して考えてみる。このとき、

dp[ i ] := 先頭から i 頭のラクダの両端の距離の最小値

このとき、dp[ N ] は以下の最大値になることがわかる。

ラクダ (1, ..., N-1) をすべて条件を満たすように並べた上で、ラクダ N-1, N を適切に引き離す：dp[ N-1 ] + dist[ (N-1, N) ]
ラクダ (1, .., N-2) をすべて条件を満たすように並べた上で、ラクダ N-2, N を適切に引き離す：dp[ N-2 ] + dist[ (N-2, ..., N) ]
ラクダ (1, ..., N-3) をすべて条件を満たすように並べた上で、ラクダ N-3, N を適切に引き離す：dp[ N-3 ] + dist[ (N-3, ..., N) ]
...

これらすべての条件を満たす必要があるので、これらの最大値がクリティカルパスとなる。よって次のような DP が組める。

dp[ i ] = max(dp[ j ] + dist[ (j, j+1, ..., i) ], j < i)

計算量は $O(2^{N}M + N! N^{2})$ となる。

補足：牛ゲー

以上の DP とまったく同じものが、牛ゲーによる考察からも導ける。牛ゲーとは

max：x[ t ] - x[ s ]
s.t.：x[ v[ j ] ] - x[ u[ j ] ] <= d[ j ]

という形をした最適化問題が、次のような最短路問題に帰着されるというものである。

「頂点数 $N$ 、長さが d[ j ] の辺 (u[ j ], v[ j ]) が貼られたグラフにおいて、s から t へと至る最短路」

今回の問題も、次のように書ける。

min：x[ N ] - x[ 1 ]
s.t.：x[ j ] - x[ i ] >= dist(bit)

これは符号反転すると

max：x[ 1 ] - x[ N ]
s.t.：x[ i ] - x[ j ] <= -dist(bit)

これは牛ゲーの考え方が適用できる形となっている。形作られるグラフは DAG なので、結局最長路問題として定式化し直すと、上述の DP と一致する。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long solve() {
    int N, M;
    cin >> N >> M;
    vector<long long> w(N);
    long long maxW = 0;
    for (int i = 0; i < N; ++i) {
        cin >> w[i];
        chmax(maxW, w[i]);
    }
    vector<long long> l(M), v(M);
    for (int j = 0; j < M; ++j) {
        cin >> l[j] >> v[j];
        if (v[j] < maxW) return -1;
    }

    // 前処理
    vector<long long> dist(1<<N, 0);
    for (int bit = 0; bit < (1<<N); ++bit) {
        long long W = 0;
        for (int i = 0; i < N; ++i) {
            if (bit & (1<<i)) W += w[i];
        }
        for (int j = 0; j < M; ++j) {
            if (v[j] < W) {
                chmax(dist[bit], l[j]);
            }
        }
    }

    // DP
    long long res = 1LL<<60;
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    do {
        vector<long long> dp(N, 0);
        for (int i = 1; i < N; ++i) {
            int bit = (1<<ids[i]);
            for (int j = i-1; j >= 0; --j) {
                bit |= (1<<ids[j]);
                chmax(dp[i], dp[j] + dist[bit]);
            }
        }
        chmin(res, dp[N-1]);
    } while (next_permutation(ids.begin(), ids.end()));
    return res;
}

int main() {
    cout << solve() << endl;
}