AtCoder Beginner Contest 259 E,G,Ex問題メモ

E - LCM on Whiteboard

問題

ホワイトボードに $N$ 個の整数 $a_1,a_2,...,a_N$ が書かれている
整数はとても巨大なことがあり、素因数分解した形で与えられる
- $m_i$ 個の素数を用いて $a_i=p_{i,1}^{e_{i,1}}p_{i,2}^{e_{i,2}}...p_{i,m_i}^{e_{i,m_i}}$
$a_i$ のうち1つを選んで $1$ に書き換えたときに、$N$ 個の総最小公倍数として取り得る値の個数を求めよ
$1 \le N \le 2 \times 10^5$
$1 \le m_iの総和 \le 2 \times 10^5$

解法

LCMは、各素因数 $p$ につき、$N$ 個の数の中で指数 $e$ が最大のものを持ってきてかけ合わせるとできる。

p\ai  49    42    20    21        2940 = LCM
2      0     1     2     0    →    2
3      0     1     0     1    →    1
5      0     0     1     0    →    1
7      2     1     0     1    →    2

「1つ選んで1に書き換える」操作をする前のLCMを「元のLCM」として、操作したときに元のLCMから変化するのは「$a_i$ の素因数の中に、その素数に対する指数が $a_1,...,a_N$ の中で唯一の最大であるようなものが含まれている」場合である。

p\ai  49    42    20    21
2      0     1    [2]    0
3      0     1     0     1      ←唯一の最大でない
5      0     0    [1]    0
7     [2]    1     0     1

上記、$p=2$ は、20を消せば最大が変化するので、結果のLCMも独自のものに変化する。
一方、$p=3$ は、42を消しても21が残ればLCMの指数は1であり続けるし、逆も同じ。LCMは元から変化しない。

このように、指数が唯一の最大である素数を素因数に持つ $a_i$ を「変化数」と呼ぶことにする。
上の例では49と20がそれに当たる。

素因数分解は一意なので、異なる変化数を消したときの結果が同じになってしまうことはない。
上記で20を消したときのLCMと49を消したときのLCMは、必ず異なる。

よって、変化数の個数を数えればよい。
20における2と5のように、同じ変化数の中に指数最大の素数が複数含まれていても、カウントは1回。

あとは変化数でない $a_i$ が存在すれば、LCMが元から変わらない場合を+1すると答えとなる。
これは、変化数の個数が $N$ 未満かどうかで判定できる。

Python3

from collections import defaultdict

n = int(input())

count = defaultdict(lambda: [0, set()])  # count[prime] = [最大個数, 最大個数を持つindex]

for i in range(n):
    m = int(input())
    for _ in range(m):
        p, e = map(int, input().split())
        if count[p][0] < e:
            count[p][0] = e
            count[p][1] = {i}
        elif count[p][0] == e:
            count[p][1].add(i)

only_one = set()

for cnt, idx in count.values():
    if len(idx) == 1:
        i = idx.pop()
        only_one.add(i)

ans = len(only_one)
if ans < n:
    ans += 1

print(ans)

G - Grid Card Game

問題

$H \times W$ のグリッド状にカードが配置されている
$i$ 行 $j$ 列目にあるカードには整数 $A_{i,j}$ が書かれている
いくつかの行といくつかの列を選ぶ（0個でもよいし、全てでもよい）
ただし、$A_{i,j}$ が負であるとき、$i$ 行目と $j$ 列目をともに選ぶことはできない
選んだ行と列に置かれたカードの $A_{i,j}$ の総和の最大値を求めよ
$1 \le H,W \le 100$
$-10^9 \le A_{i,j} \le 10^9$

解法

燃やす埋める。言われてみれば。

選ぶ行・列を決め打ったとき、結果は「選んだ行の $A_{i,j}$ の総和 + 選んだ列の $A_{i,j}$ の総和 - 選んだ行と列がクロスする部分の $A_{i,j}$ の総和」となる。

クロス部分を引くのは、行と列で総和に2回足されてしまっているのの調整のためだが、今回はこの部分の $A_{i,j}$ に、負値が1つでもあってはいけないという制約がある。

まず行・列ごとに総和を取って、それが0以下になる行・列については、選ぶ必要は無い。

