SRM629 Div1 Medium "CandyCollection"

問題

TopCoder Statistics - Problem Statement

考えたこと

１つの形を頂点として、共通の味を持つ形同士を辺で結ぶグラフを考える。１つの形には２つの味があり、１つの味には２つの形がある、というルールより、グラフは複数のサイクルで構成される。

サイクルを適当な場所で切って直線にしてしまえば、ある形の興味は、前の形と共有している味が既に買われたかどうかでしかなくなる。後はちょっとややこしいDP(
SRM629 Div1 Easy Med - zerokugiの日記 - TopCoder部
)をやればＯＫ。

事後

zerokugiさんの実装、めっちゃ簡単やん・・・何で自分のはこんな複雑なん・・・ないわ・・

ソースコード

int n;
vector<int> type[1050];
bool used[1050];
int cost1[1050];
int cost2[1050];

vector<int> T1;
vector<int> T2;
vector<int> N1;
vector<int> N2;

class CandyCollection {
public:

    int solve(vector <int> Type1, vector <int> Number1, vector <int> Type2, vector <int> Number2) {
        n = Type1.size();
        T1 = Type1;
        T2 = Type2;
        N1 = Number1;
        N2 = Number2;

        for (int i = 0; i < n; i++) {
            type[i].clear();
        }
        
        for (int i = 0; i < n; i++) {
            type[Type1[i]].push_back(i);
            type[Type2[i]].push_back(i);
        }

        for (int i = 0; i < n; i++) {
            cost1[i] = min(Number1[i], Number2[i]) + 1;
            cost2[i] = max(Number1[i], Number2[i]) + 1;
        }

        memset(used, false, sizeof(used));

        int res = 0;
        for (int i = 0; i < n; i++) {
            // 形iが属するサイクルでコストの最小値を求める。
            // 形iが一番左にある直線ということにしてDPをする。
            if (used[i]) continue;
            used[i] = true;
            res += solve(i);
        }
        return res;
    }

    // dp[flag][id][already] :=
    // flag   ...一番左の味を最初の形の飴で買うかどうか
    // id     ...着目している形の左からの場所
    // already...左の形と共有している味は既に買ったかどうか
    int dp[2][1050][2];

    int solve(int root) {
        // rootが属するサイクルの情報を取得
        vector<int> ts; // サイクルに属す形の列
        vector<bool> isLeft; // 左の形と共有している味が右の形と共有している味よりも多いかどうか
        int cul_t = root;
        int cul_v = T1[root];
        while (true) {
            ts.push_back(cul_t);
            isLeft.push_back(is_Left(cul_t, cul_v));

            pair<int, int> ne = find(cul_v, cul_t);
            if (ne.first == -1) break;
            cul_t = ne.first;
            cul_v = ne.second;
            used[cul_t] = true;
        }

        const int INF = 1000 * 2000;
        int n = ts.size();

        // dp[0][j][k]... 一番左の味は最初で買う
        // dp[1][j][k]... 一番左の味は最後で買う
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }
        dp[0][0][0] = 0;
        dp[1][0][1] = 0;

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 2; k++) {
                    if (k == 0) {
                        // 左を買わねばならない
                        // 最小を買う
                        if (isLeft[j]) {
                            setVal(dp[i][j + 1][0], dp[i][j][k] + cost1[ts[j]]);
                        }
                        // 両方買う
                        setVal(dp[i][j + 1][1], dp[i][j][k] + cost2[ts[j]]);
                    }
                    else {
                        // 左は既にある！
                        // どっちも買わない
                        setVal(dp[i][j + 1][0], dp[i][j][k]);
                        // 最小を買う
                        int nk = isLeft[j] ? 0 : 1;
                        setVal(dp[i][j + 1][nk], dp[i][j][k] + cost1[ts[j]]);
                        // 両方買う
                        setVal(dp[i][j + 1][1], dp[i][j][k] + cost2[ts[j]]);
                    }

                }
            }
        }

        return min(dp[0][n][0], min(dp[0][n][1], dp[1][n][1]));
    }

    bool is_Left(int t, int r_v) {
        int num = max(N1[t], N2[t]);
        int l_num = T1[t] == r_v ? N2[t] : N1[t];
        return l_num == num;
    }

    // 以下のような形を返す（なければ-1）
    // ・cul_tという形ではない
    // ・cul_vという味を持つ
    pair<int, int> find(int cul_v, int cul_t) {
        int res_t = -1, res_v = -1;
        if (type[cul_v][0] == cul_t) {
            int cand = type[cul_v][1];
            if (!used[cand]) {
                res_t = cand;
            }
        }
        else {
            int cand = type[cul_v][0];
            if (!used[cand]) {
                res_t = cand;
            }
        }
        if (res_t == -1) return make_pair(-1, -1);
        res_v = T1[res_t] == cul_v ? T2[res_t] : T1[res_t];
        return make_pair(res_t, res_v);
    }

    void setVal(int& tar, int val) {
        if (tar > val) tar = val;
    }
};