AtCoder Regular Contest 185 A,C,D問題メモ

AtCoder Regular Contest 185

A - mod M Game 2

問題文

正整数 $N, M$ があります。ここで $N \lt M$ が成り立ちます。
Alice と Bob がゲームをします。$2$ 人は $1, 2, \dots, N$ が書かれたカードを $1$ 枚ずつ、合計 $N$ 枚のカードをそれぞれ持っています。
ゲームは以下のように進行します。
- Alice を先攻として $2$ 人が交互に「手札を $1$ 枚選び、場に出す」という操作を繰り返します。
- カードが場に出た直後に、今まで場に出たカードに書かれている数の総和が $M$ で割り切れる状態になったら、直前にカードを出した人の負け、そうでない人の勝ちとなります。
- 上の条件を満たすことなく両者が持っているカードを全て出し切った場合は Alice の勝ちとなります。
双方が最適に行動した時、Alice と Bob のどちらが勝ちますか？
$T$ 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

制約

$1 \leq T \leq 10^5$
$1 \leq N \lt M \leq 10^9$
入力される値は全て整数

解法

論理クイズ的問題。

$N \lt M$ なので、双方とも、手元に2枚以上のカードが残っているときは必ず負けを回避できる。

Bobが勝つためのチャンスは一度きり。
Aliceがラス1を出したときに $M$ の倍数となるように、Bobが仕向けられるかにかかっている。

このとき、場にあるカードの総和は $N(N+1)-(Bobが最後に残したカード)$ で、Bobだけがこの値を操作できる。

$b=N(N+1) \mod{M}$ とすると、$b$ を残すことで、ラス1の値を $M$ の倍数にできる。
$b=0$ または $b \ge N+1$ なら、そもそも初期の手持ちにないのでできず、Aliceの必勝である。

$1 \le b \le N$ なら手持ちにあるのでBobは $b$ を残すと勝つことができる。

残る問題は、Bobがそれまでに負けることが無いか？

Bobの手持ちが3枚以上なら、選択肢が2つ以上あるので負けることはない。
Bobがラス2のカードを出すとき、$b$ を残すように出さなければならず自由度が無い。
Bobが負けることがあるとすれば、このタイミングである。

しかし、Alice,Bob が互いにラスト1枚（それぞれ $a,b$ とする）を持っているとき、場の総和は $N(N+1)-a-b \equiv -a \mod{M}$ である。

$N \lt M$ より、これは $M$ の倍数になることはないので、Bobがラス2の時に負けることはない。

したがって、$N(N+1) \mod{M}$ が $1～N$ の間ならBobの勝ち、それ以外ならAliceの勝ちと判定できる。

Python3

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    total = n * (n + 1)
    rem = total % m
    if 1 <= rem <= n:
        print('Bob')
    else:
        print('Alice')

C - Sum of Three Integers

問題文

整数列 $A = (A_1, A_2, \dots, A_N)$ および整数 $X$ が与えられます。
次の条件を全て満たす整数の組 $(i, j, k)$ を $1$ 組出力してください。
- $1 \leq i \lt j \lt k \leq N$
- $A_i + A_j + A_k = X$
条件を満たす組が存在しない場合はそのことを報告してください。

制約

$3 \leq N \leq 10^6$
$1 \leq X \leq 10^6$
$1 \leq A_i \leq X$
入力される値は全て整数

解法

2数を仮定したらあと1数が存在するかチェックすればよいが、そもそも2数の仮定が $O(N^2)$ なのでできない。

後述の解法をするに当たって、$A$ に同じ値が含まれ、それを2、3回使うような解があった場合、少し判定がややこしくなる。
そういうのは $O(N)$ で判定できるので最初にしてしまい、「解があるとしたら3数がバラバラの組である」という状態にしてしまう。

重複を除いた $A$ を $A'$、長さを $M$ とする。

$F(x):=x^{A'_1}+x^{A'_2}+...+x^{A'_M}$ とし、$F^2$ を畳み込みで計算することで「和が $y$ となる2数が存在するか？」を、任意の $y$ について $O(1)$ で判定できるようになる。

ただし、$F^2$ には同じ2数を重ねて選んだものも含まれているため、それは除いておく。
$i=1,...,M$ について、$F^2$ から $x^{2A'_i}$ を引けばよい。

後は、残り1数 $A'_i$ を固定し、$X-A'_i$ が2数の和として存在すればその2数を $O(M)$ で確認すればよい。

Python3

from collections import defaultdict

import numpy as np
from numba import njit


@njit('(i8[:],i8[:])', cache=True)
def ntt(aaa, bbb):
    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 pow_mod(x, n, m):
        r = 1
        y = x % m
        while n > 0:
            if n & 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r

    def butterfly(aaa):
        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):
        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)
    butterfly(rbbb)
    for i in range(z):
        raaa[i] = raaa[i] * rbbb[i] % MOD
    butterfly_inv(raaa)
    iz = pow_mod(z, MOD - 2, MOD)
    for i in range(k):
        raaa[i] = raaa[i] * iz % MOD
    return raaa[:k]


