AtCoder Regular Contest 205 (Div. 2) D,E問題メモ

AtCoder Regular Contest 205 (Div. 2)

ARCの中でも全完しやすいセットだったかも。
それだけにどこかで詰まると一気にパフォが落ちる怖さ。

D - Non-Ancestor Matching

問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点の根付き木が与えられます。頂点 $1$ が根で、頂点 $i$ $(2 \le i \le N)$ の親は頂点 $p_i$ $(1\le p_i \lt i)$ です。はじめ、全ての頂点は白で塗られています。
あなたは以下の一連の操作を $0$ 回以上何回でも行うことができます。
- 以下の条件を全て満たす整数の組 $(u,v)$ を選ぶ。
  - $1\le u \lt v \le N$
  - 頂点 $u$ と頂点 $v$ はどちらも白で塗られている。
  - $u$ は $v$ の祖先ではない。
- 頂点 $u$ と頂点 $v$ を黒で塗る。

あなたが適切な順序で操作を行ったとき、最大で何回操作ができるか求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 5\times 10^4$
$2\le N\le 5\times 10^5$
$1\le p_i \lt i$
全てのテストケースにおける $N$ の総和は $5\times 10^5$ 以下
入力される値は全て整数

解法

木DPというと通常、葉から根に向かっておこなう動的計画法だが、今回は逆に根から考えないと上手くいかない。
ただしDPというよりは貪欲法であり、考察はしやすい。
（ただ、実装でハマると、有効なランダムテストを作るのが難しく、デバッグしにくい。。。）

まず、根である頂点 $1$ は、他の全ての頂点の祖先のため、ペアになり得ない。

頂点 $1$ が1個の子しか持たない場合、$1$ を取り除き、$1$ の唯一の子を根として考えても答えは変わらない。
以下、根は複数の子を持つとする。

頂点 $1$ の子の部分木のうち、最大の頂点数を持つ子（の1つ）を $v$、その頂点数を $C_v$、それ以外の子の頂点数を $C_{others}$ とする。
両者の合計を $C_{total}=C_v+C_{others}$ とする。

$C_v \le C_{others}$ の場合、適当に頂点数が多い2つの部分木から1頂点ずつペアにしていけば、 $\lfloor \frac{C_{total}}{2} \rfloor$ ペア作ることができ、これが文句なく最大である。

逆に $C_v \gt C_{others}$ の場合、$C_{others}$ 個の頂点は全て $v$ 側とペアにするのがよい。

      ①
    ／｜＼
  v◎ ◎ ☆
 ／｜＼  ｜\     ○: 未マッチング頂点
☆ △ ○ △□
 ／｜＼
○ □ ○

これを、たとえば右側の子の△と□をペアにするなど、 $C_{others}$ 同士でペアにするように組み替えて得することはない。

この結果、$v$ 側の部分木の中の $C_v-C_{others}$ 個の頂点が、ペアにされず残ることになる。
この残る $C_v-C_{others}$ 個の頂点は、好きに選ぶことができる。（後から決めて問題ない）

すると今度は頂点 $v$ を根として、「最大 $\lfloor \frac{C_v-C_{others}}{2} \rfloor$ ペアまで」という制限付きで、再帰的に同じ問題に帰着することができる。

$f(頂点番号, 増やせる残りペア数)$ のような再帰関数で、$f(1, (N-1)/2)$ からはじめて、残りペア数を使い切るか、葉まで到達したら終了。

計算量は $O(N)$ となる。

Python3

根が子を1つしか持たない場合はそのまま子に処理を引き継ぐが、その際の「残りペア数」に注意。
「残りペア数」の値までそのまま引き継いでしまうと、子の部分木内の頂点数で可能な個数を超えてしまい、誤った結果となりうる。

   (u)    (u)へは残りペア数 2 で来たとしても、
   ↓
   (v)    (v)に引き継がれた時点で、(v)自身はペアにすることはかなわなくなるので、
 ／｜＼   残りペア数は 1 とするのが正しい。
○ ○ ○

毎回、$\lfloor \frac{C_v-1}{2} \rfloor$ で下限を切る必要がある。

import sys

sys.setrecursionlimit(500_005)


