F - Tournament Editorial by lynmisakura
スマートではないけれど考察ステップに対して自然に実装できると思うのでここで書いてみます.
区間 [l,r) について考えます. m = (l+r)/2 として,区間 [l,m) と区間 [m,r )から勝ち上がってきた人同士が最後にじゃんけんをして区間 [l,r) の優勝者が決まるというシナリオを考えたいですが, 「左部分木」から勝ち上がってきた人が優勝する場合と「右部分木」から勝ち上がってきた人が優勝する場合とで分けて考える必要がありそうです.ここで, [l,r) で優勝する人を固定して考えてみましょう.
[l,m) に属する人 i が最終的に優勝するとした場合の得点の最大値は,
- 区間[l,m) において,人 i が優勝する場合の得点の最大値
- 区間[m,r) における得点の最大値
- 人 i が最後に行ったジャンケンの結果で新たに獲得した得点
の合計になります.つまり,「区間について優勝者を指定した場合の最大値」と「区間について優勝者を指定しない場合の最大値」の2種類の配列があると見通しがよさそうです.
- f[i] := 2分木の頂点 i に対応した区間\([l,r)\)について解いた場合の答え. f[0]が最終的な答えに対応する.
- g[i][j]:= 2分木の頂点 i に対応した区間\([l,r)\)において,人 j \(\in\) [l,r) が優勝した場合の得点の最大値.
とします.これを再帰的に求めていくことを考えます.
関数 \(\mathsf{rec(i,h,l,r)}\) を, 2分木の頂点 i に対応した区間\([l,r)\)について解く(つまり対応する f,g を埋める)関数とします.h は頂点 i の高さとして明示します.つまり,はじめに\(\mathsf{rec(0,n,0,2^n)}\)を呼び出す形になります.
初めに \(\mathsf{rec(2*i+1,h-1,l,m),rec(2*i+2,h-1,m,r)}\) を呼び出すことで,子ノードに対応した f,g の値を埋めておきます.
次に,区間 [l,r) において誰が優勝するかを全て試すことで g[i][ * ] がもとまり, f[i] = max g[i][ * ] として区間 [l,r) の解を求めることができます.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define chmax(a, b) a = max(a, b)
int main(void) {
cin.tie(0);
ios::sync_with_stdio(false);
// cout << fixed << setprecision(12);
int n;
cin >> n;
vector c(1 << n, vector(n, 0LL));
vector gain(1 << n, vector(n, 0LL));
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
cin >> c[i][j];
if (j) {
gain[i][j] = c[i][j] - c[i][j - 1];
} else {
gain[i][j] = c[i][j];
}
}
}
/////////////////////////////////
const ll INF = 1e17;
vector<ll> f(1 << (n + 1), -INF);
vector<vector<ll>> g(n + 1, vector<ll>(1 << n, -INF));
auto rec = [&](auto& self, int i, int h, int l, int r) -> void {
if (l == r - 1) {
g[h][l] = 0;
f[i] = 0;
return;
}
self(self, 2 * i + 1, h - 1, l, (l + r) / 2);
self(self, 2 * i + 2, h - 1, (l + r) / 2, r);
ll mx = -INF;
for (int p = l; p < (l + r) / 2; p++) {
chmax(g[h][p], g[h - 1][p] + gain[p][h - 1] + f[2 * i + 2]);
chmax(mx, g[h][p]);
}
for (int p = (l + r) / 2; p < r; p++) {
chmax(g[h][p], g[h - 1][p] + gain[p][h - 1] + f[2 * i + 1]);
chmax(mx, g[h][p]);
}
f[i] = mx;
};
rec(rec, 0, n, 0, 1 << n);
cout << f[0] << '\n';
}
posted:
last update: