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}$ は小さいけど、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

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

答えには関係ないが、実際に各人がどこまで勝ち進んだかは、上の表を今度は右から辿って、「 $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の辺を張る。

入力例1

   ┌(4)─ 2    2 ─(4)┐
   │        ×        │
 S ┼(3)─ 3    3 ─(3)┼ T
   │                  │
   └(2)─ 6    6 ─(2)┘

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

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

$1$ が含まれる場合も、他の数字とのペアで余った1は1同士とペアになれるため、流量の半分（切り捨て）によって求められる。

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)

            

        
      