AtCoder Beginner Contest 463 F,G問題メモ

AtCoder Beginner Contest 463

E問題は最近のEの中では癒やし枠。

F - Senshuraku

問題文

$2N$ 人の選手が参加する大会が行われています。
各選手にとって、次が最後の試合です。試合は個人戦のため、大会全体ではあと $N$ 試合が残っています。
残る $N$ 回の試合のうち、$i$ 番目 $(1\le i\le N)$ の試合では $2i-1$ 番目の選手と $2i$ 番目の選手が対戦を行います。
それぞれの試合では、対戦する $2$ 人の選手のうち $1$ 人が勝ち、もう $1$ 人が負けます。
- どちらの選手が勝つかは試合ごとに独立に確率 $\dfrac12$ で決まります。
最後の $N$ 試合が始まる前、$i$ 番目 $(1\le i\le2N)$ の選手は $A _ i$ 回勝っています。
すべての試合が終わったあと、勝った回数が最も多い選手の中から一様ランダムかつこれまでの試合結果と独立に優勝選手が選ばれます。
$1$ 番目の選手、$2$ 番目の選手、$\ldots$、$2N$ 番目の選手のそれぞれについて、優勝する確率を${}\bmod998244353$ で求めてください。

制約

$1\le N\le2\times10 ^ 5$
$0\le A _ i\lt2N\ (1\le i\le 2N)$
入力はすべて整数

解法

場合分けが面倒くさくはあるが、場合分けしたそれぞれの答えを求めるのにはそこまで特殊なテクニックは要らない。

まず、$m=\max(A)$ として、$A_i \le m-2$ の選手は勝つ見込みはない。$0$ が答え。
優勝選手の勝利数が $m+1$ の場合と $m$ の場合を考えたいのだが、注意を要するのは、

各試合、必ず一方の選手が勝利する

という点である。例えば、$A_i=m$ 同士が争う試合があったら、必ずいずれかは勝利数 $m+1$ になる。

なので「優勝する可能性のある選手の相手もまた、優勝する可能性がある」場合などは、分けて考えなければならない。具体的には、以下のように場合分けする。

① $p=$（$m$ vs $m$ の対戦カードの個数）
② $q=$（$m$ vs $m-1$ の対戦カードの個数）
③ $r=$（$m$ vs それ以下の対戦カードの個数）
④ $s=$（$m-1$ vs $m-1$ の対戦カードの個数）
⑤ $t=$（$m-1$ vs それ以下の対戦カードの個数）

同じケースに属する人の優勝確率は同じ（②のみ、$m$ と $m-1$ の2種類ある）なので、答えに現れる $0$ でない値は6種類に限られる。

各人の優勝確率を求めるには、自身が勝った場合・負けた場合のそれぞれで、 $k$ ごとに「自身が最多勝利数であり、他に同率が $k$ 人となる確率 $p_k$」を求め、 $\dfrac{1}{k}p_k$ を合計していけばよい。

①のケース

例として、①の選手が優勝する確率を考える。
両者、勝つしか優勝の見込みは無い。

自身の試合

確率 $\frac{1}{2}$ で自身が勝つ。優勝候補の人数は $1$ 人

他の①の試合

確率 $1$ で優勝候補が $p-1$ 人増える。

②と③の試合

$m$ の方が勝った場合のみ、優勝候補となる。その人数が $l$ 人（$0 \le l \le q+r$）となる確率は

$\left ( \dfrac{1}{2} \right )^{q+r} \dbinom{q+r}{l}$

④と⑤の試合

①のケースを考える上では、このケースから優勝者が生まれることは無い。

まとめ

以上をまとめると、①の選手の優勝確率は

$\displaystyle \sum_{l=0}^{q+r} \frac{1}{p+l} \left ( \dfrac{1}{2} \right )^{q+r+1} \dbinom{q+r}{l}$

他のケースも、同様に

自身が勝った場合、負けた場合
自身の試合、自身と同じケースの他の試合、自身と違うケースの試合

それぞれで確率と勝利者数を考えて式を組み立てていくとよい。

