LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）D,F,G問題メモ

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

今回のセット、8問体制になって初めての全完を狙えたかも知れないけど、やっぱスピードが足りてなかった。

D - Left Right Operation

問題

長さ $N$ の数列 $A_1,...,A_N$
以下の操作を順に1回ずつ行う
- 整数 $x$ を好きに選び、左端から $x$ 個の要素を全て $L$ に置換する（0個でもよい）
- 整数 $y$ を好きに選び、右端から $y$ 個の要素を全て $R$ に置換する（0個でもよい）
操作後の $A$ の総和としてあり得る最小値を求めよ
$1 \le N \le 2 \times 10^5$
$-10^9 \le L,R,A_i \le 10^9$

解法

DP。

左から順に考えるにあたり、場合分けすべき「状態」って3つしかなくて、

①左端からの置換が続いている
②左端からの置換が途切れて、右端からの置換が始まっていない
③右端からの置換が始まっている

①はずっと $L$ のみを足し続けた状態、②は素の $A_i$ を1回でも採用しつつ、 $R$ はまだ採用していない状態、③は $R$ を1回でも採用した状態となる。

$DP[i][k=①/②/③]=i$ 番目の時点で、状態が $k$ であるものの、 $i$ 個の総和の最小値

かならず①→②→③の順にしか状態は遷移しない。（それぞれは、長さが0の場合もある）
なので、 $i-1→i$ の遷移は以下のようになる。

$DP[i][①] = DP[i-1][①]+L$
$DP[i][②] = min(DP[i-1][①], DP[i-1][②]))+A$
$DP[i][③] = min(DP[i-1][①], DP[i-1][②], DP[i-1][③]))+R$

$min(DP[N][①～③])$ が答え。

Python3

F - Tournament

問題

$2^N$ 人の人がトーナメント勝負をする
トーナメント表において左から $i$ 番目の人は、ちょうど $j$ 回勝った時に $C_{i,j}$ の得点を得る
- 1回も勝てなかった人は $0$ 点
1位が決まるまでの全ての対戦の勝敗を自由に決められるとき、各人が得た得点の総和としてあり得る最大値を求めよ
$1 \le N \le 16$

解法

差分更新。

入力に合わせて、トーナメント表を縦にして考える。（上下が人の並び、左→右が対戦の運び）

トーナメント表で、左から $j$ 列目までの対戦が終わった時点における最大値を求めていく。
1列目は単純に、対戦ペア毎に $C_{i,1}$ の高い方を選べばよい。

人    C
 1    [3]  9   5
 2     1   2   8
 3     4   6   9
 4    [5]  3   7
 5    [9]  4   4
 6     3   6   3
 7     2   2   8
 8    [8]  6   1

2列目以降の試合では、追加で獲得できる得点がより大きい人を選ぶ。
選ぶ区間は、2試合目なら4人、3試合目なら8人、、、のブロック毎に1人ずつ選ぶことになる。

1,2回だけ勝っても $C_{i,j}$ は小さい（そのため2試合目までの評価では敗退する）けど、3回勝てば大きい得点が見込めるので実は勝ち進んだ方がよい、みたいな人もあり得る。
最大値を選ぶ対象は敗退した人も含めなければいけない。

既に $x$ 回目の対戦で敗退している人にとっての、「 $j$ 回目の対戦で追加で獲得できる得点」とは、「『自身が $x-1$ 回の勝利で得た得点』と『その人が $j$ 回目まで勝ち進んでいた場合に、 $x$ 回目以降に対戦することになる各（暫定）勝利者が得た得点』分を $C_{i,j}$ から減じた得点」ということになる。

文章で書くと複雑そうだが、 $j$ 試合目の各ブロックの最大値（追加で獲得できる得点）が決まる毎に、そのブロックの $j+1$ 試合目以降の $C_{i,j}$ を最大値分減らしていけば、常にそのような状態を保てる。

1試合目の最大値を2人毎のブロックで計算
 人    C
 1    [3]  9   5
 2     1   2   8
 3     4   6   9
 4    [5]  3   7
 5    [9]  4   4
 6     3   6   3
 7     2   2   8
 8    [8]  6   1

1試合目の分を2試合目以降から減じる
人    C
 1    [3]  6   2   ┐2試合目以降 3ずつへらす
 2     1  -1   5   ┘
 3     4   1   4   ┐2試合目以降 5ずつへらす
 4    [5] -2   2   ┘
 5    [9] -5  -5   ┐2試合目以降 9ずつへらす
 6     3  -3  -6   ┘
 7     2  -6   0   ┐2試合目以降 8ずつへらす
 8    [8] -2  -7   ┘

