AtCoder Beginner Contest 211 D,E,F問題メモ

AtCoder Beginner Contest 211

夏の競プロは蚊が天敵

D - Number of Shortest paths

問題

$N$ 頂点 $M$ 辺のグラフが与えられる
- 単純であることは保証されるが連結であるとは限らない
辺のコストは全て1として、頂点 $1$ から $N$ への最短経路は何通りあるか求めよ
$2 \le N \le 2 \times 10^5$
$0 \le M \le 2 \times 10^5$

解法

DijkstraやBFSなどで最短距離を求めるとき、各頂点への「最短距離」の配列を管理するが、最短経路のパターン数を求める場合は、「パターン数」も一緒に管理する。

dist[v]: 頂点 $v$ への（暫定）最短距離
pat[v]: 頂点 $v$ への距離が $dist[v]$ であるような経路のパターン数

queueから取り出した頂点 $v$（最短距離が確定した頂点）から、隣接する頂点 $u$ へ伸ばすときを考える。

$v$ を経由して $u$ に至る距離を $d=dist[v]+1$ として、

既に $u$ への最短距離で、$d$ より短いものが見つかっている場合（$dist[u] \lt d$）
- 何もしない
既に $u$ への最短距離で、$d$ と同じものが見つかっている場合（$dist[u] = d$）
- $pat[u] += pat[v]$
まだ $u$ が未探索、または $d$ より長いものしか見つかっていない場合（$dist[u] \gt d$）
- $pat[u] = pat[v]$
- queueに $u$ を追加

とすれば、通常の最短経路探索と比較して無駄に探索範囲を広げることなく、パターン数も求められる。

今回は辺のコストが全て1（正）なので、queueから $u$ が取り出される前には $dist[u]$ も $pat[u]$ も全て網羅されていることが保証される。

ただし、辺のコストに $0$ があったりすると、 $u$ にコスト0の辺を使って到達できる経路がまだある状態（$pat[u]$ が確定していない状態）で $u$ がqueueから取り出されてしまうことがあり得る。

その場合は無向辺ならパターン数は無限大になるので問題の体を為さなくなるし、有向辺ならコスト0の辺だけで最初にトポロジカルソートなりして、距離が同率の場合はソート順にqueueから取り出せばいいのかな？

Python3

from collections import deque

n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

q = deque([0])
MOD = 10 ** 9 + 7
INF = 1 << 60
distances = [INF] * n
distances[0] = 0
patterns = [0] * n
patterns[0] = 1

while q:
    v = q.popleft()
    nd = distances[v] + 1
    for u in links[v]:
        if distances[u] < nd:
            continue
        elif distances[u] == nd:
            patterns[u] = (patterns[u] + patterns[v]) % MOD
        else:
            distances[u] = nd
            patterns[u] = patterns[v]
            q.append(u)

print(patterns[-1])

E - Red Polyomino

問題

$N \times N$ のマス目が与えられ、マス $(i,j)$ は $S_{i,j}$ が'#'なら黒く、'.'なら白く塗られている
白く塗られたマスを $K$ 個選んで赤く塗る
この時、赤く塗られた $K$ マスが全てタテヨコにひとつながりになっているパターン数を求めよ
$1 \le N \le 8$
$1 \le K \le 8$

解法

$N,K$ が小さいのである程度全探索的なことを考える。

まぁ、全探索とはいえ $N^2$ マスから $K$ マス選ぶ方法を全探索して連結が調べる、なんてのはさすがに無理。

サンプル3が優しくて、パターン数が最大である $N=8,K=8,$ 全マス白マスのケースが64678しかないことを教えてくれている。

なので、「赤く塗ることを仮定するマスは常に連結」となるように探索範囲を広げていけば、そこまで状態数は大きくならなさそう。マスの数も64個で、丁度64bit整数に収まるので、 bitフラグで赤く塗ることを仮定した頂点を管理することにする。

N=4
  0 1 2 3      4,8,9を赤く塗った状態を表す整数
  4 5 6 7  →    5432109876543210
  8 91011      0b0000001100010000  =  784
 12131415

探索済みの状態の集合 checked をsetで管理しておく。

まず、白マスを1マスだけ塗った状態を全てqueueに突っ込む。

queueから取り出した状態につき、

その状態で赤く塗られているマスを復元する
上下左右に隣接している白マスから新しく1マスを赤く塗った状態に遷移する
- 遷移後の状態が既に checked ならスキップ
- そうでなく、$K$ マス塗られた状態なら、答えに+1カウント、checked に追加
- そうでないなら、queueとcheckedに追加

としていけば、求められる。

Python3

n = int(input())
k = int(input())
field = [list(map('.#'.index, input())) for _ in range(n)]

q = []
for i in range(n):
    for j in range(n):
        if field[i][j] == 0:
            q.append(1 << (i * n + j))

if k == 1:
    print(len(q))
    exit()

