JAG 模擬国内予選 2016: E - ぼくのかんがえたさいきょうのおふとん

なんとか通して$5$完の$12$位。やったね。

途中までは貪欲+乱択で無理矢理通そうとしていたが、それは無理でした。

problem

For given $s \in \mathbb{N}^n, d \in \mathbb{N}^m$, answer $\min_\sigma \min_k \Sigma_{j \lt m} | d_j - \Sigma_{i \lt k_j} \sigma(s)_i |$.

solution

DP。 $d$を昇順にすると、おふとんをおしいれに戻す操作が発生しなくなり、これまでに追加したおふとんの順番が無視できる。 $d$をsortしておいて$d_j$まで見て、これまでに$s$の$x \subseteq \{ 1, \dots, n \}$番目を使ったときの、不快度の最小値$\operatorname{dp}_{j,x}$を求める。$O(MN2^N)$。

$\operatorname{dp}_{j,x} = (\min_{y \subseteq x} \operatorname{dp}_{j-1,y}) + | d_j - \Sigma_{i \in x} s_i |$という更新。 $\operatorname{dp}_{j,x}$を、$x$の中にまだ使ってないものがあってもよいとして緩めて適当にすると実装が楽。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    while (true) {
        int n, m; cin >> n >> m;
        if (n == 0 and m == 0) break;
        vector<int> s(n); repeat (i,n) cin >> s[i];
        vector<int> d(m); repeat (i,m) cin >> d[i];
        sort(d.begin(), d.end());
        vector<int> acc(1<<n);
        repeat (x,1<<n) {
            repeat (i,n) if (x & (1<<i)) {
                acc[x] += s[i];
            }
        }
        vector<vector<int> > dp(m+1, vector<int>(1<<n));
        repeat (j,m) {
            repeat (x,1<<n) {
                dp[j+1][x] = dp[j][x] + abs(d[j] - acc[x]);
                repeat (i,n) if (x & (1<<i)) {
                    int y = x & ~ (1<<i);
                    dp[j+1][x] = min(dp[j+1][x], dp[j+1][y]);
                }
            }
        }
        cout << dp[m][(1<<n)-1] << endl;
    }
    return 0;
}