はまやんはまやんはまやん

hamayanhamayan's blog

トーナメント [Kyoto University Programming Contest 2020 Spring K]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#KUPC2020Spring/problems/K

前提知識

  • ダブリングDP

解説

どこから手を付けるかと言うと、まずは1クエリでの計算である。 クエリ問題での方針は、「毎回高速に計算」「一気に前計算しておく」「差分だけ計算する」と これくらいしかないので、すべて考察してみる。 今回は一気に前計算しておくことで高速に求めることができる。

これはシフト問題でよくやるテクなのだが、同じ数列を二回繰り返して、見る区間を1ずらすことでシフトしたようにデータを見ることができるテクがある。 シフトは高コストなので、このテクを使って、シフトを見る区間のずらしとして考えよう。

考察のモチベーションは実はここからではなく、毎回愚直に計算する場合から発生する。 トーナメントを木構造として考えてみると、完全二分木として考えることができる。 そして、2回シフトを行うと、根から直接つながる2つの部分木のうち、片方の部分木は丸々同じものが残る。 こちら側は、同じ計算結果を使いまわせるのではないか? しかも、もう片方の部分木のそのまた部分木は片方が丸々同じものが残る。 メモ化を適切に行うと改めて計算が必要な部分はそんなに多くない。 計算としてはセグメントツリーととてもよく似ている。セグメントツリーの要領でメモ化されている部分はそのまま答えて、そうでないところを改めて計算していく。 部分木を区間として考えてみると、計算過程で出てくる状態は(区間の左端, 区間の長さ)となる。 区間の左端は2N+1通りで、区間の長さは、1,2,4,...2NのN+1通りなので、メモ化すべき状態数はACできる量。 計算もそんなに重くないので、適切にメモ化をすることで間に合う。

自分はここから発想を得て、ダブリングDPを構築した。 ダブリングの考え方を動的計画法に輸入したものである。 dp[p][L] := 区間の長さが2pで、左端がLの区間において、トーナメントを行ったときの勝利者 dp[p][L]はdp[p-1][L]とdp[p-1][L + 2p-1]から計算ができる。 ダブリングを理解していれば、メモ化よりもこっちのほうがわかりやすいかもしれない。

int N; string S; int P[1 << 19];
int dp[19][1 << 19];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, 1 << N) cin >> P[i];
    rep(i, 0, 1 << N) P[(1 << N) + i] = P[i];

    rep(i, 0, 1 << (N + 1)) dp[0][i] = P[i];
    rep(p, 1, N + 1) rep(L, 0, 1 << (N + 1)) {
        int R = L + (1 << (p - 1));
        if (1 << (N + 1) <= R) continue;
        int x = dp[p - 1][L];
        int y = dp[p - 1][R];
        tie(x, y) = make_pair( min(x, y), max(x, y) );

        if (S[y - x - 1] == '0') dp[p][L] = x;
        else dp[p][L] = y;
    }

    rep(i, 0, 1 << N) printf("%d\n", dp[N][i]);

}