①のケースでは、②と③の試合から発生する優勝候補者数 $l$ を仮定し全走査した。
他のケースでも、いずれかのケースからの優勝候補者数を仮定する必要があるが、（実際に式を組み立ててみると分かるが）同時に2つ以上のパラメータを仮定する必要は無い。よって全体 $O(N)$ で求められる。

Python3

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, aaa):
    m = max(max(a, b) for a, b in aaa)
    p, q, r, s, t = 0, 0, 0, 0, 0
    types = [0] * (n * 2)
    # p: m vs m : type=1
    # q: m vs m-1 : type=2;(mの方) 3;(m-1の方)
    # r: m vs others : type=4
    # s: m-1 vs m-1 : type=5
    # t: m-1 vs others : type=6
    for i in range(n):
        a, b = aaa[i]
        i1 = i * 2
        i2 = i * 2 + 1
        if a == m:
            if b == m:
                p += 1
                types[i1] = 1
                types[i2] = 1
            elif b == m - 1:
                q += 1
                types[i1] = 2
                types[i2] = 3
            else:
                r += 1
                types[i1] = 4
        elif b == m:
            if a == m - 1:
                q += 1
                types[i1] = 3
                types[i2] = 2
            else:
                r += 1
                types[i2] = 4
        elif a == m - 1:
            if b == m - 1:
                s += 1
                types[i1] = 5
                types[i2] = 5
            else:
                t += 1
                types[i1] = 6
        elif b == m - 1:
            t += 1
            types[i2] = 6
    # print(f'{p=} {q=} {r=} {s=} {t=}')

    MOD = 998244353
    inv2 = pow(2, MOD - 2, MOD)
    ipow2 = [1]
    for i in range(n * 2):
        ipow2.append(ipow2[-1] * inv2 % MOD)

    facts, finvs = precompute_factorials(n * 2, MOD)
    invs = [0]
    for i in range(1, n * 2 + 1):
        invs.append(finvs[i] * facts[i - 1] % MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    p_ans = 0
    q0_ans = 0
    q1_ans = 0
    r_ans = 0
    s_ans = 0
    t_ans = 0

    for k in range(q + r + 1):
        tmp = invs[p + k] * ipow2[q + r + 1] % MOD
        tmp *= ncr(q + r, k)
        p_ans += tmp
        p_ans %= MOD

    for k in range(q + r):
        tmp = invs[p + k + 1] * ipow2[q + r] % MOD
        tmp *= ncr(q + r - 1, k)
        q0_ans += tmp
        q0_ans %= MOD
        r_ans += tmp
        r_ans %= MOD

    if p == 0:
        for k in range(t + 1):
            tmp = invs[q * 2 + r + s + k] * ipow2[q + r + t] % MOD
            tmp *= ncr(t, k)
            q0_ans += tmp
            q0_ans %= MOD
            q1_ans += tmp
            q1_ans %= MOD
            r_ans += tmp
            r_ans %= MOD

            tmp = invs[q * 2 + r + s + k] * ipow2[q + r + t + 1] % MOD
            tmp *= ncr(t, k)
            s_ans += tmp
            s_ans %= MOD

        for k in range(t):
            tmp = invs[q * 2 + r + s + k + 1] * ipow2[q + r + t] % MOD
            tmp *= ncr(t - 1, k)
            t_ans += tmp
            t_ans %= MOD

    values = [0, p_ans, q0_ans, q1_ans, r_ans, s_ans, t_ans]
    ans = [0] * (n * 2)
    for i in range(n * 2):
        ans[i] = values[types[i]]

    return ans


n = int(input())
pairs = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, pairs)
print(*ans)

G - Random Walk Distance

問題文

正整数 $N$ および整数 $X$ が与えられます。
高橋君が数直線上の座標 $0$ にいます。高橋君はこれから $N$ 回、以下の移動を行います。
- 座標 $x$ にいるとき、座標 $x-1$ または座標 $x+1$ のどちらかを等確率で選び、そこに移動する。
ただし $N$ 回の移動での移動先の選択はすべて独立です。
$N$ 回の移動を全て終えた後の座標を $x'$ とします。$|x'-X|$ の期待値を $\bmod{998244353}$ で求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \leq T \leq 2 \times 10^5$
$1 \leq N \leq 2 \times 10^5$
$|X| \leq 2 \times 10^5$
入力はすべて整数

