AtCoder Talent Quest 〜今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）F,G問題メモ

AtCoder Talent Quest 〜今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）

F - Centroid of a Slice

問題文

$xy$ 平面上に凸 $N$ 角形 $P$ があります。$P$ の頂点には反時計回りに頂点 $1,2,\dots,N$ と番号が付けられており、頂点 $i$ の座標は $(x_i,y_i)$ です。
$Q$ 個の質問に答えてください。
- $j$ 番目の質問では、相異なる $2$ 頂点 $u_j,v_j$ が与えられます。ただし頂点 $u_j,v_j$ は $P$ の周上において隣り合いません。
- 頂点 $u_j$ と頂点 $v_j$ を結ぶ線分で $P$ を二つの多角形に分割し、頂点 $u_j$ から頂点 $v_j$ へ向かう直線の右側にある方を $P'$ としたとき、$P'$ の幾何中心（多角形の内部を一様な密度の薄板とみなしたときの重心）の座標を求めてください。

制約

$4 \leq N \leq 3 \times 10^4$
$1 \leq Q \leq 2 \times 10^5$
$|x_i|,|y_i| \leq 5 \times 10^5$
$(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$ は反時計回りに凸多角形をなす
$P$ のすべての内角は $180$ 度未満
$1 \leq u_j,v_j \leq N$
$u_j \neq v_j$
$P$ の周上で頂点 $u_j$ と頂点 $v_j$ は隣り合わない
入力はすべて整数

解法

幾何中心の求め方に知識が要るものの、調べたら出てくるし、その求め方から累積和が使えることは気付きやすい。

幾何中心

$n$ 多角形の幾何中心 $(C_x,C_y)$ は、以下で求められる。頂点は反時計回りに整列済みで、$x_{n+1}=x_1$ とする。

$\displaystyle C_x = \frac{\sum_{i=1}^{n}(x_i+x_{i+1})(x_iy_{i+1}-x_{i+1}y_i)}{3 \sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)}$
$\displaystyle C_x = \frac{\sum_{i=1}^{n}(y_i+y_{i+1})(x_iy_{i+1}-x_{i+1}y_i)}{3 \sum_{i=1}^{n}(x_iy_{i+1}-x_{i+1}y_i)}$

幾何中心は2点 $(x_i,y_i),(x_{i+1},y_{i+1})$ 間の一定の計算値の総和から求められることが分かる。以下の3つの値の累積和を取っておけば、

$(x_i+x_{i+1})(x_iy_{i+1}-x_{i+1}y_i)$
$(y_i+y_{i+1})(x_iy_{i+1}-x_{i+1}y_i)$
$(x_iy_{i+1}-x_{i+1}y_i)$

クエリ毎に、3つの値それぞれの $[u,v)$ の区間和に、$v→u$ 辺の情報を加えれば $O(1)$ で計算できる。

Python3

def solve(n, q, points, queries):
    x_acc = [0]
    y_acc = [0]
    a_acc = [0]
    for i in range(-n, n - 1):
        x0, y0 = points[i]
        x1, y1 = points[i + 1]
        x_acc.append(x_acc[-1] + (x0 + x1) * (x0 * y1 - x1 * y0))
        y_acc.append(y_acc[-1] + (y0 + y1) * (x0 * y1 - x1 * y0))
        a_acc.append(a_acc[-1] + (x0 * y1 - x1 * y0))

    ans = []
    for u, v in queries:
        if u < v:
            x = x_acc[v - 1] - x_acc[u - 1]
            y = y_acc[v - 1] - y_acc[u - 1]
            a = a_acc[v - 1] - a_acc[u - 1]
        else:
            x = x_acc[v + n - 1] - x_acc[u - 1]
            y = y_acc[v + n - 1] - y_acc[u - 1]
            a = a_acc[v + n - 1] - a_acc[u - 1]
        x0, y0 = points[v - 1]
        x1, y1 = points[u - 1]
        x += (x0 + x1) * (x0 * y1 - x1 * y0)
        y += (y0 + y1) * (x0 * y1 - x1 * y0)
        a += x0 * y1 - x1 * y0
        cx = x / 3 / a
        cy = y / 3 / a
        ans.append((cx, cy))
    return ans


n, q = list(map(int, input().split()))
points = [list(map(int, input().split())) for _ in range(n)]
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, points, queries)
for x, y in ans:
    print(x, y)

G - Cascading Grid

問題文

$H$ 行 $W$ 列のグリッドがあります。
- 各マスには +, -, # のいずれか一文字が書かれています。
- グリッドの情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2 , \dots ,S_H$ によって与えられます。
あなたは、次の操作を $0$ 回以上行うことができます。
- # でないマスを $1$ つ選ぶ。「選んだマスから # のマスを通ることなく、隣接するマスへ左・右・下のいずれかの方向に移動することだけで到達できるマス」をすべて # に変える。ただし、選んだマス自身も到達できるマスに含まれる。
操作後のグリッドにおける、+ のマスの個数から - のマスの個数を引いた値としてあり得る最大値を求めてください。

