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);
    }
};

TopCoder SRM 726 Div2 Hard: HeroicScheduled2

するめうめ

tsutaj.hatenablog.com

問題

原文 → TopCoder Statistics - Problem Statement

個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。

個の仕事の部分集合であって、適切にこなすことで全タスクをこなせるような部分集合の総数を求めよ。

解説

貪欲込みの DP で解きました。

すでに仕事を割り当てた時間の集合が であるような部分集合の総数 とします。何も考えずに DP を組むと、例えば S = 11 (binary) のときに、仕事 を 番目に割り当て、仕事 を 番目に割り当てたときの状態と、仕事 を 番目に割り当て、 仕事 を 番目に割り当てる場合を別々に数えてしまいます。これでは答えが合わないので、もう少し工夫する必要があります。

ここで、区間スケジューリングと同じように、それぞれの仕事の区間を終端でソートします。さらに、選べる時間の中で最も早いところを選択するようにします。そうすることで重複がなくなり、正しく数えられます。

ソースコード

const int itrvl = 16;
long long int dp[1 << itrvl];

struct Segment {
    int l, r;
    bool operator<(const Segment &s) const {
        if(r != s.r) return r < s.r;
        return l < s.l;
    }
};

class HeroicScheduled2 {
    public:
    long long getcount(vector<int> start, vector<int> finish) {
        int N = start.size();
        vector<Segment> seg;
        for(int i=0; i<N; i++) {
            seg.push_back(Segment{start[i], finish[i]});
        }
        sort(seg.begin(), seg.end());

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(int i=0; i<N; i++) {
            for(int bit=(1<<itrvl)-1; bit>=0; bit--) {
                for(int k=seg[i].l; k<=seg[i].r; k++) {
                    if(bit >> k & 1) continue;
                    dp[bit | (1 << k)] += dp[bit];
                    break;
                }
            }
        }
        long long int ans = accumulate(dp, dp+(1<<itrvl), 0LL);
        return ans;
    }
};

TopCoder SRM 727 Div1 Easy: OnlySanta

するめうめ

tsutaj.hatenablog.com

問題概要

文字列 が与えられる。 にいくつか文字を挿入して、"SANTA" を部分列として含み、かつ "SATAN" を部分列として含まないような文字列を構成せよ。

解説

方針は同じ回の Div2 Hard (hogecoder での解説) と全く同じです。この問題では文字列を復元する必要があるので、文字列を DP table に入れてとけばよいです。

ソースコード

string dp[1010][7][7];
class OnlySanta {
    public:
    string solve(string S) {
        string A = "SANTA", B = "SATAN";
        string INIT(1010, 'z');
        int len_s = S.length(), len_a = 5, len_b = 5;
        for(int i=0; i<=len_s; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<=len_b; k++) {
                    dp[i][j][k] = INIT;
                }
            }
        }

        string ret = INIT;
        dp[0][0][0] = "";
        for(int i=0; i<=len_s; i++) {
            for(int j=0; j<=len_a; j++) {
                for(int k=0; k<len_b; k++) {
                    if(i == len_s && j == len_a) {
                        chmin(ret, dp[i][j][k]);
                    }

                    // insert S[i]
                    if(i < len_s) {
                        int nxt_a = j + (j < len_a && S[i] == A[j]);
                        int nxt_b = k + (k < len_b && S[i] == B[k]);
                        chmin(dp[i+1][nxt_a][nxt_b], dp[i][j][k] + S[i]);
                    }

                    // insert A[j]
                    if(j < len_a) {
                        int nxt_s = i + (i < len_s && A[j] == S[i]);
                        int nxt_b = k + (k < len_b && A[j] == B[k]);
                        chmin(dp[nxt_s][j+1][nxt_b], dp[i][j][k] + A[j]);
                    }
                }
            }
        }
        return ret;
    }
};