def solve(n, parents):
    children = [[] for _ in range(n)]
    for i, p in enumerate(parents, start=1):
        p -= 1
        children[p].append(i)

    subtree_size = [0] * n
    for u in range(n - 1, -1, -1):
        subtree_size[u] = sum(subtree_size[v] for v in children[u]) + 1

    def sub(u, rem):
        if len(children[u]) == 0:
            return 0
        if len(children[u]) == 1:
            v = children[u][0]
            # return sub(v, min(rem, subtree_size[v] - 1))
            return sub(v, rem)

        total = 0
        max_ss = 0
        max_v = -1
        for v in children[u]:
            ss = subtree_size[v]
            total += ss
            if ss > max_ss:
                max_ss = ss
                max_v = v

        others = total - max_ss
        if max_ss <= others:
            return min(total // 2, rem // 2)

        if others * 2 >= rem:
            return min(others, rem // 2)

        nxt = sub(max_v, rem - others * 2)
        return min(rem // 2, others + nxt)

    ans = sub(0, n - 1)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    parents = list(map(int, input().split()))
    ans = solve(n, parents)
    print(ans)

E - Subset Product Problem

問題文

長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$k=1,2,\ldots,N$ に対し以下の問題を解いてください。
$A_i$ と $A_k$ のビット単位 $\mathrm{OR}$ 演算が $A_k$ となるような $1$ 以上 $k$ 以下の整数 $i$ 全てに対する $A_i$ の総積を $998244353$ で割ったあまりを求めてください。

制約

$1\le N\le 4\times 10^5$
$0\le A_i \lt 2^{20}$
入力される値は全て整数
実行制限時間:6秒

解法

$A_i$ の上限が $10^9$ とかでなく $2^{20}$ 程度に抑えられていることには意味がありそう。

TLEとなるが愚直解法としては、以下のようなものがある。簡単のため、$\max(A)$ を $6$ bit として考える。

Memo[i] = 1 で初期化（i=000000～111111）

k=1,2,... の順に、

① 答えを求める。
   k に対しての答えは、Ak * Memo[Ak]

② 後続の k のために更新する。
   たとえば Ak = 010110 だったら、
   それを部分集合に含む値 x = 010110, 011111, 110110 などについて、
   Memo[x] *= Ak としていけばよい。

これ、$A_k$ にいっぱいbitが立っていれば更新箇所も少ないが、ちょっとしかbitが立っていないと更新するべき $x$ の個数が多くなり、TLEとなってしまう。

また、以下のような解法もある。

Memo[i] = 1 で初期化

k=1,2,... の順に、

① 答えを求める。
   ans = Ak で初期化し、Ak の部分集合について、
   （Ak = 010110 だったら、x = 000100, 010010, 000000 など）
   ans *= Memo[x] としていけばよい。

② 後続の k のために更新する。
   Memo[Ak] *= Ak

前者は①が軽く②が重い。①ですぐ答えを求められるよう、Memoは常に「答えがそのまま入っている状態」が保たれている。
後者は①が重く②が軽い。②では各 $A_k$ の箇所だけ更新しておき、①でそれをかき集める方法となる。

このようなトレードオフの2つの解法がある場合、平方分割で上手くいくことがある。
仮に $2^{10}$ ずつに平方分割することができれば、$N \times 2^{10} \simeq 4 \times 10^8$ となり、重めだが制限時間も長いため、間に合いそうなオーダーとなる。

$A_k$ の20bitのうち、上位10bitを $p_k$、下位10bitを $q_k$ とする。

①では $p_k$ を前者、$q_k$ を後者の方法で答えを求める。
つまり、$p_k$ を固定し、$q_k$ の部分集合 $x$ について、$\mathrm{Memo}[p_k, x]$ の値をかけていく。

②では $q_k$ を前者、$p_k$ を後者の方法で更新する。
つまり、$q_k$ は固定し、$p_k$ を部分集合に含む値 $x$ について $\mathrm{Memo}[x, q_k]$ を更新する。

これで、$O(N \sqrt{A_{\max}})$ で答えが求められる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    aaa = inp[1:]
    MOD = 998244353

    memo = np.ones(1 << 20, np.int64)
    mask = (1 << 10) - 1
    ans = np.zeros(n, np.int64)

    for i in range(n):
        a = aaa[i]
        u = a >> 10
        l = a & mask
        tmp = a

        b = u
        while True:
            tmp *= memo[b << 10 | l]
            tmp %= MOD
            if b == 0:
                break
            b = (b - 1) & u
        ans[i] = tmp

        r = l ^ mask
        b = r
        base = (u << 10) | l
        while True:
            memo[base | b] *= a
            memo[base | b] %= MOD
            if b == 0:
                break
            b = (b - 1) & r

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

目次

AtCoder Regular Contest 205 (Div. 2) D,E問題メモ

D - Non-Ancestor Matching

問題文

制約

解法

E - Subset Product Problem

問題文

制約

解法