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

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$ から、長さ $M$ の $N$ 本の枝が伸びている。
どの枝に入ったとしても、最奥の頂点まで到達しなければあまり意味が無い。
最奥の頂点が塗られないまま0に戻ったら、結局、最奥を塗るために再度その枝に入らないといけない。

期待値を、移動の過程を「枝の1つに入ってから出るまで」で区切って計算しようと思うと、なかなか難しい。
その枝の最奥まで到達した場合・しなかった場合で確率・期待値を分けて計算したいが、あまり上手くできない。

「枝に入ってから出るまで」ではなく、「どれかの最奥に着くまで」で移動を区切って考えるとスムーズである。

①頂点 $0,1,...,M$ からなる一直線のグラフで $0$ からランダムウォークする。
- 負の数や $M+1$ 以上にはならず、端の $0,M$ ではそれぞれ必ず $+1,-1$ に移動するとする。
- このグラフで $M$ に至ることは、元のグラフでどれかの枝の最奥に至ったことに相当する。$M$ に至ったら②に進む。
②どの枝の最奥に至ったかは等確率なので、$N$ 面ダイスを振って後から枝を決めると考える。
- その枝が未探索だったら未探索枝が1減る
③未探索枝が0になったら終了
④未探索枝が1以上なら、$M$ から $0$ までランダムウォークで戻る。①に戻る。

①で $0→M$ に至る回数期待値と、④で $M→0$ に至る回数期待値は等しい。$E$ とする。

$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(M)$ はゴールなので $0$ となる。$E(0)$ は必ず1に移行するので少し遷移が異なる。

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

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

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

コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語

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

答えは、$2FE-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)

E - Adjacent GCD

問題文

正整数列 $B = (B_1, B_2, \dots, B_k)$ のスコアを $\displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1})$ として定義します。
長さ $N$ の正整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられるので、$m = 1, 2, \dots, N$ に対して次の問題を解いてください。
- 列 $(A_1, A_2, \dots, A_m)$ の空でない部分列は $2^m - 1$ 通りありますが、それらのスコアの総和を $998244353$ で割った余りを求めてください。ただし、$2$ つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

制約

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

解法

$A$ の制約 $10^5$ 以下で最多の約数を持つものは、83160 の 128 個である。

大まかなイメージとして、$i=1,2,...,N$ の順に、$A_i$ の約数1つ1つについて「自分より左に、この約数を持つ数は何個ありましたか？」を参照＆メモしていく、という解法が考えられる。
$N$ 以下の整数の中での約数の個数の最大値を $d(N)$ として、 $O(d(A_{\max})N) \sim 6 \times 10^7$ の計算量はちょっと不安を感じるが、定数倍が軽ければPyPyでも間に合いそう。

だが、たとえば2数のGCDが 6 の場合、単に約数毎に個数をメモするだけの方法では 1,2,3,6 の4回で重複して数えられてしまう。

これを解決するには、オイラーのトーシェント関数が使える。

オイラーのφ関数

任意の $n$ について、「$n$ の全ての約数 $d$ に対して $\phi(d)$ を合計すると、$n$ になる」という性質を持っている。
これを使うことで、約数ごとに個数をカウントして合計を取って正しく求まるようになる。

           約数毎の個数カウント
 d  φ(d)  A:  6  9  8   12
 1    1        1  1  1   ←  3個×φ(1)  = 3
 2    1        1     1   ←  2個×φ(2)  = 2
 3    2        1  1      ←  2個×φ(3)  = 4
 4    2              1   ←  1個×φ(4)  = 2
 6    2        1         ←  1個×φ(6)  = 2
 8    4              1
 9    6           1
12    4                  ←  0個×φ(12) = 0
                                         ~~~~~ 合計 13  ←約数ごとのφの合計が、
                                                        ↙ペア毎にGCDを計算した合計と
GCD(6,12)=6, GCD(9,12)=3, GCD(8,12)=4      →  合計 13    一致する

また、この問題で求めるべきは、全ペアのGCDの総和ではなく、「全ての部分列の【隣接GCDの総和】の総和」なので、たとえば $A=(1,2,3,4,5,6)$ に対して $GCD(3,5)$ は、それより外側にある $1,2,6$ をそれぞれ部分列に含むか含まないかの $2^3$ 通りで加算される。

よって、それを織り込みながらカウントする必要がある。

$S_m:=A$ の先頭 $m$ 要素からなる数列に対するスコア
$C_{m,d}:=A$ の先頭 $m$ 要素からなる数列の部分列のうち、末尾の要素の約数に $d$ が含まれるものの個数（$m$ の次元は実装上は省略し、逐次更新）

$S_m$ を求めたい。
- $S_{m-1}$ に含まれるペアは、$S_m$ にも全て含まれる。加算回数は $A_m$ を部分列に含むか否かで、全てのペアで2倍になる。
- $A_m$ を部分列の末尾に追加することで生じる新たなペアのスコアは、$A_m$ の約数 $d$ ごとに $C_{m-1,d} \phi(d)$ を合計することで求まる。
$\displaystyle S_m = 2S_{m-1} + \sum_{d|A_m}C_{m-1,d}\phi(d)$ となる。
$A_m$ の各約数 $d$ に対して、寄与を $C_{m,d}$ に加算する。
- $A_m$ が末尾となるような部分列は $2^{m-1}$ 個あるため、$C_{m,d}=C_{m-1,d}+2^{m-1}$ となる。

これを、$m=1,2,...$ の順に求めていくことで、全ての $m$ に対する $S_m$ が求まる。

Python3

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


def get_divisor(x, spf, memo={}):
    if x in memo:
        return memo[x]
    facts = prime_factorize(x, spf)
    result = [1]
    for p, c in facts:
        for j in range(len(result)):
            k = result[j]
            for _ in range(c):
                k *= p
                result.append(k)
    result.sort()
    memo[x] = result
    return result


def get_euler_totient(n):
    """ オイラーのトーシェント関数を、i=1～n まで計算する。 """
    totient = list(range(n + 1))
    for i in range(2, n + 1):
        if totient[i] == i:
            for j in range(i, n + 1, i):
                totient[j] = totient[j] // i * (i - 1)
    return totient


def solve(n, aaa):
    MOD = 998244353
    a_max = max(aaa)
    euler_totient = get_euler_totient(a_max)
    spf = get_spf(a_max)
    counter = [0] * (a_max + 1)
    ans = 0
    buf = []
    p2 = 1
    for a in aaa:
        ans *= 2
        divisors = get_divisor(a, spf)
        for d in divisors:
            ans += counter[d] * euler_totient[d]
            counter[d] += p2
            counter[d] %= MOD
        ans %= MOD
        buf.append(ans)
        p2 *= 2
        p2 %= MOD
    return buf


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print('\n'.join(map(str, ans)))

目次

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

A - mod M Game 2

問題文

制約

解法

C - Sum of Three Integers

問題文

制約

解法

D - Random Walk on Tree

問題文

制約

解法

E - Adjacent GCD

問題文

制約

解法