def solve(n, x, aaa):
    counter = defaultdict(list)
    for i, a in enumerate(aaa, start=1):
        counter[a].append(i)

    # 同じの3つ
    if x % 3 == 0:
        a = x // 3
        if a in counter and len(counter[a]) >= 3:
            return counter[a][:3]
    # 同じの2つ
    for a, pos in counter.items():
        if len(pos) == 1:
            continue
        b = x - a * 2
        if b > 0 and b != a and b in counter:
            i, j = pos[:2]
            k = counter[b][0]
            return i, j, k

    # 全て別々の数から選ぶケースに絞られる
    # 畳み込みで、cnv[x] := 2数の和が x となる方法の個数 を求める。
    aaa = list(counter.keys())
    n = len(aaa)
    bbb = np.bincount(aaa).astype(np.int64)
    cnv = ntt(bbb, bbb).tolist()
    lim = len(cnv) - 1

    # 同じ数が使われるケースを除く
    for a in aaa:
        cnv[a * 2] -= 1

    for i in range(n):
        a = aaa[i]
        if x - a > lim:
            continue
        if cnv[x - a] == 0:
            continue
        # 存在が確定
        for j in range(i + 1, n):
            b = aaa[j]
            c = x - a - b
            if c > 0 and (c in counter) and a != b and b != c and c != a:
                return counter[a][0], counter[b][0], counter[c][0]
    return -1, -1, -1


n, x = map(int, input().split())
aaa = list(map(int, input().split()))
ans = solve(n, x, aaa)
if ans[0] == -1:
    print(-1)
else:
    print(*sorted(ans))

D - Random Walk on Tree

問題文

頂点に $0, 1, \dots, N \times M$ の番号がついた $N \times M + 1$ 頂点の木があります。
- $i$ 本目の辺 $(1 \leq i \leq N \times M)$ は頂点 $i$ と頂点 $\max(i - N, 0)$ を結ぶ辺です。
- また、頂点 $0$ には色が塗られています。それ以外の頂点は色が塗られていません。
高橋君は頂点 $0$ にいます。高橋君は色が塗られていない頂点が存在する間、次の操作を行います。
- 自身がいる頂点に隣接する頂点の中から一様ランダムに頂点を $1$ つ選んで、その頂点に移動する。(全ての選択は独立である。) そして、今いる頂点に色が塗られていなければ色を塗る。
操作を行う回数の期待値を $\text{mod }998244353$ で求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$N, M$ は整数

解法

こんなグラフである。

0---1--5--9   ^
 |--2--6--10  |N
 |--3--7--11  |
 `--4--8--12  v
   <---M--->

どの枝に入ったとしても、結局、最奥の頂点まで到達しなければ意味が無い。
最奥の頂点が塗られないまま0に戻ったら、結局、最奥を塗るために再度その枝が選ばれないといけない。

「0からある枝に入ったとき、その枝の中で、最奥まで行くか、行かずに戻るか」などで分類して確率・期待値を計算しようと思うと、「最奥まで到達する確率」「しない確率」「する場合の回数期待値」「しない場合の回数期待値」など収拾が付かなくなる。

こう考えるとスムーズである。

頂点0から、どれかの枝の最奥に最初に至る回数期待値を $E$ とする。
- この時、途中で0まで戻って複数の枝にまたがって移動が発生するかもしれないが、かまわない。
- あくまで「どこかの最奥まで辿り着く」までの回数が重要。

$E$ は、以下のグラフで「頂点 $i$ からスタートして最奥に至るまでの回数期待値を $E(i)$」として、$E(0)$ を求めれば良い。

M=3
0---1---2---3

$E(3)=0$
$E(2)=1+\frac{E(1)+E(3)}{2}$
$E(1)=1+\frac{E(0)+E(2)}{2}$
$E(0)=1+E(1)$

$E(3)$ はゴールなので $0$ となる。$E(0)$ は必ず1に移行するので少し遷移が異なる。

この $E(0)$ は結果的に $M^2$ になるが、それを知らなくても $O(M)$ かけて計算してもよい。
$E(M)=0$ から順に代入していくことで、$E(0)$ を求めることができる。

また、$E$ は左右反転させれば「どれかの最奥から、0まで戻るための回数期待値」とも等しくなる。

すると、これは1回引くのにコストが往復分で $2E$ かかる、$N$ 個を揃えるコンプガチャと見ることができる。

コンプガチャを引く回数期待値は、$F=\frac{N}{N}+\frac{N}{N-1}+...+\frac{N}{1}$ となる。

ただし、この問題では最後の頂点をコンプした後のみ0に戻らなくてよいため、その分は減算できる。

答えは、$(2F-1)E$ となる。

Python3

def solve(n, m):
    MOD = 998244353
    a = 0
    b = 0
    for _ in range(m - 1):
        a = pow(2 - a, -1, MOD)
        b = (2 + b) * a % MOD
    e = (1 + b) * pow(1 - a, -1, MOD) % MOD

    c = 0
    for i in range(1, n + 1):
        c += pow(i, -1, MOD)
    c %= MOD
    c *= n * 2
    c -= 1
    c %= MOD

    return e * c % MOD


n, m = map(int, input().split())
ans = solve(n, m)
print(ans)

目次

AtCoder Regular Contest 185 A,C,D問題メモ

A - mod M Game 2

問題文

制約

解法

C - Sum of Three Integers

問題文

制約

解法

D - Random Walk on Tree

問題文

制約

解法