mayoko’s diary

プロコンとかいろいろ。

SRM 478 div1 med:KiwiJuice

微妙に理由わかってないんですが解説ないのでうーん。ていうかこれ…

解法

理由がよくわからないんですが, ある集合 s を選んで, その集合同士でのみジュースのやり取りをした場合, 必ずジュースの量の割り当ては以下のようになります。

sum がその集合のジュースの合計量であるとして, sum/C 個, 容量が C のジュースになり, 1 つ sum%C のジュースがあり, あとはすべて 容量が 0 のジュースになります。

よって, dp[s] = (集合 s から得られる利益の最大値)とすれば, s からジュースをやり取りする集合 sub を選んで, sub について得られる利益を調べた後, 残りの集合 s^sub で得られる利益を dp[s^sub] で調べます。これらの和の最大値が dp[s] です。

s の部分集合 sub 蟻本の 144 ページに書いてあるような要領で全列挙することが出来ます。部分集合を調べるのに 2^n の計算量を書ける必要はないです。
計算量を解析します。要素の数が k 個の部分集合を列挙するのは, O(2^k) かかるので, 全体の計算量は,
comb[15][k] * 2^(15-k) の和です。ただし, comb[n][r] は nCr を表します(伝われ)。

これは 3^k に等しいです。およそ 1.4*10^7 なので十分間に合います。下のコードでは少し手抜きして この 15 倍の計算量がかかりますが普通に間に合いました。

int dp[1<<16];

int dfs(int s, const int C, const vi& bottles, const vi& prices) {
    int& ret = dp[s];
    if (ret >= 0) return ret;
    if (s == 0) return ret = 0;
    int sub = s, n = bottles.size();
    ret = 0;
    do {
        int ns = s^sub;
        int tmp = dfs(ns, C, bottles, prices);
        int cnt = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            if ((sub>>i)&1) {
                sum += bottles[i];
                cnt++;
            }
        }
        for (int i = 0; i < cnt; i++) {
            if (sum >= C) {
                tmp += prices[C];
                sum -= C;
            } else {
                tmp += prices[sum];
                sum = 0;
            }
        }
        ret = max(ret, tmp);
        sub = (sub-1)&s;
    } while (sub != s);
    return ret;
}

class KiwiJuice {
public:
    int theProfit(int C, vector <int> bottles, vector <int> prices) {
        int n = bottles.size();
        memset(dp, -1, sizeof(dp));
        return dfs((1<<n)-1, C, bottles, prices);
    }
};