Mister雑記

競プロやります。

Diverta 2019 2 - D「Squirrel Merchant」 (600)

atcoder.jp

問題

リスは今家にいて、 N個のどんぐりを持っている。 これを増やすために、今から換金所へ行こうとしている。

換金所は2つあり、 i番目の換金所では j = 1, 2, 3について 以下の操作ができる。

  • どんぐり g_{i,j}個と1gの金属 jを交換する。
    • この交換は双方向で行うことができる。

リスはこれから家→換金所1→換金所2→換金所1→家の順に移動を行い、 換金所では好きな回数だけ上の操作を行うことができる。

最後に家に着いた時点で、 リスが持ちうるどんぐりの個数の最大値を求めよ。

制約

  •  1 \leq N, g_{i, j} \leq 5000

考察

最初の換金所1→換金所2の移動について考える。

ここで、換金所2に移動したとき換金所1で手に入れた全ての金属を どんぐりに戻しても問題ない。 これはそのどんぐりをまた同じ数の金属に戻せるためである。

ここから、各操作というのは 「 g_{1, j}個のどんぐりを g_{2, j}個に変える」 と同値になる。 これは最初に持っているどんぐりを「重さ」、 得られるどんぐりを「価値」と見ることで 個数無制限ナップザックDPによって最適解が得られる (何それ?という人は蟻本のP.58を読みながら これ を通すといいと思います)。

重みの最大値を W、取引種数を Kとしたとき このDPの計算量は時間は O(WK)、空間は O(W)となる。 換金所2にいる時点で持っているどんぐりの数は高々  2.5 \times 10^7個なので、時間はともかくメモリも際どいが取れる。

ただし、DPの初期値に注意する必要がある。 単純に全部0にすると、例えば

  •  N = 3 2 \to 2で解が 2になる。
  •  N = 1 2 \to 2で解が 0になる。

みたいなことが起こる。これは取引に使わなかったどんぐりの存在を 無視しているためである。 よって「取引なしでも i個は得られる」ということで  dp_i = iと初期化するとよい。

実装例

atcoder.jp

using lint = long long;

int main() {
    /* ----- 入力 ----- */
    lint N;
    cin >> N;
    vector<vector<lint>> val(2, vector<lint>(3));
    for (auto& v : val) {
        for (auto& m : v) cin >> m;
    }

    /* ----- 取引 ----- */
    for (int i = 0; i < 2; ++i) {
        vector<lint> from = val[i], to = val[(i + 1) % 2];
        // fromで金属に変換してからtoでどんぐりに戻す

        /* ----- 個数無制限ナップザックDP ----- */
        vector<lint> dp(N + 1);
        iota(dp.begin(), dp.end(), 0LL);
        // dp[i] = どんぐりi個から得られるどんぐりの最大個数
        //         無変換でi個は確実に得られることに注意

        for (int i = 0; i < 3; ++i) {
            lint F = from[i], T = to[i];
            for (int m = 0; m + F <= N; ++m) {
                dp[m + F] = max(dp[m + F], dp[m] + T);
            }
        }
        N = dp[N];
    }

    cout << N << endl;
    return 0;
}

反省

  • 考察はとてもスムーズだったが詰めが甘かった。
    • 「99%このミスがWAの原因じゃないな」と思いながら再提出するのやめてぇ。
  • 個数無制限ナップザックDPはなぜかすんなり書ける。
  • ちなみに本番では要らない場合分けをしていた。通ったからいいけど。