キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）G問題メモ

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

G - Security Camera 3

問題

$H \times W$ の、空きマス'.'と壁マス'#'からなるグリッドが与えられる
監視カメラを設置する
- 監視カメラは、空きマスに上下左右の方向を決めて設置できる
- 各監視カメラは、設置された方向の直線上の空きマスを壁マスにぶつかるまで監視できる（設置されたマスを含む）
全ての空きマスを監視するために必要な監視カメラの最小数を答えよ
$1 \le H,W \le 300$

解法

燃やす埋める問題。（に必ずしも帰着しなくてもいいけど、自分が知ってるフォーマットに当てはめるにはそれが近かった）

まず、監視カメラは、上か左が壁かグリッド外である空きマスに、下か右を向けて置くと考えてよい。

.#...←....#..  ここに左向きのカメラを設置するくらいなら
.#.......←#..  こう設置した方が絶対にいいし、
.#→.......#..  それはこう設置するのと全く変わらない。上下も一緒

すると各マスにつき「下方向に監視されるならこの監視カメラ」「右方向ならこのカメラ」というのが一意に決まる。
このようなカメラを、マス $c$ に対し、それぞれ $D(c),R(c)$ とする。

カメラ候補を頂点として、「使う」「使わない」の燃やす埋める問題として考える。

使う場合はコスト1
使わない場合はコスト0

1#2
345

 ,--0-- →1 --1--,    S側に属する: 使う
 |               |    T側に属する: 使わない
 |--0-- →2 --1--|
 |               |
S---0-- →3 --1---T
 |               |
 |--0-- ↓1 --1--|
 |               |
 |--0-- ↓2 --1--|
 |               |
 `--0-- ↓4 --1--'

で、監視されないマスがあってはいけないので、各マス $c$ につき、「 $D(c)$ と $R(c)$ がともに「使わない」であってはいけない（コスト無限大）」という制約を課したい。

一般的な燃やす埋めるでは、2つの頂点が違う側に属した時のコストは設定できるが、同じ側に属したときは設定できない。

だが今回の場合は下向きカメラと右向きカメラの間にしか辺が張られないことが明らかなので（下向き同士、右向き同士に制約は課されないので）、どちらか（例えば下向き）だけ、「使う」「使わない」の意味合いを反転させてしまえばよい。

 ,--0-- →1 --1--,    ┐ 
 |               |    │S側に属する: 使う
 |--0-- →2 --1--|    │T側に属する: 使わない
 |               |    │
S---0-- →3 --1---T   ┘
 |               |
 |--1-- ↓1 --0--|    ┐
 |               |    │S側に属する: 使わない
 |--1-- ↓2 --0--|    │T側に属する: 使う
 |               |    │
 `--1-- ↓4 --0--'    ┘

こうした上で、例えば「→1と↓2がともに使わないであってはいけない」なら、 ↓2から→1にコスト無限大の辺を張ることで制約が表現できる。

$S→T$ に最大流を流せば答え。

Python3

        
          
          
              
              from collections import deque
from typing import Tuple, List
 
 
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
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
 
cells = set()
cameras = set()
camera_ud = [-1] * (h * w)
camera_lr = [-1] * (h * w)
 
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            continue
        key = i * w + j
        cells.add(key)
        if i == 0 or field[i - 1][j] == '#':
            camera_key = key << 1
            camera_ud[key] = camera_key
            cameras.add(camera_key)
        else:
            camera_ud[key] = camera_ud[key - w]
        if j == 0 or field[i][j - 1] == '#':
            camera_key = (key << 1) + 1
            camera_lr[key] = camera_key
            cameras.add(camera_key)
        else:
            camera_lr[key] = camera_lr[key - 1]
 
n = len(cameras)
s = n
t = s + 1
mf = Dinic(n + 2)
 
camera_idx = {c: i for i, c in enumerate(cameras)}
INF = 1 << 60
 
for key in cameras:
    u = camera_idx[key]
    if key & 1:
        mf.add_link(u, t, 1)
    else:
        mf.add_link(s, u, 1)
 
for key in cells:
    u = camera_idx[camera_ud[key]]
    v = camera_idx[camera_lr[key]]
    mf.add_link(u, v, INF)
 
ans = mf.max_flow(s, t)
 
print(ans)

            

        
      