ICPC2018国内予選 H問題

今年もチームcatsatmatで出場しました。4位で通過出来て嬉しかったです。

• H問題

前原先生の記事
木上のナップサック問題
でだいたいわかりますが、コードを載せておきます。

まず、素直な解法として、dp[v][c] := vの部分木についてコストcで得られるmaxとおくとO(nkk)ですが、このままでは高速化が難しいです。

ポイントは、各頂点vの子たちを、vの必要量の昇順に並べておくと、ある子に潜ることが出来る時その手前の子たちも全部使えて、このことを利用するとdpの配列を持ちつつdfsすることができるという点です。これだけでオーダーが良くなるのは不思議な感じですね。これに加えて各頂点に使える上限があるので面倒になっています(このパートはスライド最小値をやると線形で解けます)　よって時間計算量はO(Case * NK)です。100*100*10^5 = 10^9を8秒なので結構実装に気を使わないといけません。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;

const ll inf = -1e18;
const int MN = 110;
const int MK = 100010;

inline void chmax(ll &x, ll y) { if (x < y) x = y; }

int n, k;
vi g[MN];
int h[MN], s[MN], lo[MN];
vl dp[MN];
int deq[MK];

void dfs(int v, vl vec) {
    vl &res = dp[v];
    
    int l = 0, r = 0;
    
    for (int i = 0; i <= k; ++i) {
        if (vec[i] != inf) {
            ll x = vec[i] - (ll)i * s[v];
            while (l+1 <= r) {
                int id = deq[r-1];
                if (vec[id] - id * (ll)s[v] <= x) {
                    --r;
                } else {
                    break;
                }
            }
            deq[r++] = i;
        }
        if (l+1 > r) {
            res[i] = inf;
            break;
        } else {
            res[i] = vec[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
            if (deq[l] <= i - h[v]) {
                ++l;
            }
        }
    }
    
    for (int to : g[v]) {
        dfs(to, vec);

        vl &nx = dp[to];
        
        for (int i = 0; i <= k; ++i) {
            chmax(vec[i], nx[i]);
        }
        
        l = r = 0;
        for (int i = 0; i <= k - lo[to]; ++i) {
            if (nx[i] != inf) {
                ll x = nx[i] - (ll)i * s[v];
                while (l+1 <= r) {
                    int id = deq[r-1];
                    if (nx[id] - id * (ll)s[v] <= x) {
                        --r;
                    } else {
                        break;
                    }
                }
                deq[r++] = i;
            }
            if (l+1 > r) {
                nx[i] = inf;
                break;
            } else {
                ll val = nx[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
                chmax(res[i + lo[to]], val + (ll)s[v] * lo[to]);
                if (deq[l] <= i - (h[v] - lo[to])) {
                    ++l;
                }
            }
        }
    }
}

int main() {
    while (cin >> n >> k, n) {
        rep(i, n) dp[i] = vl(k + 1, inf);
        rep(i, n) g[i].clear();
        rep(i, n) cin >> h[i];
        rep(i, n) cin >> s[i];
        for (int i = 1; i < n; ++i) {
            int p; cin >> p; --p;
            g[p].push_back(i);
        }
        for (int i = 1; i < n; ++i) {
            cin >> lo[i];
        }
        rep(i, n) {
            sort(g[i].begin(), g[i].end(), [&](int a, int b) {
                return lo[a] < lo[b];
            });
        }
        vector<ll> vec(k + 1, inf);
        vec[0] = 0;
        dfs(0, vec);
        cout << *max_element(dp[0].begin(), dp[0].end()) << endl;
    }
    return 0;
}