2試合目の最大値を4人毎のブロックで計算
人    C
 1    [3] [6]  2
 2     1  -1   5
 3     4   1   4
 4    [5] -2   2
 5    [9] -5  -5
 6     3  -3  -6
 7     2  -6   0
 8    [8][-2] -7

2試合目の分を3試合目以降から減じる
人    C
 1    [3] [6] -4   ┐ 6ずつへらす
 2     1  -1  -1   ┤
 3     4   1  -2   ┤
 4    [5] -2  -4   ┘
 5    [9] -5  -3   ┐-2ずつへらす
 6     3  -3  -4   ┤
 7     2  -6   2   ┤
 8    [8][-2] -5   ┘

3試合目の最大値を8人毎のブロックで計算
人    C
 1    [3] [6] -4
 2     1  -1  -1
 3     4   1  -2
 4    [5] -2  -4
 5    [9] -5  -3
 6     3  -3  -4
 7     2  -6  [2]
 8    [8][-2] -5

答えは、[ ] のついた数字の合計となる。

計算量は $O(N^22^N)$ 。
毎回全ての $C_{i,j}$ を直接は更新せず、「人 $i$ は初期値から $D_i$ だけ減じた値で最大値を評価する」みたいな $D_i$ を管理しておくような実装にすれば $O(N2^N)$ となる。

答えには関係ないが、実際に各人がどこまで勝ち進んだかは、上の表を今度は右から辿って、「 $j$ 列目に人 $i$ に[ ]がついていたら、 $j-1$ 列目以前の、その対戦において $i$ が含まれるブロックに[ ]が（もしあれば）消す」という風にしていくとわかる。

 人    C
 1     3  [9]  5
 2     1   2   8
 3     4   6   9
 4    [5]  3   7
 5    [9]  4   4
 6     3   6   3
 7     2   2  [8]
 8     8   6   1

Python3

G - Erasing Prime Pairs

問題

黒板に $N$ 種類の数字が書かれている
- $i$ 種類目の数字 $A_i$ は $B_i$ 個書かれている
和が素数となるような2つの数字があればそれを両方消す、ということをできる限り繰り返す
最大何ペア消せるか、求めよ
$1 \le N \le 100$
$1 \le A_i \le 10^7$
$1 \le B_i \le 10^9$

解法

最大流。

各数字（の種類）を1頂点で表し、それを2重にする。
$S→i_L$ と $i_R→T$ に容量 $B_i$ の辺を張り、さらに足すと素数になるペアについては左右間に容量INFの辺を張る。

A1=1, B1=4
A2=2, B2=3
A3=5, B3=2
          iL    iR
   ┌(4)─ 1 ─ 1 ─(4)┐
   │        ×        │
 S ┼(3)─ 2    2 ─(3)┼ T
   │        ×        │
   └(2)─ 5    5 ─(2)┘

これで最大流を流すと、最大ペアの2倍の流量が求まる。

なぜならば、基本的に同じ数字をペアにできるのは $1$ が特例であり、その他の数字は同じ同士では消せない。
異なる数字同士では、例えば2→5に流量2流れたなら、5→2にも2流れる。（最大流を達成する方法が複数あったら、流し終えた実際のグラフ上ではそうなっていないかも知れないが、少なくともこのように鏡映しになっているような達成状態も必ず存在する）
よって、異なる数字同士に関しては最大ペアの2倍量が流れる。

$1$ が含まれる場合、余った1の個数が最大流に加わっている。
この時、最大流なので、異なる数字同士のペア数が同じなら、1が最大限余るような結果が求まっている。
ここから作れる1同士のペアは、余った個数の半分（切り捨て）となる。

異なる数字同士、1同士、いずれも2倍の量が求まるので、最終的な答えも最大流を半分にすることによって求められる。

Python3

        
          
          
              
              from collections import deque
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.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
 
    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
 
    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                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
        stack = [s]
 
        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                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
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])
 
        for link in fwd_links:
            link[0] -= f
 
        for link in bwd_links:
            link[0] += 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したあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges
 
 
def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf
 
 
n = int(input())
s = 2 * n
t = s + 1
max_flow = Dinic(2 * n + 2)
 
spf = get_spf(20_000_000)
INF = 1 << 60
 
numbers = [tuple(map(int, input().split())) for _ in range(n)]
for i in range(n):
    a1, b1 = numbers[i]
    max_flow.add_link(s, i, b1)
    max_flow.add_link(n + i, t, b1)
 
    if a1 == 1:
        max_flow.add_link(i, n + i, INF)
 
    for j in range(i + 1, n):
        a2, b2 = numbers[j]
        p = a1 + a2
        if spf[p] == p:
            max_flow.add_link(i, n + j, INF)
            max_flow.add_link(j, n + i, INF)
 
ans = max_flow.max_flow(s, t)
 
print(ans // 2)

            

        
      