AtCoder Beginner Contest 422 D,F,G問題メモ

AtCoder Beginner Contest 422

大会の決勝を兼ねていたため、珍しくお昼の開催。海外勢には参加しづらい時間帯のためか、参加者数は若干少なめ？

D - Least Unbalanced

問題文

$N$ を正整数とします。長さ $2^N$ の非負整数列 $A=(A_1, A_2, \dots, A_{2^N})$ のアンバランスさを次の操作によって得られる非負整数値として定義します。
- はじめ、$X=0$ とする。
- 次の一連の操作を $N$ 回行う。
  - $X$ を $\max(X, \max(A) - \min(A))$ に更新する。ここで $\max(A)$ および $\min(A)$ は数列 $A$ の最大値と最小値を意味する。
  - 先頭から順に $2$ つずつ要素を組にして、それらの和を並べることでできる長さが $A$ の半分の数列を、新たな $A$ とする。すなわち、$A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert})$ とする。
- 最終的な $X$ をアンバランスさとする。

例えば $N=2, A=(6, 8, 3, 5)$ は以下の手順によりアンバランスさが $6$ であるとわかります。
- はじめ、$X=0$ である。
- 1 回目の一連の操作は次の通りである。
  - $X$ を $\max(X, \max(A) - \min(A)) = \max(0, 8 - 3) = 5$ に更新する。
  - $A$ を $(6+8, 3+5) = (14, 8)$ とする。
- 2 回目の一連の操作は次の通りである。
  - $X$ を $\max(X, \max(A) - \min(A)) = \max(5, 14 - 8) = 6$ に更新する。
  - $A$ を $(14 + 8) = (22)$ とする。
- 最終的に $X=6$ となる。

非負整数 $K$ が与えられます。長さ $2^N$ の非負整数列であって総和が $K$ であるものの中で、アンバランスさが最小値を取る数列を構成してください。

制約

$1 \leq N \leq 20$
$0 \leq K \leq 10^9$
$N, K$ は整数

解法1

区間和のセグメント木を、上から半分ずつにして埋めていくイメージ。

N=3  K=35
  |--------------35---------------|
  |------18-------|------17-------|
  |---9---|---9---|---9---|---8---|
  |-5-|-4-|-5-|-4-|-5-|-4-|-4-|-4-|

$K$ が $2^N$ で割り切れるならアンバランスさは $0$。それ以外の場合、$1$ が達成できる。

解法2

とりあえず $K/2^N$ の商の部分は均等に配って、端数の $K \mod 2^N$ をどう分配するかの話になる。
以下の順で配っていくのが良い。

N=4
  0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    1
                                            2
                        3                                       4
              5                   7                   6                   8
         9         13        11        15        10        14        12        16

これは、よく見ると「2進数の $0000,0001,0010,0011,0100,...$ を、文字列として逆から見た順」となっている。
その順で端数分を配ると答えとなる。

または、$A=[0000]$ からはじめて、以下のように端数を配っていくことでもよい。

$A$ のそれぞれに1bit目を立てたindexに配り、$A$ にそれらを加える→$A=[0000,1000]$
$A$ のそれぞれに2bit目を立てたindexに配り、$A$ にそれらを加える→$A=[0000,1000,0100,1100]$
$A$ のそれぞれに3bit目を立てたindexに配り、$A$ にそれらを加える→$A=[0000,1000,0100,1100,0010,...]$

Python3

def solve(n, k):
    n2 = 1 << n
    d, m = divmod(k, n2)
    ans = [d] * n2
    if m == 0:
        return 0, ans
    ans[0] += 1
    if m == 1:
        return 1, ans
    m -= 1

    q = [0]
    for i in range(n - 1, -1, -1):
        bit = 1 << i
        new = []
        for base in q:
            x = base | bit
            ans[x] += 1
            m -= 1
            if m == 0:
                return 1, ans
            new.append(x)
        q.extend(new)


n, k = map(int, input().split())
u, ans = solve(n, k)
print(u)
print(*ans)

F - Eat and Ride

問題文

$N$ 頂点 $M$ 辺の連結無向グラフがあります。
頂点には頂点 $1,$ 頂点 $2,\ldots,$ 頂点 $N$ と番号付けられており、$i$ 番目 $(1\le i\le M)$ の辺は頂点 $u _ i$ と頂点 $v _ i$ を結んでいます。
$i=1,2,\ldots,N$ について次の問題を解いてください。
- はじめ、高橋くんの体重は $0$ です。
- 高橋くんは、車に乗って頂点 $1$ に訪れ、頂点 $i$ に向かって移動を行います。
- 高橋くんが頂点 $v\ (1\le v\le N)$ に訪れるとき、高橋くんの体重は $W _ v$ だけ増加します。
- 高橋くんが乗っている車は辺に沿って移動することができます。
- 高橋くんが辺を通過するとき、そのときの高橋くんの体重を $X$ として、車は燃料を $X$ 消費します。
- 高橋くんが頂点 $i$ にたどり着くために消費する燃料の量の最小値を求めてください。

