Educational Codeforces Round 104 E Cheap Dinner

日本語解説無かったから書きます。俺自身が日本語解説になることだ。

地獄みたいな実装で泣きそうになった。一昔前のこどふぉって感じ。こんなんやって楽しいか？

問題設定

コース料理を食べます。

メニューには個の最初の料理、個の二番目の料理、個のドリンク、個のデザートの値段がそれぞれ書かれています。

食べ合わせの相性があって、最初の料理と二番目の料理について、一緒に食べてはいけない組み合わせが個あります。
同様に、二番目の料理とドリンクについて一緒に食べてはいけない組み合わせが個、ドリンクとデザートについて一緒に食べてはいけない組み合わせが個あります。

食べられる組み合わせで、最も安いコースはいくらになるでしょうか。

考察

うーん、補グラフでダイクストラ！w としたいところですが、流石に辺の数がヤバいことになるのでできません。

とりあえずこういう順番が本質でない問題はソートしても困らないので、各メニューの金額をソートしてから考えることにしましょう。

和の最小化は、一番小さい数同士を足したときが明らかに最小なので、ソートした後に食べられる組み合わせの中で一番左のものを選んであげればいいことがわかります。

具体的な手順を示してイメージを補強します。まず、一番目の料理は小さい順に左からソートされているものとして、二番目の料理を見ていきます。

各二番目の料理を一つずつ見ていき、それとの食べ合わせが良い一番目の料理の中で最も左にあるものを選べば、「二番目の各料理まで食べる時の最小コスト」がわかります。

「二番目の各料理まで食べる時の最小コスト」がわかったので、その数列をソートして、同じように各ドリンクについて一つずつ見ていきます。

そうすると「各ドリンクまで食べる時の最小コスト」がわかるので、更にその数列をソートし、各デザートについて一つずつ見れば、「各デザートまで食べる時の最小コスト」を求めることが出来ます。その最小値が答えです。

計算量を考えてみましょう。一番時間がかかりそうなのは「各料理に対して食べ合わせの良いものの中で、最も左にある料理を選ぶ」操作ですが、実はsetなどを利用すれば普通に間に合います。

証明してみます。個の食べ合わせの悪いペアが存在し、ペアの数はです。

i番目の料理が持つ食べ合わせの悪いものの数 とします。

全ての料理について見る際には 回の計算が発生することになります。をしているのは、であっても各料理を一つずつ見ていくという行為は必ず行われるためです。

そして は、

と

に分解できます

ここでsetを使用するため となり

また明らかに です。

よってとなります。

ということで計算が間に合うことはわかりました。

あとは実装を頑張るんですが、この実装が嫌すぎて禿げました。ソートするから添え字の対応を上手くしてやらないと壊れてしまうんですが、まあ上手くできなかったですね。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i].first;
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}


ll x_min_element(const set<int> &x, const vector<P> &val) {
    ll ret = LINF;
    rep(i,x.size()+1) {
        if (!x.count(i)) {
            if (i != val.size()) ret = val[i].first;
            break;
        }
    }
    return ret;
}

void calc_dp(const vector<set<int>> &x, const vector<P> &val, const vector<ll> &b, vector<P> &dp) {
    int n = x.size();
    rep(i,n) {
        ll tmp = x_min_element(x[i], val);
        tmp += b[i];
        chmin(dp[i].first, tmp);
        dp[i].second = i;
    }
    return;
}

int main(int argc, char const *argv[]) {
    input_init();

    int n1,n2,n3,n4; cin>>n1>>n2>>n3>>n4;
    vector<P> a(n1), b(n2), c(n3), d(n4);
    rep(i,n1) cin>>a[i].first, a[i].second = i;
    rep(i,n2) cin>>b[i].first, b[i].second = i;
    rep(i,n3) cin>>c[i].first, c[i].second = i;
    rep(i,n4) cin>>d[i].first, d[i].second = i;

    // 一番目の料理をソート
    sort(a.begin(), a.end());

    vector<int> idx_a(n1), idx_b(n2), idx_c(n3), idx_d(n4);

    // 添え字を対応付ける
    rep(i,n1) idx_a[a[i].second] = i;

    int m1,m2,m3; cin>>m1;
    vector<set<int>> x(n2), y(n3), z(n4);
    rep(i,m1) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_a_index = idx_a[p];
        int cur_b_index = q;
        x[cur_b_index].insert(cur_a_index);
    }

    vector<P> dp0(a);
    vector<P> dp1(n2, {LINF, LINF});
    vector<ll> B, C, D;
    for (auto &&e: b) B.push_back(e.first);
    for (auto &&e: c) C.push_back(e.first);
    for (auto &&e: d) D.push_back(e.first);

    calc_dp(x, dp0, B, dp1);
    
    // 二番目の料理までわかったのでソートする
    sort(dp1.begin(), dp1.end());

    // 添え字を対応付ける
    rep(i,n2) idx_b[dp1[i].second] = i;

    cin>>m2;
    rep(i,m2) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_b_index = idx_b[p];
        int cur_c_index = q;
        y[cur_c_index].insert(cur_b_index);
    }

    vector<P> dp2(n3, {LINF, LINF});
    calc_dp(y, dp1, C, dp2);

    // ドリンクまでわかったのでソートする
    sort(dp2.begin(), dp2.end());

    // 添え字を対応付ける
    rep(i,n3) idx_c[dp2[i].second] = i;

    cin>>m3;
    rep(i,m3) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_c_index = idx_c[p];
        int cur_d_index = q;
        z[cur_d_index].insert(cur_c_index);
    }

    vector<P> dp3(n4, {LINF,LINF});

    // デザートまでわかった
    calc_dp(z, dp2, D, dp3);

    ll ans = min_element(dp3.begin(), dp3.end())->first;
    if (ans != LINF) cout << ans << '\n';
    else cout << -1 << '\n';

    return 0;
}