けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題

問題概要

 N 本の棒を用いて、下図のようなモビールを作りたい。

f:id:drken1215:20210104024203p:plain

入力としては、各棒  i についての

  • 左端から支点までの長さ  P_{i}
  • 右端から支点までの長さ  Q_{i}
  • 左端からつながっている棒の index  L_{i} (重りの場合は 0)
  • 右端からつながっている棒の index  R_{i} (重りの場合は 0)

が与えられる。重りの重さはすべて整数値でなければならない。考えられるモビールをすべて考えたときの、重りの重さの総和の最小値を求めよ。

制約

考えたこと

モビールは実際には木に過ぎない。木 DP と同じ発想が使える。

  • dp[i]モビール  i 以下のみを考えたときの、重りの重さの総和として考えられる最小値

とする。さて、dp[i] を求めるとき

  • 左側のモビールについての重さの総和を  L (= dp[L[i]])
  • 右側のモビールについての重さの総和を  R (= dp[R[i]])

としよう。このとき、左側の重さの総和は  L の倍数となり、右側の重さの総和は  R の倍数となる。よって、てこの原理を考慮して

 LP_{i}x = RQ_{i}y

を満たす正の整数  x, y の最小値を求めればよいということになる。具体的には、

  •  G = {\rm GCD}(LP_{i}, RQ_{i})

としたとき、

とすればよいことがわかる。よって、

  • dp[i] =  \frac{LR}{G}(P_{i} + Q_{i})

と求められた。このような DP を再帰的に実施すれば OK。なお、最初に根の位置を特定する必要がある。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> P(N), Q(N), left(N), right(N);
    vector<int> par(N, -1);
    for (int i = 0; i < N; ++i) {
        cin >> P[i] >> Q[i] >> left[i] >> right[i];
        --left[i], --right[i];
        if (left[i] != -1) par[left[i]] = i;
        if (right[i] != -1) par[right[i]] = i;
    }

    // 根を特定
    int root = -1;
    for (int v = 0; v < N; ++v) if (par[v] == -1) root = v;

    // DP
    auto rec = [&](auto self, int v) -> long long {
        // 葉の場合
        if (v == -1) return 1;

        long long L = self(self, left[v]);
        long long R = self(self, right[v]);
        long long G = gcd(L*P[v], R*Q[v]);
        return L * R * (P[v] + Q[v]) / G;
    };
    cout << rec(rec, root) << endl;
}