ans = 0
counted = set(q)
n1 = n - 1
while q:
    ijs = q.pop()
    t = ijs
    adjacent = set()
    nij = 0
    pop_count = 0
    while t:
        if t & 1:
            i, j = divmod(nij, n)
            if 0 < i and field[i - 1][j] == 0:
                adjacent.add((i - 1) * n + j)
            if i < n1 and field[i + 1][j] == 0:
                adjacent.add((i + 1) * n + j)
            if 0 < j and field[i][j - 1] == 0:
                adjacent.add(i * n + j - 1)
            if j < n1 and field[i][j + 1] == 0:
                adjacent.add(i * n + j + 1)
            pop_count += 1
        t >>= 1
        nij += 1

    for nij in adjacent:
        b = 1 << nij
        if ijs & b:
            continue
        if ijs | b in counted:
            continue
        counted.add(ijs | b)
        if pop_count == k - 1:
            ans += 1
        else:
            q.append(ijs | b)

print(ans)

F - Rectilinear Polygons

問題

二次元平面上に $N$ 個の多角形がある
- $i$ 個目の多角形は $M_i$ 角形で、各頂点の座標も与えられる
- 多角形は単純（連続しない2辺が公差や接触していない）
- 全ての多角形の辺は、$x$ 軸または $y$ 軸に平行
- 頂点の座標は順に与えられるが、時計回りか反時計回りかは不明
以下の $Q$ 個のクエリに答えよ
- 座標 $(X_i+0.5, Y_i+0.5)$ には、いくつの多角形が重なっているか？
$1 \le N \le 10^5$
全多角形の頂点数の合計 $\le 4 \times 10^5$
$0 \le $ 多角形やクエリの $x,y$ 座標の値 $\le 10^5$

解法

クエリ先読みでイベントソート。

「多角形のうち垂直な辺」「クエリ」を全てまとめて $x$ 座標でソートする。

1つの多角形の1つの垂直な線が $Y_1～Y_2$ まで引かれていたとして、ここを境として左と右では、$Y_1～Y_2$ に対するクエリの答えが+1または-1される。

$x$ 座標の小さい方からFenwick Treeなどで管理してやれば、

多角形: 区間 $Y_1～Y_2$ に1または-1を加算する
クエリ: 現時点の $Y$ の値を求める

という区間加算の問題に変わり、各操作を $O(\log(座標最大値))$ で処理できる。

さて問題は、各多角形の垂直な線が+1（外から内）なのか-1（内から外）なのかをどうやって判定するか。
これは、座標の与えられ方が時計回りか反時計回りかに依存する。

時計回りなら、与えられた順で↑向きの辺で+1され、↓向きの辺で-1される
反時計回りなら、↓向きの辺で+1され、↑向きの辺で-1される

では、時計回りか反時計回りかをどう判定するか。
最初の3点が右に折れ曲がっていたからといって、時計回りとは限らない。

④←←③
↓    ↑    ⓪→①→②だけを見ると右に折れ曲がっているが、
↓①→②    座標の与えられ方は反時計回り
↓↑
↓⓪←⑦
↓    ↑
⑤→→⑥

多角形の座標を全て $(x,y)$ でソートすれば、一番左下にある垂直な辺を取り出せる。（図では④→⑤）

この辺は一番左下なので、（当然だが）もっと左を回り込むような辺は無い。
なので、必ず外→内の辺である。

これが上向きなら時計回り、下向きなら反時計回りだといえる。

Python3

import sys
from operator import add

input = sys.stdin.buffer.readline
n = int(input())
events = []
for _ in range(n):
    m = int(input())
    xys = map(int, input().split())
    xys = list(zip(xys, xys))
    xys_with_index = [(x, y, i) for i, (x, y) in enumerate(xys)]
    xys_with_index.sort()
    x1, y1, i1 = xys_with_index[0]
    x2, y2, i2 = xys_with_index[1]

    if i1 == 0 and i2 == m - 1:
        ccw = False
    elif i1 == m - 1 and i2 == 0:
        ccw = True
    elif i1 < i2:
        ccw = True
    else:
        ccw = False

    for (x1, y1), (x2, y2) in zip(xys[0::2], xys[1::2]):
        assert x1 == x2
        if y1 < y2:
            if ccw:
                events.append((x1, 0, y1, y2))
            else:
                events.append((x1, 1, y1, y2))
        else:
            if ccw:
                events.append((x1, 1, y2, y1))
            else:
                events.append((x1, 0, y2, y1))

q = int(input())
for i in range(q):
    x, y = map(int, input().split())
    events.append((x, i + 100, y, 0))

events.sort()


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total


fwt = FenwickTreeInjectable(10 ** 5 + 5, int, add)
ans = [0] * q
for x, op, y1, y2 in events:
    if op == 0:
        fwt.add(y1, 1)
        fwt.add(y2, -1)
    elif op == 1:
        fwt.add(y1, -1)
        fwt.add(y2, 1)
    else:
        i = op - 100
        tmp = fwt.sum(y1)
        ans[i] = tmp

print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 211 D,E,F問題メモ

D - Number of Shortest paths

問題

解法

E - Red Polyomino

問題

解法

F - Rectilinear Polygons

問題

解法