AtCoder Beginner Contest 241（Sponsored by Panasonic）D,G問題メモ

AtCoder Beginner Contest 241（Sponsored by Panasonic）

D - Sequence Query

問題

空の数列 $A$ がある
$Q$ 回、以下のクエリに答えよ
クエリの種類
- 1 x: $A$ に $x$ を追加する
- 2 x k: $A$ の $x$ 以下の要素のうち、大きい方から $k$ 番目の値を出力する
- 3 x k: $A$ の $x$ 以上の要素のうち、小さい方から $k$ 番目の値を出力する
ただしクエリ2,3の時に該当する値が $k$ 個無かったら -1 と出力する
$1 \le Q \le 2 \times 10^5$
$1 \le k \le 5$

解法

$k$ が小さいので、例えばクエリ2なら「 $x$ 以下で最大の値 $y$ と個数を得る」「 $y-1$ 以下で最大の値 $z$ と個数を得る」……で $k$ 個に達したらそれが答えとなる。

C++なら、multisetを使えばほぼそのままの関数が用意されているんだけど、毎度のことながらPythonでは平衡二分探索木がないので、自分で代わりのものを実装する必要がある。

どうやるのが速いんだろうね。Python3でACが早い方から見ていくに、

みたいな感じだった。
まぁ、この辺を把握しておくとよさそう。

また、Binary Indexed Tree や Binary Trie も、素の状態ではなく、multisetに相当する関数を用意した状態で準備しておくと混乱せず使える。

個数が $k$ に満たないとき用に、番兵として -1 と INF を5個ずつ入れておくと楽。

Python3

G - Round Robin

問題

$N$ 人で総当たり戦をする
- 勝負は必ず決着し、引き分けはない
既に $M$ 試合が終了しており、結果が与えられる
残り試合も行った上で、単独優勝する可能性のある人を全て列挙せよ
$2 \le N \le 50$

解法

それぞれの人について独立に判定する。

人 $i$ が単独優勝できるか？
可能性の話なので、残り試合は全て勝つものとして問題ない。

よって、「終了した試合での勝ち数」＋「残り試合数」が $i$ の最終的な勝利数 $V_i$ で、他の人はこれ以上にさせないことができるか？という問題となる。

基本的には、 $V_i$ が、他の人の現時点での最大勝利数より大きければよさそうに見える（多く勝ってる人には今後負け続けてもらう）が、たとえば以下のような場合（AND条件）は、 $i$ は単独優勝し得ない。

$i$ の最終的な勝利数 $V_i=5$
既に4勝している人が $i$ 以外に2人いて、その2人はまだ直接対戦してない

終了した試合での勝ち数が多い人は残り試合でなるべく負けてほしいが、そういう人同士の対戦ではどうしてもどちらかが勝ってしまう。
2人だけならいいが、複数人が絡んできて、またその残り試合も誰と誰は終わった、残っている、がバラバラなのでどこから決めれば最適か、一概に決めづらい。

このような問題は、最大流に言い換えられる。

$V_i$ が決まった段階で、それ以外の人につき、「あと何勝まではできる」というのが決まる。

この時点で、 $i$ 以外に $V_i$ 以上勝っている人がいれば、 $i$ は単独優勝不可能。

それ以外の場合、「始点 → 人を表す $N$ 頂点 → 残り試合を表す頂点 → 終点」というグラフを作る。（ $i$ が勝利すると決めた残り試合は除く）

(始点 → 人) には、各人に許される残り勝利数＝容量の辺
(人 → 試合) には、その人がその試合に出場する場合、容量1の辺
- この辺に流れる場合、その人がその試合に勝ったことを表現する
(試合 → 終点) には、容量1の辺
- 2人が同時に勝つことはないようにする

を張り、残り試合数分だけの容量を流せれば、 $i$ 以外の全員を $V_i$ 未満の勝利数に抑えられる試合結果が存在することになる。

グラフの辺の容量は人によって変化するものの、頂点間の辺の張り方・構造は不変のため、毎回グラフを作るより、リセット・容量の変更を可能にしておくと、若干速い。

Python3

        
          
          
              
              from collections import deque
