diverta 2019_2 D - Squirrel Merchant (青色, 600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。

問題へのリンク

問題概要

問題画像そのままを

解法 1: 自分のやつ

僕が最初に考えたことは、例えば

「最初に A でドングリのいくつかを金 (銀、銅も) にかえた上で、最後に A で金 (銀、銅も) をドングリに変える」というのは意味がない

ということ。よって、金・銀・銅それぞれについて

• A でドングリを金属に変えて (2 ターン目)、B でドングリに戻す (3 ターン目)
• B でドングリを金属に変えて (3 ターン目)、A でドングリに戻す (4 ターン目)

のどちらかになることが言える。さらにこのどちらの方がいいかも特定できる。すなわちドングリに戻すときの換算レートが高い方を採用する。

さらにさらに、3 ターン目については、

• ある金属たちについてドングリに戻す
• 他の金属たちについて金属に換算する

の両方が行われる可能性があるが、ドングリに戻す方を先に行って損はない。以上から、この問題は「前半」と「後半」に真っ二つにきれいにわかれて、それぞれ

---

金属が 0〜3 種類あって、例えば 3 種類の場合では、それぞれ金・銀・銅を グラムずつ得るとすると

max: ax + by + cz
s.t. px + qy + rz <= N

みたいな最適化を解く (1 種類、2 種類の場合は変数の数が 1, 2 になる、また a < p, b < q, c < r である)

---

という問題に帰着される。editorial ではナップサック DP でやっている。僕は を固定する全探索でやった (でもナップサック DP でやった方がいいと思う...)

を固定したとき、c < r が保証されているので「残りを目一杯換算した方がいい」という Greedy で OK。よって全体として くらいでできる。

怖いのは後半パートにおける は 5000 倍くらいまで大きくなる可能性があるのだが、その場合は後半は高々 2 変数以下なので大丈夫。

#include <iostream>
#include <vector>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long N;
long long a[3], b[3];

long long calc(vector<long long> sei, vector<long long> obj, long long M) {
    if (sei.size() == 0) return M;
    if (sei.size() == 1) {
        long long rem = M;
        long long p = rem / sei[0];
        long long r = rem % sei[0];
        return p * obj[0] + r;
    }
    if (sei.size() == 2) {
        long long res = M;
        for (long long x = 0; x * sei[0] <= M; ++x) {
            long long rem = M - x * sei[0];
            long long p = rem / sei[1];
            long long r = rem % sei[1];
            chmax(res, x * obj[0] + p * obj[1] + r);
        }
        return res;
    }
    if (sei.size() == 3) {
        long long res = M;
        for (long long x = 0; x * sei[0] <= M; ++x) {
            for (long long y = 0; x * sei[0] + y * sei[1] <= M; ++y) {
                long long rem = M - x * sei[0] - y * sei[1];
                long long p = rem / sei[2];
                long long r = rem % sei[2];
                chmax(res, x * obj[0] + y * obj[1] + p * obj[2] + r);
            }
        }
        return res;
    }
    return M;
}

long long solve() {
    // zenhan
    {
        vector<long long> sei, obj;
        for (int i = 0; i < 3; ++i) {
            if (a[i] < b[i]) {
                sei.push_back(a[i]);
                obj.push_back(b[i]);
            }
        }
        N = calc(sei, obj, N);
    }

    // kouhan
    {
        vector<long long> sei, obj;
        for (int i = 0; i < 3; ++i) {
            if (a[i] > b[i]) {
                sei.push_back(b[i]);
                obj.push_back(a[i]);
            }
        }
        N = calc(sei, obj, N);
    }
    return N;
}

int main() {
    while (cin >> N) {
        for (int i = 0; i < 3; ++i) cin >> a[i];
        for (int i = 0; i < 3; ++i) cin >> b[i];
        cout << solve() << endl;
    }
}

解法 2: ナップサック DP

解法 1 では、金銀銅それぞれに応じて前半と後半どちらでドングリにするかを割り振ったけど、本当はそれをする必要はなくて、単に

---

金属が 0〜3 種類あって、それぞれ金・銀・銅を グラムずつ得るとすると

max: ax + by + cz
s.t. px + qy + rz <= N

みたいな最適化を解く

---

というのを係数を入れ替えて二回解くだけでも OK。この場合、 という保証はない。そしてこれは個数制限なしナップサック問題として解くことができる。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long N;
vector<long long> a(3), b(3);

const int MAX = 30000000;
long long dp[MAX];

long long calc(vector<long long> sei, vector<long long> obj, long long M) {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < sei.size(); ++i) {
        for (int v = 0; v + sei[i] <= M; ++v) {
            chmax(dp[v+sei[i]], dp[v] + obj[i]);
        }
    }
    long long res = M;
    for (int v = 0; v <= M; ++v) chmax(res, dp[v] + M-v);
    return res;
}

long long solve() {
    N = calc(a, b, N);
    N = calc(b, a, N);
    return N;
}

int main() {
    cin >> N;
    for (int i = 0; i < 3; ++i) cin >> a[i];
    for (int i = 0; i < 3; ++i) cin >> b[i];
    cout << solve() << endl;
}