AtCoder Regular Contest 027 C: 最高のトッピングにしような

またまた DP 自力で解けた記念。

問題概要

原文 → C: 最高のトッピングにしような - AtCoder Regular Contest 027 | AtCoder

種類のトッピングがある。トッピング は 枚のチケットを交換することで入手でき、その価値は である。

チケットにはスペシャルチケットと通常のチケットの 種類が存在し、どのトッピングにおいてもスペシャルチケット最低 枚を含むチケットの組み合わせでなければ交換できない。

いま、スペシャルチケットを 枚、通常のチケットを 枚持っている。トッピングの価値の合計値を最大化せよ。

解説

ナップザックの亜種、ということで動的計画法を使って解いていきます。説明のため、スペシャルチケットは ST と、通常のチケットは RT と略記します。

dp[i][j][k] := i 番目までのトッピングを使って、ST の残りが j 枚で RT の残りが k 枚である時の価値の最大値 となるように配列を用意します。

どちらの種類のチケットも十分な数あると仮定するとき、 枚のチケットが必要なトッピングに対して使うチケットの組み合わせは 通りありますが、これを全て試していってしまうと DP の更新が 乗ループになり時間的に間に合いません。どこかを工夫して、計算量を落とせないでしょうか？

今回の場合は、ST と RT を組み合わせて 枚使えば良いとのことですので、使うチケットの枚数はどの組み合わせでも等しいです。さらに、いずれのトッピングも ST が最低 枚以上必要であることも重要で、これらを考えると RT の方をなるべく多く使っていけば (ST がなるべく余るように使っていけば) 良いことがわかります。この貪欲で 乗ループになりますので間に合います。計算量は です。

ソースコード

最初メモ化で書こうと思ったけど、意味不明なコードになったので DP で。

int x, y, n;
int t[310], h[310];
int dp[310][310][310];

signed main() {
    cin >> x >> y >> n;
    rep(i,0,n) cin >> t[i] >> h[i];
    memset(dp, 0, sizeof(dp));
    
    rep(i,0,n) repq(j,0,x) repq(k,0,y) {
        dp[i+1][j][k] = dp[i][j][k];
        if(j+k >= t[i] && j != 0) {
            int p, q;
            if(k >= t[i] - 1) {
                p = 1;
                q = t[i] - 1;
            }
            else {
                p = t[i] - k;
                q = k;
            }
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-p][k-q] + h[i]);
        }
    }
    int ans = 0;
    repq(i,0,x) repq(j,0,y) ans = max(ans, dp[n][i][j]);
    cout << ans << endl;
    return 0;
}

さすがにナップザックの亜種は割とできるようになってきたけど、他の DP にもトライしてみなければ・・・。

TopCoder SRM707 Div 2 Med: StepsConstruct

正答率低いのはバグりやすいせいかな。発想自体はそんなに難しくない。

問題概要

原文 → TopCoder Statistics - Problem Statement

の盤面があり、. は通行可能な座標、# は通行不可能な座標を表す。座標の移動は上下左右の方向のみ許されている。左上の座標からスタートし、右下の座標にちょうど ステップで到達できるルートが存在するならば、そのルートを出力せよ。なお、同じ座標に何度移動しても構わないものとする。

解説

まず普通に BFS をやってみて、右下に行くまでに最短で何ステップ必要かを求めましょう。この時点で INF になったり を超えてたりしていると明らかに無理なので弾きます。

次に、 と最短ステップの偶奇を調べましょう。これが一致していないときも弾きます。

経路復元は、ゴールから再度 BFS していくのがやりやすいと思います。ゴールからたどれば、今いる座標の隣のどこかに (スタートから今いる座標に行くまでのステップ数 - ) の座標が必ず存在するので、経路復元が可能になります。

ここまで来たら、ステップ数が になるように適当に増やせば終わりです。手っ取り早いやり方としては、右下の座標の隣のドットと右下の座標に交互に移動し続けるのが良いでしょう。

ソースコード

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
string dir = "DURL";

int rec[100][100];
class StepsConstruct {
    public:
    string construct(vector<string> board, int k) {
        int n = board.size(), m = board[0].size();
        rep(i,0,n) rep(j,0,m) rec[i][j] = INF;
        rec[0][0] = 0;
        queue<pii> q;
        if(board[0][0] == '.') q.push(pii(0,0));

        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(board[x][y] == '#') continue;
                if(rec[x][y] <= rec[t.fr][t.sc] + 1) continue;
                rec[x][y] = rec[t.fr][t.sc] + 1;
                q.push(pii(x,y));
            }
        }

        if(rec[n-1][m-1] == INF || rec[n-1][m-1] > k) return "";
        if(k % 2 != rec[n-1][m-1] % 2) return "";

        string ret = "";
        int dist = rec[n-1][m-1];
        q.push(pii(n-1, m-1));
        int repdir = -1;
        while(!q.empty()) {
            pii t = q.front(); q.pop();
            rep(i,0,4) {
                int x = t.fr + dx[i];
                int y = t.sc + dy[i];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(rec[x][y] != dist - 1) continue;
                if(repdir == -1) repdir = i;
                ret += dir[i ^ 1];
                dist--;
                q.push(pii(x, y));
            }
        }
        reverse(ret.begin(), ret.end());
        while(ret.size() != k) ret = ret + dir[repdir] + dir[repdir ^ 1];
        return ret;
    }
};

今回はすんなり行けたけど、この手の問題って本番書いたらバグりそうでこわい。

AOJ DPL_1_G: Knapsack Problem with Limitations

個数制限付きナップザック問題です。

問題概要

原文 → Knapsack Problem with Limitations | Aizu Online Judge

価値 で重さ であるような 種類の品物と、容量が のナップザックがある。

番目の品物は 個まで使用できる。

ナップザックの容量を超えないように品物を入れた時の価値の最大値を求めよ。

解説

各品物について、品物を 個入れたとき、 個入れたとき・・・と愚直に ずつ増やして考えていくと計算量的に間に合いません。

そこで、繰り返し二乗法のように(厳密には少し違うけど)、取る数を 倍ずつ増やしていくことで考えていきましょう。

例えば品物が 個ある場合は、この場合ですと

• 品物を 個入れたとき
• 品物を 個入れたとき
• 品物を 個入れたとき
• 品物を 個入れたとき

をそれぞれ計算するというわけですね。これで計算量が となり間に合います。

ソースコード

for 文の向きに気をつけましょう。

signed main() {
    int N, W; cin >> N >> W;
    int v[110], w[110], m[110];
    rep(i,0,N) cin >> v[i] >> w[i] >> m[i];

    int dp[10010] = {};
    rep(i,0,N) {
        // take key good(s) each
        for(int k=0; m[i]>0; k++) {
            int key = min(m[i], (int)(1<<k));
            m[i] -= key;
            for(int j=W; j>=key*w[i]; j--) {
                // do not take or take
                dp[j] = max(dp[j], dp[j-key*w[i]] + key*v[i]);
            }
        }
    }
    int ans = 0;
    repq(i,0,W) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}