AtCoder Beginner Contest 445 E,F,G問題メモ

AtCoder Beginner Contest 445

帰省中によりノートPCから挑戦したが、環境の準備不足がいろいろ明らかになった。
もしオンサイトがあったら問題になってたので、その前に気づけて良かった、、、か？

E - Many LCMs

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
$k=1,2,\dots,N$ について、$A$ のうち $A_k$ を除いた $N-1$ 個の要素の最小公倍数を $998244353$ で割ったあまりを求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \leq T \leq 10^5$
$2 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^7$
入力はすべて整数
$1$ つの入力に含まれるテストケースについて、$N$ の総和は $2 \times 10^5$ 以下

解法

普通に最小公倍数を取っていたら一般的なプログラムで扱える整数の範囲を軽く超える。

$A$ の全要素のLCMを $L=2^{r_1} \cdot 3^{r_2} \cdot 5^{r_3} \cdot 7^{r_4}...$ と表す。
$r_1$ は、各 $A_i$ を素因数分解したときの $2$ の指数（$2^r$ の $r$）の最大値
$r_2$ は、各 $A_i$ を素因数分解したときの $3$ の指数（$3^r$ の $r$）の最大値
：

という形で表せば、$A$ に素因数として現れる素数ごとに求めた結果を掛け合わせられる。

で、$A_i$ だけ除いた要素のLCMは、$A_i$ の素因数分解の結果をたとえば $2^x3^y7^z$ として

$Ans=L$ で初期化する
$x=r_1$ の場合、次に $A$ の中で大きい指数を $q_1$ として、$Ans$ を $2^{x-q_1}$ で割る
$y=r_2$ の場合、次に $A$ の中で大きい指数を $q_2$ として、$Ans$ を $3^{y-q_2}$ で割る
$z=r_4$ の場合、次に $A$ の中で大きい指数を $q_4$ として、$Ans$ を $7^{z-q_4}$ で割る

とすれば、答えが求められる。各素因数につき、指数の上位2つまでを保持しておけばよい。

Python3

from collections import defaultdict


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


def prime_factorize(x, spf):
    """ xを素因数分解、(素数, 個数)の配列で返す """
    factors = []
    prev = -1
    cnt = 0
    while x > 1:
        if spf[x] == prev:
            cnt += 1
        else:
            if prev != -1:
                factors.append((prev, cnt))
            prev = spf[x]
            cnt = 1
        x //= spf[x]
    if prev != -1:
        factors.append((prev, cnt))
    return factors


SPF = get_spf(10 ** 7)
MOD = 998244353


def solve(n, aaa):
    top_idx = {}
    top_fac = {}
    sec_fac = defaultdict(int)
    pfs = []
    for i in range(n):
        a = aaa[i]
        pf = prime_factorize(a, SPF)
        pfs.append(pf)
        for p, c in pf:
            if p not in top_idx:
                top_idx[p] = i
                top_fac[p] = c
            elif top_fac[p] < c:
                sec_fac[p] = top_fac[p]
                top_idx[p] = i
                top_fac[p] = c
            elif sec_fac[p] < c:
                sec_fac[p] = c
    all_lcm = 1
    for p, c in top_fac.items():
        all_lcm *= pow(p, c, MOD)
        all_lcm %= MOD

    ans = []
    for i in range(n):
        tmp = all_lcm
        pf = pfs[i]
        for p, c in pf:
            if top_idx[p] == i:
                tmp *= pow(p, sec_fac[p] - c, MOD)
                tmp %= MOD
        ans.append(tmp)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(*ans)

F - Exactly K Steps 2

問題文

頂点 $1,$ 頂点 $2,\ldots,$ 頂点 $N$ の $N$ 頂点からなる有向グラフがあります。
$1$ 以上 $N$ 以下の任意の整数の $2$ つ組 $(i,j)$ について、頂点 $i$ から頂点 $j$ への有向辺がちょうど $1$ 本存在し、そのコストは $C _ {i,j}$ です。

正整数 $K$ が与えられます。
$s=1,2,\ldots,N$ のそれぞれについて、以下の問題を解いてください。
- 頂点 $s$ から出発し、辺に沿って移動することを $K$ 回繰り返して頂点 $s$ へ向かう方法のうち、通った辺のコストの総和としてありうる最小値を求めよ。

制約

$1\le N\le100$
$1\le K\le10 ^ 9$
$0\le C _ {i,j}\le10 ^ 9\ (1\le i\le N,1\le j\le N)$
入力はすべて整数

解法

ダブリング。

$A(c)_{i,j}:=i$ から $j$ へ、ちょうど $c$ 回の移動で辿り着くときの最小コスト

とする。最初は、$A(1)=C$ がわかっている。

$A(c_1)$ と $A(c_2)$ がわかっていれば、ワーシャルフロイドっぽく以下の擬似コードで、 $A(c_1+c_2)$ が $O(N^3)$ で求まる。（$i-(c_1回)→k-(c_2回)→j$ と移動する $k$ を全探索している）

result を各要素 INF の NxN 行列で初期化する

for i in range(N):
    for j in range(N):
        for k in range(N):
            result[i][j] = min(result[i][j], A(c1)[i][k]+A(c2)[k][j])