残った行・列に対して選ぶ・選ばないを割り振っていくのだが、

$i$ 行目を選ぶと $i$ 行目の総和の利益
$j$ 列目を選ぶと $j$ 列目の総和の利益
- 利益は前もって獲得したものとして、「選ばないと○○のコスト」と言い換えられる
$A_{i,j} \lt 0$ のとき、$i$ 行と $j$ 列をともに選ぶと $\infty$ のコスト
$A_{i,j} \ge 0$ のとき、$i$ 行と $j$ 列をともに選ぶと $A_{i,j}$ のコスト

とまとめられ、燃やす埋める問題に帰着でき、最小カットで解ける。

通常の燃やす埋めるでは、2項間の関係について「$a_i$ を埋め、$a_j$ を燃やせば○○のコスト」のように、 2つで異なる選択肢をとったときのコストしか表現できない。
この問題では「ともに選ぶ」ことで発生するコストがあるが、これは行と列で左右の意味合いを反転させることで対応できる。

   ,-- 行① --,       最小カット問題の文脈で、
   |          |       行の頂点は、Ｓ側に属することを「選ぶ」
   |-- 行② --|                   Ｔ側に属することを「選ばない」
   |          |       列の頂点は、Ｓ側に属することを「選ばない」
Ｓ-|-- 行③ --|-Ｔ                Ｔ側に属することを「選ぶ」 と意味づける
   |          |
   |-- 列① --|       Ｓ→行 に各行の総和のコストを設定
   |          |       列→Ｔ に各列の総和のコストを設定
   `-- 列② --'       行→列 にクロスする箇所のコストを設定

頂点数 $O(H+W)$、辺数 $O(HW)$ の最大流問題となり、制約的に十分高速に解ける。

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


h, w = map(int, input().split())
aaa = [list(map(int, input().split())) for _ in range(h)]

rows_sum = list(map(sum, aaa))
cols_sum = list(map(sum, zip(*aaa)))
available_rows = [i for i, s in enumerate(rows_sum) if s > 0]
available_cols = [i for i, s in enumerate(cols_sum) if s > 0]

nr = len(available_rows)
nc = len(available_cols)

dnc = Dinic(nr + nc + 2)
s = nr + nc
t = s + 1
INF = 1 << 40
ans = 0

for ri, i in enumerate(available_rows):
    dnc.add_link(s, ri, rows_sum[i])
    dnc.add_link(ri, t, 0)
    ans += rows_sum[i]

for cj, j in enumerate(available_cols, start=nr):
    dnc.add_link(s, cj, 0)
    dnc.add_link(cj, t, cols_sum[j])
    ans += cols_sum[j]

for ri, i in enumerate(available_rows):
    for cj, j in enumerate(available_cols, start=nr):
        if aaa[i][j] < 0:
            dnc.add_link(ri, cj, INF)
        elif aaa[i][j] > 0:
            dnc.add_link(ri, cj, aaa[i][j])

res = dnc.max_flow(s, t)
ans -= res
print(ans)

Ex - Yet Another Path Counting

問題

$N \times N$ のグリッドの各マスに、ラベル $A_{i,j}$ が設定されている
あるマスから「$0$ 回以上の右または下への1マス移動」を繰り返してあるマスで移動を終える経路を「パス」と呼ぶ
出発マスと到着マスのラベルが同じパスの個数を $\mod{998244353}$ で求めよ
$1 \le N \le 400$

解法

複数のラベルをまとめて算出、というのはかなり難しそうなので、ラベル毎に答えを求めていく。

解き方が2種類あって、マスが疎（個数が少ない）時に高速な方法と、密（個数が多い）時に効率的な方法を使い分ける。

1つの解法が浮かぶと、それをどうにか高速化する方法を考えてしまい、2つめの解法の存在に気づきにくい。

解法①

ラベルが同じ起終点ペアを全探索。

右と下移動のみで到達できない位置関係ならパス数は0。
下に $r$ 回、右に $c$ 回移動するなら二項係数 ${}_{r+c}C_r$ がそのペア間のパス数。これを全ペアで合計する。

1ラベルあたりの計算量は、そのラベルが設定されたマスの個数を $L_i$ として、$O(L_i^2)$。
全体ではこれをラベル毎に合算した計算量がかかる。

解法②

よくある経路数数え上げDP。
左上から順に、「そのマスのすぐ左と上の値を足し合わせる」やつ。

$DP[i][j]=(i,j)$ に至るパスで、始点のラベルが現在着目中のラベルであるものの個数

全てが $0$ の状態から始め、 $A_{i,j}$ が着目中のラベルであるときには、そこからスタートするパスが新たに発生するので+1する。

最終的に、着目中のラベルが設定されたマスの $DP$ 値の合計が、そのラベルに関する総パス数。

1ラベルあたりの計算量は、そのラベルのマスの個数に依らず、$O(N^2)$。（枝刈りできるっちゃできる）

場合分け

解法①では、例えば同じラベルを持つマスの個数 $L_i$ が、各ラベル $L_i=L$ で大体同程度な場合はラベルの種類数が $\dfrac{N^2}{L}$、全体の計算量は $O(N^2L)$ となる。$L$ が小さいときは十分通る計算量であることがわかる。

解法②ではラベルの種類数のみに依存するので、$L$ が大体同程度な場合、ラベルの種類数が $\dfrac{N^2}{L}$、全体の計算量は $O(\dfrac{N^4}{L})$ となる。$L$ が大きければよさそうなことがわかる。

$O(N^2L)$ と $O(\dfrac{N^4}{L})$ のバランスが取れるのは $L=N$ の時であり、ここを基準に処理を振り分ければよさそう。

上記の例では $L$ が同程度の時しか説明できていないが、それ以外の場合でも、$L \le N$ を基準にすると

①は、$\displaystyle \sum_{各ラベル} L_i^2 \le \sum N \cdot L_i = N \sum L_i$ となり、 $\sum L_i$ は、つまりこの処理を適用する総マス数なので $N^2$ 以下。$N \sum L_i \le N^3$。

②は、$N$ 以上のマス数があるラベルは多くとも $N$ 種類以下しかないので、1種類あたり $O(N^2)$ なら全体で $O(N^3)$。

となり、いずれも $O(N^3)$ に収まることが確認できる。①の解析の仕方が上手。

Python3


import os
import sys

import numpy as np


def solve(inp):
    def pow_mod(x, n, m):
        r = 1
        y = x % m
        while n:
            if n & 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = pow_mod(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    MOD = 998244353

    n = inp[0]
    aaa = np.zeros((n, n), dtype=np.int64)
    for i in range(n):
        aaa[i, :] = inp[1 + i * n:1 + (i + 1) * n]

    facts, finvs = prepare_factorials(n * 2, MOD)

    list_of_tuple = [(n, n)]
    list_of_tuple.clear()
    locations = [list_of_tuple.copy() for _ in range(n * n + 1)]

    for i in range(n):
        for j in range(n):
            a = aaa[i, j]
            locations[a].append((i, j))

    ans = n * n
    dp = np.zeros((n, n), dtype=np.int64)

    for c in range(n * n + 1):
        loc = locations[c]
        m = len(loc)
        if m == 0:
            continue
        if m < n:
            for li in range(m):
                i0, j0 = loc[li]
                for lj in range(li + 1, m):
                    i1, j1 = loc[lj]
                    if (i0 <= i1) ^ (j0 <= j1) == 1:
                        continue
                    di = abs(i0 - i1)
                    dj = abs(j0 - j1)
                    ans += facts[di + dj] * finvs[di] % MOD * finvs[dj]
                    ans %= MOD
        else:
            dp.fill(0)
            for i in range(n):
                for j in range(n):
                    if i > 0:
                        dp[i, j] += dp[i - 1, j]
                    if j > 0:
                        dp[i, j] += dp[i, j - 1]
                    dp[i, j] %= MOD
                    if aaa[i, j] == c:
                        ans += dp[i, j]
                        ans %= MOD
                        dp[i, j] += 1

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

目次

AtCoder Beginner Contest 259 E,G,Ex問題メモ

E - LCM on Whiteboard

問題

解法

G - Grid Card Game

問題

解法

Ex - Yet Another Path Counting

問題

解法

解法①

解法②

場合分け