hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 726 Div1 Easy: Unpacking

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

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

解説

仮に増減がないなら、 \mathrm{dp} \left[ i \right] \left[ j \right] \left[ k \right] :=  i 番目まで見て、袋を  j 個使って、総和が  k になるようなコストの最小値 という DP を、赤と青それぞれについて行えばよいです。

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

袋を  x 個選ぶと、最大で  x の増減が考えられます。  \max( \text{赤}, \text{青} ) \geq K であれば条件を満たすため、赤か青のどちらかが  K+x 個以上あれば条件を満たすことになります。この DP は上と同様に処理できます。

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

答えとなるのはこれらの  \min です。 2K-1 まで 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);
    }
};