元のワーシャルフロイド法では、result を新規に作らず距離配列 $C$ を上書きしていくことで「移動回数に依らない、全ての頂点間の最短距離」が求まるが、ここでは result を新規に作っているので計算済みの値が更新されず、あくまで「$c_1+c_2$ 回の移動」での最短距離が求まる点に注意する。

$A(1)$ 同士にこの合成を適用すると $A(2)$ が、以下、$A(4),A(8),A(16),...$ が順次わかる。

$K=2+16+32+256$ など2の冪乗の和で表した場合、$A(2),A(16),A(32),A(256)$ の合成で答えが求められる。

計算量は $A(\log{K}N^3)$ となる。

Python3

def solve(n, k, ccc):
    def merge(aaa, bbb):
        result = [[INF] * n for _ in range(n)]
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    result[i][j] = min(result[i][j], aaa[i][k] + bbb[k][j])
        return result

    INF = 1 << 60
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    while k:
        if k & 1:
            dist = merge(dist, ccc)
        ccc = merge(ccc, ccc)
        k >>= 1
    ans = [0] * n
    for i in range(n):
        ans[i] = dist[i][i]
    return ans


n, k = list(map(int, input().split()))
ccc = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, k, ccc)
print('\n'.join(map(str, ans)))

G - Knight Placement

問題文

縦 $N$ 行、横 $N$ 列のマス目があります。
それぞれのマスは空きマスか壁マスのどちらかで、入力により与えられます。
あなたは、このマス目にコマを置けるだけ置きたいです。コマの置き方には以下のような制約があります。
- 壁マスにコマを置くことはできない。
- $1$ つのマスにコマを $2$ つ以上置くことはできない。
- マス $(i,j)$ にコマが置かれているとき、$(i \pm A, j \pm B)$ または $(i \pm B, j \pm A)$ で表される最大8マスにコマを置くことはできない。
この制約のもと置くことができるコマの個数の最大値を $K$ として、制約を満たす $K$ 個のコマの配置をひとつ求めてください。

制約

$1\le N\le300$
$0\le A\le B\le N$
$1\le B$
$N,A,B$ は整数
$S _ i$ は ., # からなる長さ $N$ の文字列 $(1\le i\le N)$

解法

あちらを立てればこちらが立たず、という関係がいっぱいあるこのような問題は、フローを検討してみる。

とりあえず全ての空きマスにコマを置き、「置けないコマ」をコストとし、コストを最小化するとよさそう。
燃やす埋める問題に言い換え、互いに利きにある2マス間で「どちらにもコマを置くと罰金 $\infty$」という制約を与えたいが、燃やす埋めるで「どちらも同じ選択肢を選んだときに罰金」という制約を与えるには、関係性が二部グラフである必要がある。

で、この問題における互いに利きにあるマスの関係性って、実は二部グラフにできる。

略証

なので、マスを二部グラフの2グループに分け、グループ①の方は「$S$ ならコマを置く」、②は「$T$ ならコマを置く」と定義して、利きの関係にある①→②のマス間の辺に $\infty$ の辺を張れば、最小カットが答えとなる。

$S,T$ の意味: 燃やす埋める問題の「カットの定義」参照

あとは復元すればよい。

Python3

from atcoder.maxflow import MFGraph


def solve(n, a, b, field):
    links = [set() for _ in range(n * n)]
    MOVE = [(-a, -b), (-b, -a), (-a, b), (b, -a), (a, -b), (-b, a), (a, b), (b, a)]
    for i in range(n):
        for j in range(n):
            key1 = i * n + j
            for di, dj in MOVE:
                ni = i + di
                nj = j + dj
                if 0 <= ni < n and 0 <= nj < n:
                    key2 = ni * n + nj
                    links[key1].add(key2)
                    links[key2].add(key1)
    groups = [-1] * (n * n)
    for i in range(n * n):
        if groups[i] != -1:
            continue
        groups[i] = 0
        q = [i]
        while q:
            u = q.pop()
            for v in links[u]:
                if groups[v] == -1:
                    groups[v] = groups[u] ^ 1
                    q.append(v)
    dnc = MFGraph(n * n + 2)
    s = n * n
    t = s + 1
    blank_count = 0
    INF = 1 << 60
    for i in range(n):
        for j in range(n):
            if field[i][j] == '#':
                continue
            key = i * n + j
            blank_count += 1
            if groups[key] == 0:
                dnc.add_edge(s, key, 1)
                for v in links[key]:
                    i2, j2 = divmod(v, n)
                    if field[i2][j2] == '#':
                        continue
                    dnc.add_edge(key, v, INF)
            else:
                dnc.add_edge(key, t, 1)
    f = dnc.flow(s, t)
    result = []
    for row in field:
        result.append(['o' if c == '.' else '#' for c in row])
    reachable = dnc.min_cut(s)
    for key in range(n * n):
        i, j = divmod(key, n)
        if field[i][j] == '#':
            continue
        if reachable[key]:
            if groups[key] == 1:
                result[i][j] = '.'
        else:
            if groups[key] == 0:
                result[i][j] = '.'
    ans = [''.join(row) for row in result]
    return ans


n, a, b = list(map(int, input().split()))
field = [input() for _ in range(n)]
ans = solve(n, a, b, field)
print('\n'.join(ans))

目次

AtCoder Beginner Contest 445 E,F,G問題メモ

E - Many LCMs

問題文

制約

解法

F - Exactly K Steps 2

問題文

制約

解法

G - Knight Placement

問題文

制約

解法