TopCoder SRM 726 Div1 Easy: Unpacking

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

個の袋がある。 番目の袋には 個の赤いキャンデーと の青いキャンデーが入っていて、コストは とのことである。

それぞれの袋について、この情報は微妙に間違っている可能性があり、赤と青の総和は確かにこの通りだが、「赤も青も個数が同じ」「赤が 個少なく青が 個多い」「青が 個少なく赤が 個多い」の つの可能性がある。

いま、赤か青のキャンデーどちらかを 個以上集めたいと考えている。どの可能性においてもこれを満たすような袋の選び方であって、コストが最小のものを求めよ。そのような選び方が存在しないならば を出力せよ。

解説

仮に増減がないなら、 番目まで見て、袋を 個使って、総和が になるようなコストの最小値 という DP を、赤と青それぞれについて行えばよいです。

しかし今回は増減があるため、この DP から少し工夫しなければいけません。

袋を 個選ぶと、最大で の増減が考えられます。 であれば条件を満たすため、赤か青のどちらかが 個以上あれば条件を満たすことになります。この DP は上と同様に処理できます。

赤と青のどちらも 個未満しかなくても、条件を満たす場合があります。それは を満たしている場合で、均等に割り当ててもどちらかは 個以上になるためです。したがって、赤と青を足したものを新たに要素として作り、上と同じ DP を解けばよいです。

答えとなるのはこれらの です。 まで DP する必要があるので、 DP 配列のサイズに注意しましょう。

ソースコード

int dp[51][30000];
class Unpacking {
    public:
    int solve(vector<int> item, vector<int> cost, int lim, int mode) {
        int N = item.size(), ret = INF;
        int nlim = lim + N;
        for(int i=0; i<=N; i++) {
            fill(dp[i], dp[i]+nlim+1, INF);
        }

        dp[0][0] = 0;
        for(int i=0; i<N; i++) {
            for(int j=i; j>=0; j--) {
                for(int k=nlim; k>=0; k--) {
                    if(dp[j][k] == INF) continue;
                    chmin(dp[j+1][min(nlim, k+item[i])], dp[j][k] + cost[i]);
                }
            }
        }

        for(int j=1; j<=N; j++) {
            int xlim = (mode ? lim + j : lim);
            for(int k=xlim; k<=nlim; k++) {
                chmin(ret, dp[j][k]);
            }
        }
        return ret;
    }

    int getcost(vector<int> a, vector<int> b, vector<int> cost, int K) {
        int ans = INF;
        chmin(ans, solve(a, cost, K, 1));
        chmin(ans, solve(b, cost, K, 1));

        int N = a.size();
        vector<int> c;
        for(int i=0; i<N; i++) {
            c.push_back(a[i] + b[i]);
        }
        chmin(ans, solve(c, cost, 2*K-1, 0));
        return (ans == INF ? -1 : ans);
    }
};