from itertools import accumulate
from typing import List, Tuple
 
 
class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """
 
    def __init__(self, n: int):
        self.n = n
        self.edges: List[List[int]] = []  # [from, to, capacity]
        self.links: List[List[int]] = [[] for _ in range(n)]
        # if exists an edge (u -> v) with capacity...
        #   links[u] = [ i, j, ...]
        #         ,------'
        #   edges[i] = [u, v, capacity]
        # Reverse edge is i^1
 
    def add_link(self, from_: int, to: int, capacity: int) -> None:
        li = len(self.edges)
        self.links[from_].append(li)
        self.links[to].append(li + 1)
        self.edges.append([from_, to, capacity])
        self.edges.append([to, from_, 0])
 
    def reset_link(self):
        """ 一回流したフローを初期化する """
        edges = self.edges
        for li in range(0, len(edges), 2):
            edges[li][2] += edges[li ^ 1][2]
            edges[li ^ 1][2] = 0
 
    def change_link(self, from_: int, to: int, new_capacity: int):
        """ リンクコストを変更する。流す前またはリセット後に呼ぶこと """
        for li in self.links[from_]:
            if li & 1 == 1:
                continue
            if self.edges[li][1] == to:
                self.edges[li][2] = new_capacity
                break
        else:
            assert RuntimeWarning(f'No edge {from_} -> {to}')
 
    def bfs(self, s: int) -> List[int]:
        links = self.links
        edges = self.edges
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for li in links[v]:
                _, to, cap = edges[li]
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth
 
    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        edges = self.edges
        stack = [s]
 
        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                li = links[v][i]
                _, to, cap = edges[li]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0
 
        f = 1 << 60
        used_links = []
        for v in stack[:-1]:
            li = links[v][progress[v]]
            _, to, cap = edges[li]
            f = min(f, cap)
            used_links.append(li)
 
        for li in used_links:
            edges[li][2] -= f
            edges[li ^ 1][2] += f
 
        return f
 
    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow
 
    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        links = self.links
        edges = self.edges
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for li in links[v]:
                _, u, cap = edges[li]
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        cut_edges = []
        for u, v, cap in edges[::2]:
            if reachable[u] == 1 and reachable[v] == 0:
                cut_edges.append((u, v))
        return cut_edges
 
 
n, m = map(int, input().split())
win_count = [0] * n
rem_match = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    w, l = map(int, input().split())
    w -= 1
    l -= 1
    win_count[w] += 1
    rem_match[w].remove(l)
    rem_match[l].remove(w)
 
all_rem_match = []
idx_rem_match = {}
 
for i in range(n):
    for j in rem_match[i]:
        if i < j:
            k = len(all_rem_match)
            all_rem_match.append((i, j))
            idx_rem_match[i, j] = idx_rem_match[j, i] = k
 
arm = len(all_rem_match)  # remaining match count
 
mf = Dinic(n + arm + 2)
s = n + arm
t = s + 1
 
for i in range(n):
    mf.add_link(s, i, 0)
 
for k, (i, j) in enumerate(all_rem_match):
    mf.add_link(i, k + n, 1)
    mf.add_link(j, k + n, 1)
    mf.add_link(k + n, t, 1)
 
fwd_max = [0]
fwd_max.extend(accumulate(win_count, func=max))
bwd_max = [0]
bwd_max.extend(accumulate(reversed(win_count), func=max))
bwd_max.reverse()
 
ans = []
for i in range(n):
    rem = rem_match[i]
    max_win = win_count[i] + len(rem)
    if max_win <= max(fwd_max[i], bwd_max[i + 1]):
        continue
    for j in range(n):
        if i == j:
            mf.change_link(s, j, 0)
        else:
            mf.change_link(s, j, max_win - 1 - win_count[j])
    for j in rem:
        k = idx_rem_match[i, j]
        mf.change_link(j, k + n, 0)
 
    if mf.max_flow(s, t) >= arm - len(rem):
        ans.append(i + 1)
 
    mf.reset_link()
    for j in rem:
        k = idx_rem_match[i, j]
        mf.change_link(j, k + n, 1)
 
print(*ans)

            

        
      