解法

答えの $2^N$ 倍の値、つまり「$\displaystyle \sum_{x'}$ 高橋君が移動終了後 $x'$ にいるような移動方法の数 $\times |x'-X|$」を求めることにする。

高橋君が $N$ 回移動後に $x'$ にいるような場合の数には、二項係数が現れる。（ただし座標は2つ飛びになる）

... -4 -3 -2 -1  0  1  2  3  4 ...
                 1
              1     1
           1     2     1
        1     3     3     1
     1     4     6     4     1

ここで、$N \le |X|$ ならば（つまり、$X$ が $N$ 回で移動可能な範囲の端または外側にあるなら）、答えは $|X|$ である。距離が（$|X|-1$ になる確率）と（$|X|+1$ になる確率）、（$|X|-2$ になる確率）と（$|X|+2$ になる確率）、、、などが全て等しいので、打ち消しあうことから言える。

内側にある場合、対称性から左半分にある前提としてよい。以下のような値を求めたい。

N=4  X=-1     X
... -4 -3 -2 -1  0  1  2  3  4 ...
              :
     1     4  :  6     4     1    二項係数
 ×  3     1  :  1     3     5    Xからの距離
 -----------------------------
     3  +  4  +  6  + 12  +  5  = 30

つまり、$X$ の左右それぞれにおける

二項係数の総和
二項係数に、公差 $2$ の等差数列をかけたものの総和

の値が分かれば、答えは計算できる。

ところが、「二項係数の $N$ 段目の prefix, suffix の総和」は、 $\binom{N}{0}+\binom{N}{1}+...$ を目的の箇所まで足していく以外に効率的な方法がない。

したがって $T$ 個のテストケースを個別に解くとTLEとなる、のだが、クエリを先読みし、Mo's Algorithm の要領で効率的な順番で答えを求めることで、計算量を削減できる。

特にパスカルの三角形に特化した探索順というものじゃなくても、 2次元グリッドの Mo's Algorithm で解く場合の探索順（Hilbert曲線や、短冊状への分割）と同様の基準を使って問題ない。

また、面白いことに、「二項係数に、公差 $2$ の等差数列をかけたものの総和」は「二項係数の総和」から計算できる。

$\displaystyle f(i,j)=\sum_{k=0}^{j}\binom{i}{k}$ : 二項係数を $0～j$ まで足したもの
$\displaystyle g(i,j)=\sum_{k=0}^{j}2k\binom{i}{k}$ : 二項係数に $k=0～j$ まで $2k$ をかけて足したもの

$j\dbinom{i}{j}=j\dfrac{i!}{j!(i-j)!}=\dfrac{i!}{(j-1)!(i-j)!}=i\dbinom{i-1}{j-1}$ を利用すると、

$\displaystyle g(i,j)=\sum_{k=1}^{j}2i\binom{i-1}{k-1} = 2i \times f(i-1,j-1)$

$g$ を $f$ の式で表せた。ただ、$i$ がズレてると実装の時に混乱しやすいので、$f(i,j)=2f(i-1,j-1)+\dbinom{i-1}{j}$ を利用して変形すると、

$\displaystyle g(i,j)=i \times f(i,j) - (i-j) \binom{i}{j}$

となり、$f(i,j)$ から $g(i,j)$ を求められるので考えやすくなる。

よって、$f(i,j)$ を、パスカルの三角形上を1マス動くたびに適切に更新できれば良くなった。これは、先ほども利用した $f(i,j)=2f(i-1,j-1)+\dbinom{i-1}{j}$ を利用すると、上下方向の移動時も問題なく値を更新できる。

まとめると、

クエリを先読みし、各 $N,X$ から最寄りの二項係数 $(N,j)$ を求める。
Mo's Algorithm の探索順にソートする。
$(0,0)$ から、$f(i,j)$ の値を更新しながら移動する。
クエリ地点に着いたら $g(i,j)$ などを求め、答えを計算する。

以上で、階乗の前計算の元、全体を $O(\max(N) \sqrt{T})$ などで計算できる。