AtCoder Beginner Contest 281 F,G問題メモ

AtCoder Beginner Contest 281

F - Xor Minimization

• $N$ 個の非負整数の集合 $A=\{A_1,...,A_N\}$
• 好きな整数 $x$ を選び、$A$ の各項を、$x$ を XOR したものに置き換えた集合を $B$ とする
• $B$ の最大値としてあり得る最小値を求めよ
• $1 \le N \le 150000$
• $0 \le A_i \lt 2^{30}$

（※以下、桁は2進数での桁を表し、小さい方から（1,2,4,8,16,… を表す桁の順に）1,2,3,… 桁目とする）

再帰で分割していく。

もし、$A$ の中で $d$ 桁目が'0'のものと'1'のものが混在していたら、 どのように $x$ を選ぼうと、$B$ でも'0'と'1'が混在してしまう。

逆に、全て'0'か全て'1'なら、$B$ の全てで必ず $d$ 桁目は'0'にできる。

それを踏まえて、上位bitから考える。

いま、$A$ の中で0と1が混在しているような最上位桁を $d$ とする。
すると、$B$ の最大値も $d$ 桁にならざるを得ない。

$A$ を「$d$ 桁目が0であるグループ」「1であるグループ」に分割すると、 同じグループの操作後の $d$ 桁目は同じになる。

さて、どちらのグループの操作後の $d$ 桁目を0にし、どちらを1にすべきか？

操作後の $d$ 桁目が0になるグループは、その時点で必ず1になるグループより小さくなることが確定するので、 $d-1$ 桁目以降がどんなに大きくなってもかまわない。
$x$ を決める際は、1になるグループの $d-1$ 桁目以降を最小化することに注力すればよい。

よって、それぞれのグループで $d-1$ 桁以降のみで全体と同じ問題を解き、「もしこっちのグループを1にした場合、最小値はいくつになる？」を調べる。

その結果、最大値が小さくなる方を、操作後に $d$ 桁目が1となるようにすればよい。

d桁目
v        ｸﾞﾙｰﾌﾟ
00101101 -,        _0101101  グループ0のみで
01010101  | 0  →  _1010101  全体と同じ問題を解いた答えをpとする
01101110 -'        _1101110
10111000 -,
11100011  | 1  ┐  _0111000  グループ1のみで
11001100 -'    └> _1100011  全体と同じ問題を解いた答えをqとする
                   _1001100

p <= q なら、グループ0の操作後のd桁目が 1 となるようにし、答えは 10000000 + p
p >  q なら、グループ1の操作後のd桁目が 1 となるようにし、答えは 10000000 + q

これを再帰的に処理すれば良い。

処理の途中でグループのサイズが1個になったら、 後はその1個が操作後に完全に0になるような $x$ を選べば良いので、（分割問題の答えは $0$） 以降の桁は探索を打ち切れる。

仮に打ち切らず最終桁まで処理したとしても、$N$ 個の要素がそれぞれ $\log_2{A_i}$ 回、 bitが0か1かチェックされたり分割されたりすることになるので、$O(N \log{A_{max}})$ で処理できる。

Python3

def check(d, group):
    if len(group) == 1:
        return 0

    zero = set()
    one = set()
    bit = 1 << d
    for a in group:
        if a & bit:
            one.add(a ^ bit)
        else:
            zero.add(a)

    if len(zero) == 0:
        return check(d - 1, one)
    if len(one) == 0:
        return check(d - 1, zero)
    if len(zero) == 1 or len(one) == 1:
        return bit

    return min(check(d - 1, zero), check(d - 1, one)) | bit


n = int(input())
aaa = set(map(int, input().split()))
print(check(29, aaa))

G - Farthest City

• $N$ 頂点の単純連結無向グラフの内、以下の条件を満たすものの個数を $M$ で割ったあまりで答えよ
• 条件
  • 頂点1からの最短距離を考えると、頂点 $N$ が単独で最も遠い頂点である
  • 言い換えると、頂点 $u=2,...,N-1$ の全てについて、$1→u$ の最短距離が、$1→N$ の最短距離より真に小さい
• $3 \le N \le 500$

