−目次

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）G,Ex問題メモ
- G - Max of Medians
  - 問題
  - 解法
    - 上の桁からの再帰
    - 計算量
- Ex - Constrained Topological Sort
  - 問題
  - 解法

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）G,Ex問題メモ

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）

ジャッジが詰まってUnrated。サーバーがんばれー。

G - Max of Medians

問題

$2N$ 個の非負整数 $A_1,...,A_{2N}$ がある
2個ずつ組み合わせてbitwise-XORし、 $N$ 個の非負整数を作ることを考える
中央値として考えられる最大値を求めよ
- 中央値: 昇順に並べて $\left \lfloor \dfrac{N}{2} \right \rfloor +1$ 番目の要素
$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'
- 次の桁からは、 $S_{d0}$ と $S_{d1}$ から1つずつ選んでペアにすることが必須
- その前提のもとで、 $k$ 以上のペアを最大化
$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'
- $(A_0,B_1)$ または $(A_1,B_0)$ でペアにしないといけない。それぞれで最大化した結果を求めて合計
$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)ペアを最大まで作らず、(0,0)、(1,1)のペアを多くすることで、 $k$ 以上にできる個数が多くなることはあるか？

                (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'のとき
- (0,1)ペアを多くしてXORも'1'にしないと $k$ 未満確定なので、(0,0)(1,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$ は以下の条件を全て満たさないといけない
- $u→v$ に辺があるとき、 $P_u \lt P_v$
- 各頂点に割り当て可能な値の範囲制約があり、頂点 $i$ に対して $L_i \le P_i \le R_i$ を満たす
割り当て可能か判定し、可能なら $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$ は（流入辺が無くても）キューには入れない
- キューに入っている頂点は、 $L_i$ の条件は必ず満たす状態にしておく
- 入れられない頂点は、「 $T$ の長さが $l$ になったら入れる」みたいなのに別途記録して後で入れる

という改変を加えることで、条件を満たすソート結果の一例を作れる。（または破綻する）

キューから取り出す優先順位である「制約が厳しい」とは、その頂点の $R_i$ だけでなく、そこから辺で繋がる頂点の $R_i$ にも影響される。

    ①→②   この時、①は 4 番目までに置く必要がある
Ri  10   5

よって、まず最初に後ろからトポロジカルソート的なことをし、各頂点の実質的な制約 $R'_i$ を求めておく。

$R'_i = \min(R_i, R'_{j1}-1, R'_{j2}-1, ...)$
- ただし $i$ から直接辺で繋がる頂点を $j_1,j_2,...$ とする

あとは、先ほどの改変を加えてトポロジカルソートし、 $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)

            

        
      