Editorial for 第2回卬高杯 K問題 - Bully Dunsparce
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
C++
まず、Dunsparceの移動の言いかえを行います。 これは、①今いる部屋より気温の高い部屋への移動 ②今いる部屋より気温の低い部屋への移動 の二パターンに大きく分けられます。
①今いる部屋より気温の高い部屋への移動 この時、"元の部屋から繋がっていて、なおかつ行こうとしている部屋よりも気温が高い部屋"をすべて封鎖した後に移動する必要があります。 なぜなら、そのような部屋が存在するときには、今行こうとしている部屋ではなく、その部屋へと移動しようとしてしまうためです。また、このような部屋以外は封鎖する必要がないことも、そのような部屋の封鎖の手順があることも証明できます。
②今いる部屋より気温の低い部屋への移動 この時、"元の部屋から繋がっていて、なおかつ行こうとしている部屋よりも気温が高い部屋"と、"現在いる部屋"をすべて封鎖する必要があります。 なぜなら、上記の①の時の理由に加えて、現在いる部屋のほうが行こうとしている部屋よりも気温が高いと、Dunsparceが移動を行おうとしないので、無理やり今いる部屋を封鎖して追い出す必要があるからです。
では、このような移動の言いかえを行ったので、これを利用し、最大のスコアを取るのはどのような場合かを考察します。
まず、①、②のような移動をするときに"元の部屋から繋がっていて、なおかつ行こうとしている部屋よりも気温が高い部屋"、さらに"現在いる部屋よりも気温の高い部屋"をただ封鎖するような行動は、スコアの減少につながります。 なぜなら、そのような封鎖を行う際に、封鎖しようとしている部屋に行った後、その部屋から戻ってくる方が必ずスコアがその分加算され、大きくなるからです。
次に、今いる部屋よりも気温の低い部屋への移動を行う場合を考えます。このような時、現在いる部屋を封鎖する、以外の操作は、あまり考えなくてもよいことがわかります。 なぜなら、現在いる部屋を封鎖すれば、それ以降現在いる部屋への移動はなくなり、現在いる部屋から繋がっている部屋へのアクセスを考える必要がなくなるからです
すべてのDunsparceの移動は、この二つの移動のうちの必ずどちらかになります。 そのため、一つ目の移動をできるだけしきってから、二つ目の移動を行う、という行動が、最大のスコアを生むということになります。
そのような行動のスコアを効率よく求める方法は、繋がっている部屋を部屋の気温の高い順にみていくということです。 具体的にどのように見ていけばよいか、というと、気温の高い順に部屋をsortした後、①下に行って戻ってくることができるような制約で行動した時の最大のスコア と ②下へ行ったきりになってもいいようなときの最大のスコア の二通りのdpテーブルをもち、それぞれを更新することで答えを出すことができます。
つまり、そのようなdpテーブルをそれぞれ dp1、dp2 と、置くと、max(Σ(j=0→i-1)dp1[j(ただし、Tjは現在いる部屋の気温より大きい)] + dp2[i])(iは、0～つながっている部屋の数)というものを求めることで再帰的に木dpを行うと最大のスコアを得ることができます。
詳細はコードを確認してください。
C++20
#include <bits/std_abs.h> // for abs
#include <ext/alloc_traits.h> // for __alloc_traits<>::value_type
#include <algorithm> // for max, copy, sort
#include <functional> // for greater
#include <iostream> // for cin, istream, endl, basic_istream<>::_...
#include <memory> // for allocator_traits<>::value_type
#include <utility> // for pair
#include <vector> // for vector
using namespace std;
using ll = long long;
const ll inf = ((1LL << 62) - (1LL << 31));
vector<ll> t;
vector<vector<ll>> g;
vector<ll> dp1, dp2;
void solve1(ll x, ll p)
{
vector<pair<ll, ll>> v;
for (auto y : g[x])
{
if (y == p)
continue;
solve1(y, x);
v.push_back({t[y], y});
}
sort(v.begin(), v.end(), greater<pair<ll, ll>>());
ll ret1 = 0, ret2 = 0;
ll sum = 0;
for (ll i = 0; i < (int)v.size(); i++)
{
ll y = v[i].second;
ret2 = max(ret2, sum + dp2[y] + abs(t[y] - t[x]));
if (t[y] > t[x])
sum += dp1[y] + 2 * (t[y] - t[x]);
}
ret1 = sum;
dp1[x] = ret1;
dp2[x] = max(ret1, ret2);
}
int main()
{
ll n;
cin >> n;
t.resize(n);
g.resize(n);
for (ll i = 0; i < n; i++)
cin >> t[i];
for (ll i = 0; i < n - 1; i++)
{
ll a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dp1.resize(n, -inf);
dp2.resize(n, -inf);
solve1(0, -1);
cout << dp2[0] << endl;
}
Comments