$M$ が素数とは限らないので、いつもの逆数modや、FFTによる畳み込みは使えない点に注意。
まぁ $N$ が小さいので、二項係数 ${}_nC_r$ なんかは $n \le N$ の範囲なら事前計算してしまえる。

素直(?)に考えると3次元DPで遷移にも $N$ かかって $O(N^4)$ 解法が思いつくが、 実は1次元省略して $O(N^3)$ にできる、という問題。

• $DP[i,j,k]=$ 頂点1からの最短距離が $i$ までを考えて、頂点1を含め $j$ 個を既に使っていて、特に最短距離が $i$ である頂点数が $k$ であるようなグラフの個数

距離   1   2  ...    i

  ①--○--○- ...  -○
    `-○    ` ...  -○
                   -○
                    ↑  ...k個
 └─────────┘ ...j個

ここに、最短距離が $i+1$ の頂点を $l$ 個追加することを考える。

• ① $l$ 個の選び方
  • 既に使った頂点と $N$ を除く $N-j-1$ 個から $l$ 個選ぶ
  • ${}_{N-j-1}C_{l}$ 通り
• ② 最短距離が $i$ である頂点群と $i+1$ である頂点群の間の辺の張り方
  • $i+1$ の頂点1つにつき、$i$ の $k$ 個のそれぞれとの辺を張る/張らないを決められる
    • $i-1$ 以前と辺を張ったら最短距離が $i+1$ でなくなるため、あくまで張るのは直前 $i$ との間のみ
    • $2^k$ 通りの張り方があるが、そのうち「全て張らない」パターンだけは除く必要がある
    • よって、1つにつき $2^k-1$ 通り
  • それが $l$ 個なので $(2^k-1)^l$ 通り
• ③ $i+1$ 同士の辺の張り方
  • 同じ最短距離同士は張っても問題ない
  • $\frac{l(l-1)}{2}$ の全ての頂点間につき、張る/張らないを決められる
  • $2^{l(l-1)/2}$ 通り

これらを掛け合わせたものとなる。

• $DP[i+1,j+l,l]+=DP[i,j,k] \times ① \times ② \times ③$

実は、遷移の式を見ても $i$ が出てこないことからもわかるとおり、$i$ の次元は省略できる。
最短距離が異なっていても「今までに $j$ 個使って、そのうち直前が $k$ 個」という情報さえ一致していれば同じ遷移ができる。

• $DP[j,k]=$ 頂点1を含め $j$ 個を既に使っていて、特に最短距離が最も長い頂点が $k$ 個であるようなグラフの個数
• $DP[1,1]=1$
• $DP[j+l,l]+=DP[j,k] \times ① \times ② \times ③$

さて、$j=N-1$ まで埋め終えたとして、最後に頂点 $N$ との辺を考慮しつつ合計する。

末尾 $k$ 個と頂点 $N$ 間の辺の張り方は、上記②の考え方と同じく $2^k-1$ 個ある。
$DP[N-1,k] \times (2^k-1)$ を $k=1,...,N-2$ で合計すれば答え。

Python3

import os
import sys

import numpy as np


def solve(inp):
    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    n, m = inp

    ncr = np.zeros((n, n), np.int64)
    ncr[0, 0] = 1
    for i in range(1, n):
        ncr[i, 0] = 1
        ncr[i, i] = 1
        for j in range(1, i):
            ncr[i, j] = (ncr[i - 1, j - 1] + ncr[i - 1, j]) % m

    pow2 = np.zeros(n * n, np.int64)
    pow2[0] = 1
    for i in range(1, n * n):
        pow2[i] = pow2[i - 1] * 2 % m

    dp = np.zeros((n, n), np.int64)
    dp[1, 1] = 1

    for j in range(2, n):
        for k in range(1, j):
            for l in range(1, j - k + 1):
                if dp[j - k, l] == 0:
                    continue
                tmp = dp[j - k, l] * ncr[n - 1 - (j - k), k] % m
                tmp *= mod_pow(pow2[l] - 1, k, m)
                tmp %= m
                tmp *= pow2[k * (k - 1) // 2]
                dp[j, k] += tmp
                dp[j, k] %= m

    ans = 0
    for k in range(1, n):
        ans += dp[n - 1, k] * (pow2[k] - 1)
        ans %= m

    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(ans)