制約

$1\le N\le5000$
$1\le M\le5000$
$1\le W _ i\le10 ^ 9\ (1\le i\le N)$
$1\le u _ i\le v _ i\le N\ (1\le i\le M)$
与えられるグラフは連結
入力はすべて整数

解法

Dijkstraの改良だが計算量が間に合う証明はできていない。
実装してみたら意外と高速に通ったが、テストケースに助けられているだけなのかは不明。

この問題の難しい点は、「$1→v$ の最適な経路」と「$1→(v経由)→u$ の最適な経路の $1→v$ の部分」が、同じとは限らない点にある。

①-------②-------⑦--⑧
 `-③--④--⑤--⑥-'

i  1   2  3  4  5  6  7  8
W  1  10  1  1  1  1  1  1

⑦への燃料は、
①→②→⑦の12が最適だが、その時の体重は12
①→③→...→⑦の経路を取れば、燃料は15かかるが、体重は6

⑧までの燃料は、
①→②→⑦→⑧だと増えた体重が重くかかり、24
①→③→...→⑦→⑧だと21で逆転する。

⑦に燃料12で到達した後、別経路で燃料15で到達しても、その後の探索を広げる必要があるということになる。

ただし「燃料・体重のいずれも、過去に訪れた場合より悪い」場合は、さすがにそれ以降の頂点も最適にはなり得ない。
少なくともどちらかが過去に訪れたときより小さいなら、探索を広げればよい。

燃料を第一基準としてDijkstraをおこなうと、ある頂点に訪れるのは「消費燃料が小さい順」であると保証される。
よって、通常のDijkstraにおけるコスト（今回は燃料）の他に「$w_v:=$ これまでに頂点 $v$ を訪れたときの最小体重」も記録しておき、現在体重がそれを下回る場合のみ、探索を広げることをすればよい。

Python3

from heapq import heappop, heappush


def solve(n, m, www, edges):
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].append(v)
        links[v].append(u)

    INF = 1 << 60
    fuels = [INF] * n
    last_w = [INF] * n
    fuels[0] = 0
    q = [(0, 0, 0)]
    while q:
        f, w, u = heappop(q)
        if fuels[u] <= f and last_w[u] <= w:
            continue
        fuels[u] = min(fuels[u], f)
        last_w[u] = min(last_w[u], w)
        nw = w + www[u]
        nf = f + nw
        for v in links[u]:
            if fuels[v] <= nf and last_w[v] <= nw:
                continue
            heappush(q, (nf, nw, v))
    return fuels


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

解法2

公式Editorialの、計算量保証のある解法。

「$x$ に到着するまでに通る辺数」を固定すると、ある頂点 $v$ に訪れたときの全体にかかるコストは $W_v \times 残り辺数$ となる。

x までに4辺通るとすると

  ①----> (a) ----> (b) ----> (c) ----> (x)

W1×4    Wa×3     Wb×2     Wc×1      ←この合計が、このパスのコスト

1つのパスの中で同じ頂点を訪れる意味は無いので、通る辺数は最大 $N-1$ に限られる。

よって、それぞれの頂点を $(頂点番号, 残り辺数)$ とし、 $(u,i)→(v,i-1)$ にコスト $W_u \times i$ の辺を張ればよい。

頂点数、辺数が高々 $N$ 倍となるので、$N^2$ 頂点、$MN$ 辺のDijkstraとして解ける。

G - Balls and Boxes

問題文

正整数 $N, A, B, C$ が与えられます。
問題 $1$ および問題 $2$ をそれぞれ解いてください。

問題1
- $N$ 個のボールがあります。ボール同士は区別できません。
- 次の条件を満たすように、区別できる箱 $1,2,3$ に全てのボールを入れる方法の個数を $998244353$ で割った余りを求めてください。
  - 箱 $1$ に入っているボールの個数は $A$ の倍数である。
  - 箱 $2$ に入っているボールの個数は $B$ の倍数である。
  - 箱 $3$ に入っているボールの個数は $C$ の倍数である。

問題2
- $1$ から $N$ までの番号のついた $N$ 個のボールがあります。ボール同士は区別できます。
- 次の条件を満たすように、区別できる箱 $1,2,3$ に全てのボールを入れる方法の個数を $998244353$ で割った余りを求めてください。
  - 箱 $1$ に入っているボールの個数は $A$ の倍数である。
  - 箱 $2$ に入っているボールの個数は $B$ の倍数である。
  - 箱 $3$ に入っているボールの個数は $C$ の倍数である。

制約

$1 \leq N \leq 3 \times 10^5$
$1 \leq A \leq 3 \times 10^5$
$1 \leq B \leq 3 \times 10^5$
$1 \leq C \leq 3 \times 10^5$
入力される値は全て整数

解法

知ってたら一発の問題。以下のサイトにズバリの解法がある。

形式的べき級数による数え上げ（JSC2019予選 [F]） | maspyのHP
- 「分割数と形式的べき級数」の項

問題1は、取れる値に制約（$A,B,C$ の倍数であること）がある上での $N$ の分割数である。
以下の3つの形式的冪級数の積をとり、$x^N$ の項の係数が答えとなる。

$x^0+x^A+x^{2A}+...$
$x^0+x^B+x^{2B}+...$
$x^0+x^C+x^{2C}+...$

問題2は、たとえば箱1,2,3に $p,q,r$ 個入れた場合のボールの対応付け方は、$\dfrac{N!}{p!q!r!}$ 個ある。
よって、これも係数に折り込んでから畳み込めばよい。最後に $x^N$ の項の係数の $N!$ 倍が答えとなる。

$x^0+ \dfrac{1}{A!}x^A+\dfrac{1}{(2A)!}x^{2A}+...$
$x^0+ \dfrac{1}{B!}x^B+\dfrac{1}{(2B)!}x^{2B}+...$
$x^0+ \dfrac{1}{C!}x^C+\dfrac{1}{(2C)!}x^{2C}+...$

Python3

import numpy as np
import numpy.typing as npt
import numba


@numba.njit('(i8[:],i8[:])', cache=True)
def convolve_998244353(aaa: npt.NDArray[np.int64], bbb: npt.NDArray[np.int64]) -> npt.NDArray[np.int64]:
    MOD = 998244353
    SUM_E = np.array(
        [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456,
         131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443,
         56250497, 867605899, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)
    SUM_IE = np.array(
        [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882,
         927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183,
         824071951, 103369235, 0, 0, 0, 0, 0, 0, 0, 0], np.int64)

    def bit_length(n):
        x = 0
        while 1 << x < n:
            x += 1
        return x

    def bit_scan_forward(n):
        x = 0
        while n & 1 == 0:
            n >>= 1
            x += 1
        return x

    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def butterfly(aaa, mod, sum_e):
        n = aaa.size
        h = bit_length(n)

        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p] * now % mod
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = (l - r) % mod
                now = now * sum_e[bit_scan_forward(~s)] % mod

    def butterfly_inv(aaa, mod, sum_ie):
        n = aaa.size
        h = bit_length(n)

        for ph in range(h, 0, -1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = aaa[i + offset]
                    r = aaa[i + offset + p]
                    aaa[i + offset] = (l + r) % mod
                    aaa[i + offset + p] = ((l - r) * inow) % mod
                inow = inow * sum_ie[bit_scan_forward(~s)] % mod

    n = aaa.size
    m = bbb.size
    k = n + m - 1
    z = 1 << bit_length(k)
    raaa = np.zeros(z, np.int64)
    rbbb = np.zeros(z, np.int64)
    raaa[:n] = aaa
    rbbb[:m] = bbb
    butterfly(raaa, MOD, SUM_E)
    butterfly(rbbb, MOD, SUM_E)
    for i in range(z):
        raaa[i] = raaa[i] * rbbb[i] % MOD
    butterfly_inv(raaa, MOD, SUM_IE)
    iz = mod_pow(z, MOD - 2, MOD)
    for i in range(k):
        raaa[i] = raaa[i] * iz % MOD
    return raaa[:k]


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, a, b, c):
    MOD = 998244353

    facts, finvs = precompute_factorials(n, MOD)

    def prepare(a):
        f1 = np.zeros(n + 1, np.int64)
        f2 = np.zeros(n + 1, np.int64)
        for i in range(n // a + 1):
            f1[i * a] = 1
            f2[i * a] = finvs[i * a]
        return f1, f2

    f1, f2 = prepare(a)
    g1, g2 = prepare(b)
    h1, h2 = prepare(c)

    fg1 = convolve_998244353(f1, g1)[:n + 1]
    fgh1 = convolve_998244353(fg1, h1)
    fg2 = convolve_998244353(f2, g2)[:n + 1]
    fgh2 = convolve_998244353(fg2, h2)

    return fgh1[n], fgh2[n] * facts[n] % MOD


n, a, b, c = map(int, input().split())
ans = solve(n, a, b, c)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 422 D,F,G問題メモ

D - Least Unbalanced

問題文

制約

解法1

解法2

F - Eat and Ride

問題文

制約

解法

解法2

G - Balls and Boxes

問題文

制約

解法