制約

$1 \le H,W \le 30$
$S_i$ は +, -, # からなる長さ $W$ の文字列
$H, W$ は整数

解法

上には移動できない点がポイント。

+,- マスをまとめて「空きマス」と呼ぶ。

適当な前計算により、以下の問題に変換できる。

DAGがある。
- 横方向に繋がった一連の空きマスを1頂点とみなす。
- 上下に繋がった空きマスは、上→下方向に辺を張る。
頂点毎に、値 $A_1,...,A_n$ が決まっている。
- 各頂点に含まれる '+'を $+1$、'-'を $-1$ として総和を取ったものを $A_i$ とする。
$0$ 個以上の頂点を選んで、そこから到達できる全ての頂点の $A_i$ を $0$ にできる。
残った $A_i$ の総和を最大化せよ

++#--++      ①# ②      DAG
-+---+#        ③  #     ①          ⑤→⑦
##++-++  →  ##  ④        ↘          ↗
--#-++-      ⑤# ⑥      ②→③→④→⑥→⑧
+---#++       ⑦ #⑧

i   1  2  3  4  5  6  7  8    ⑤⑦を選んだ時、残る頂点のAiの総和は 5 で最大
A  +2  0 -2 +3 -2  0 -2  2

これは、貪欲が上手くいかない。例えば「到達できる頂点の $A_i$ の総和が負になるような頂点を選ぶ」ことを繰り返す、とすると、以下を見落とす。

(①:-2)→(③:+2)    全ての頂点について、単独で選んだ時の寄与は非負だが、
(②:-2)↗           実際は①②③を全て選ぶのが最適

最小カット（燃やす埋める）で解く。以下のようにグラフを作る。

超頂点 $s,t$ を用意する。
$A_i$ 正の頂点は、$s→i$ にコスト $A_i$ の辺
$A_i$ 負の頂点は、$i→t$ にコスト $-A_i$ の辺
$i→j$ に辺がある場合、$j→i$ にコスト $\infty$ の辺

上記の辺の張り方は、以下のように意味づけられる。

各頂点に $S,T$ のいずれかを割り当てる。$S$ を「選ばない」、$T$ を「選ぶ」と意味づける。
各頂点 $(i,j)$ 間につき、「$i$ を $S$ に割り当て、$j$ を $T$ に割り当てた場合」の辺コストが、元の問題を上手く表すようにすればよい。

最初、$A_i$ 正の頂点のみ無条件に貰っておく。
$A_i$ 正の頂点を $T$:選ぶ側に割り当てると、貰えるはずだった $A_i$ が貰えなくなるのでコスト $A_i$
$A_i$ 負の頂点を $S$:選ばない側に割り当てると、最終的な総和にコスト $-A_i$
$i→j$ に辺がある場合、$j$ を選ばず(S) $i$ を選ぶ(T) ことは許されないので、コスト $\infty$

これで $s→t$ に最大流を流せば、それが最小カットと一致する。

Python3

from atcoder.maxflow import MFGraph


def solve(h, w, grid):
    vi = 0
    v_indices = []
    v_values = []
    links = []

    for i in range(h):
        row = grid[i]
        l = 0
        row_indices = [-1] * w
        for seg in row.split('#'):
            seg_len = len(seg)
            if seg_len == 0:
                l += 1
                continue
            r = l + seg_len
            row_indices[l:r] = [vi] * seg_len
            val = 0

            for j in range(l, r):
                if row[j] == '-':
                    val -= 1
                else:
                    val += 1
                if i > 0 and v_indices[i - 1][j] != -1:
                    links[v_indices[i - 1][j]].add(vi)
            v_values.append(val)
            links.append(set())
            vi += 1
            l = r + 1

        v_indices.append(row_indices)

    n = vi
    mf = MFGraph(n + 2)
    s = n
    t = s + 1
    ans = 0
    INF = 1 << 60
    for i in range(n):
        v = v_values[i]
        if v > 0:
            mf.add_edge(s, i, v)
            ans += v
        elif v < 0:
            mf.add_edge(i, t, -v)
        for j in links[i]:
            mf.add_edge(j, i, INF)

    cost = mf.flow(s, t)
    ans -= cost
    return ans


h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]
ans = solve(h, w, grid)
print(ans)

なお、横方向に繋がったマスを1頂点に集約せず、元のグリッドの1マスを1頂点として扱っても、同様に最小カットに帰着できる。

目次

AtCoder Talent Quest 〜 今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）F,G問題メモ

F - Centroid of a Slice

問題文

制約

解法

G - Cascading Grid

問題文

制約

解法

AtCoder Talent Quest 〜今から28卒には脱出してもらいます〜予選（AtCoder Beginner Contest 472）F,G問題メモ