東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）G,Ex問題メモ
問題
$2N$ 個の非負整数 $A_1,...,A_{2N}$ がある
2個ずつ組み合わせてbitwise-XORし、$N$ 個の非負整数を作ることを考える
中央値として考えられる最大値を求めよ
$1 \le N \le 10^5$
$0 \le A_i \lt 2^{30}$
解法
中央値として達成できる最大値、みたいな問題は、答えを二分探索して、
「$k$ 以上の値を半数（$\left \lfloor \dfrac{N+1}{2} \right \rfloor$）以上にできるか？」
の判定問題に落とし込む解法がよくある。
上の桁からの再帰
「XORが $k$ 以上になるペアを最大何個作れるか？」を解く。
2進数で上の桁から再帰的に「$k$ 以上にするためのペア」で分類していく。
$A_i$ のうち、2進数で $d$ 桁目が0のやつの多重集合を $S_{d0}$、1のやつを $S_{d1}$ とする。
$S_{d0},S_{d1}$ から1つずつ取ったペア（(0,1)ペア）のXORは $d$ 桁目が1、
同じ中から2つ取ったペア（(0,0),(1,1)ペア）は0になる。
この時、上の桁から貪欲に、その桁が'1'となるペアを最大化していってよい。（理由は後述）
d
A 1011 Sd1 Sd0とSd1を優先的にペアにし、
1001______ （今回はSd0の方が多いので）
0111 Sd0 残ったSd0同士でペアにする
0101
0100
0010
0000
0000
$k$ 以上のペアを数えるには、
$k$ の $d$ 桁目が '1'
$k$ の $d$ 桁目が '0'
$\min(|S_{d0}|,|S_{d1}|)$ 個のペアは $k$ 以上確定
残り（$S_{d0},S_{d1}$ のうち要素数が多い方）の中で、次の桁以降で $k$ 以上となるペアを最大化
ただし、あくまで(0,1)ペアを取った残りを組み合わせる前提なので、上限は $\frac{要素数の差分}{2}$ 以下
なので、徐々に「これとこれの中から1個ずつ取らないといけない」
「この中同士でペアにしないといけない」制約が細分化されていく。
上から $x$ 桁を処理した後の制約内のペアは、どのように組み合わせてもXORの結果の上から $x$ 桁が全て同じになる。
また、$k$ 以上・未満が確定したものは探索の必要は無いので、実質的に調べる中では、上から $x$ 桁は $k$ とも同じになる。
2桁目以降
2桁目以降は、既に2つに分けられ「$A$ と $B$ から1つずつ選んでね」という制約付きで上から降ってくることがある。
$A,B$ それぞれで、着目中の桁 $d$ の0,1で4グループに分けて、$A_0,A_1,B_0,B_1$ とする。
$k$ の $d$ 桁目が '1'
$k$ の $d$ 桁目が '0'
$(A_0,B_1)$ および $(A_1,B_0)$ で優先的にペアを作る
$A_0,B_0$ がともに余るとき、この2つから1つずつ選んで $k$ 以上を最大化
$A_1,B_1$ がともに余るとき、この2つから1つずつ選んで $k$ 以上を最大化
とすればよい。
再帰関数
$f(A, k, d)=A$ から2個ずつ取って $k$ 以上のペアを最大化した時の個数、$d$ 桁目に着目
$g(A, B, k, d)=A,B$ から1個ずつ取って $k$ 以上のペアを最大化した時の個数、$d$ 桁目に着目
の2つの関数を定義しておくと、上記の遷移を実現できる。
$f(入力として与えられるA, 二分探索で試行するk, 29)$ が求めるもの。
再帰の末端は、
最後の桁まで行き着いたら（$d=-1$）
$f(A,k,d)$ なら $\left \lfloor \dfrac{|A|}{2} \right \rfloor$
$g(A,B,k,d)$ なら $\min(|A|,|B|)$
途中で打ち切れる条件
$f(A,k,d)$なら $|A| \lt 2$ のとき、結果は0
$g(A,B,k,d)$ なら $\min(|A|,|B|)=0$ のとき、結果は0
貪欲でよい証明
(0,1)ペアは優先的に作ってよいとしたが、本当か？
(0,1)最大 その他の組み合わせ方例
Sd1 1???? x2 → 1???? (0,1) 0???? (1,1)
Sd0 0???? x6 1???? (0,1) 0???? (0,0)
0???? (0,0) 0???? (0,0)
0???? (0,0) 0???? (0,0)
↑k以上がこっちの方が多くなることはある？
ない。
$k$ の $d$ 桁目が'1'のとき
$k$ の $d$ 桁目が'0'のとき
(0,0)ペア、(1,1)ペアいずれかの中に $k$ 以上にできないものがあるなら、それをバラして(0,1)として組み合わせた方がよい
(0,0):x,(1,1):o → (0,1):o,(0,1):o
全て $k$ 以上にできるとしても、(0,1)として組み合わせても損しない
ので、(0,1)ペアは優先的に組み合わせることにして問題ない。
計算量
1回の判定問題で、1要素当たり最大 $O(\log{A_{max}})$ 回の再帰で評価されるので、$O(N\log{A_{max}})$
二分探索するので、$O(N(\log{A_{max}})^2)$
Python3
def solve(n, aaa):
n2 = (n + 1) // 2
l = 0
r = 1 << 30
while l + 1 < r:
m = (l + r) >> 1
if calc1(aaa, m, 29) >= n2:
l = m
else:
r = m
return l
def calc1(aaa, m, d):
if d == -1:
return len(aaa) // 2
if len(aaa) < 2:
return 0
bit = 1 << d
aaa0 = []
aaa1 = []
for a in aaa:
if a & bit:
aaa1.append(a)
else:
aaa0.append(a)
if m & bit:
return calc2(aaa0, aaa1, m, d - 1)
else:
if len(aaa0) > len(aaa1):
aaa0, aaa1 = aaa1, aaa0
diff = len(aaa1) - len(aaa0)
res = len(aaa0) + min(diff // 2, calc1(aaa1, m, d - 1))
return res
def calc2(aaa0, aaa1, m, d):
if d == -1:
return min(len(aaa0), len(aaa1))
if len(aaa0) == 0 or len(aaa1) == 0:
return 0
bit = 1 << d
aaa00 = []
aaa01 = []
aaa10 = []
aaa11 = []
for a in aaa0:
if a & bit:
aaa01.append(a)
else:
aaa00.append(a)
for a in aaa1:
if a & bit:
aaa11.append(a)
else:
aaa10.append(a)
if m & bit:
res1 = calc2(aaa01, aaa10, m, d - 1)
res2 = calc2(aaa00, aaa11, m, d - 1)
return res1 + res2
else:
res1 = min(len(aaa01), len(aaa10))
res2 = min(len(aaa00), len(aaa11))
res = res1 + res2
if len(aaa01) > len(aaa10) and len(aaa11) > len(aaa00):
limit = min(len(aaa01) - len(aaa10), len(aaa11) - len(aaa00))
res += min(limit, calc2(aaa01, aaa11, m, d - 1))
elif len(aaa01) < len(aaa10) and len(aaa11) < len(aaa00):
limit = min(len(aaa10) - len(aaa01), len(aaa00) - len(aaa11))
res += min(limit, calc2(aaa00, aaa10, m, d - 1))
return res
n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)
Ex - Constrained Topological Sort
問題
$N$ 頂点 $M$ 辺の有向グラフがある
$(1,2,...,N)$ の順列 $P=(P_1,...,P_N)$ として、頂点 $i$ に値 $P_i$ を割り当てる
$P$ は以下の条件を全て満たさないといけない
割り当て可能か判定し、可能なら $P$ の一例を示せ
$2 \le N \le 2 \times 10^5$
$0 \le M \le 4 \times 10^5$
解法
トポロジカルソートと、区間スケジューリング問題みたいな $R_i$ の昇順に貪欲的に決めていけるやつ（呼び方忘れた）の複合。
問題は以下のように言い換えられる。
グラフの辺に従ってトポロジカルソートし、頂点番号を順に記録する
頂点 $i$ は、ソート結果で $L_i～R_i$ 番目の中にないといけない
矛盾無くソートできたなら、$a$ 番目に頂点 $b$ が記録されたとして $P_b=a$ としたものが答え
トポロジカルソートのアルゴリズムは、ソート結果を記録する空配列 $T$ を用意し、流入辺が無くなった頂点からキューに入れ、キューから取り出された順に $T$ に追加しグラフから削除する、というものである。
キューに複数の頂点が同時にあるとき、どれを取り出すかに自由度がある。
キューに入っている頂点の内、制約が厳しいものを優先的に取り出す
頂点 $i$ が取り出されたとき、$L_i～R_i$ 番目の中にあるかチェックする
まだ $T$ の長さが $L_i-1$ に達していないなら、頂点 $i$ は（流入辺が無くても）キューには入れない
という改変を加えることで、条件を満たすソート結果の一例を作れる。（または破綻する）
キューから取り出す優先順位である「制約が厳しい」とは、
その頂点の $R_i$ だけでなく、そこから辺で繋がる頂点の $R_i$ にも影響される。
①→② この時、①は 4 番目までに置く必要がある
Ri 10 5
よって、まず最初に後ろからトポロジカルソート的なことをし、各頂点の実質的な制約 $R'_i$ を求めておく。
あとは、先ほどの改変を加えてトポロジカルソートし、$N$ 個の頂点を矛盾無く並べられるかチェックすればよい。
Python3
import sys
from heapq import heapify, heappop, heappush
input = sys.stdin.buffer.readline
def encode(a, b):
return (a << 20) | b
def decode(key):
a = key >> 20
b = key ^ (a << 20)
return a, b
def solve(n, m, fwd_links, bwd_links, in_counts, out_counts, lll, rrr):
r_limit = rrr.copy()
q = [i for i, o in enumerate(out_counts) if o == 0]
fixed = len(q)
while q:
v = q.pop()
for u in bwd_links[v]:
out_counts[u] -= 1
r_limit[u] = min(r_limit[u], r_limit[v] - 1)
if out_counts[u] == 0:
q.append(u)
fixed += 1
if fixed < n:
return False
topo = []
stock = [[] for _ in range(n + 2)]
q = []
for v, ic in enumerate(in_counts):
if ic == 0:
item = encode(r_limit[v], v)
if lll[v] == 1:
q.append(item)
else:
stock[lll[v]].append(item)
heapify(q)
while q:
rl, u = decode(heappop(q))
topo.append(u)
if not (lll[u] <= len(topo) <= r_limit[u]):
return False
next_l = len(topo) + 1
for v in fwd_links[u]:
in_counts[v] -= 1
if in_counts[v] == 0:
item = encode(r_limit[v], v)
if lll[v] <= next_l:
heappush(q, item)
else:
stock[lll[v]].append(item)
for item in stock[next_l]:
heappush(q, item)
if len(topo) < n:
return False
ans = [0] * n
for i, t in enumerate(topo):
ans[t] = i + 1
return ans
n, m = map(int, input().split())
fwd_links = [set() for _ in range(n)]
bwd_links = [set() for _ in range(n)]
in_counts = [0] * n
out_counts = [0] * n
for _ in range(m):
s, t = map(int, input().split())
s -= 1
t -= 1
fwd_links[s].add(t)
bwd_links[t].add(s)
out_counts[s] += 1
in_counts[t] += 1
lll = [0] * n
rrr = [0] * n
for i in range(n):
l, r = map(int, input().split())
lll[i] = l
rrr[i] = r
ans = solve(n, m, fwd_links, bwd_links, in_counts, out_counts, lll, rrr)
if ans == False:
print('No')
else:
print('Yes')
print(*ans)