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

AtCoder Beginner Contest 450

E - Fibonacci String

問題文

文字列 $X,Y$ が与えられます。文字列の列 $S_1,S_2,\dots$ を以下で定義します。
- $S_1=X$
- $S_2=Y$
- $i\geq 3$ のとき、$S_i$ は $S_{i-1}$ と $S_{i-2}$ をこの順に連結したもの

各 $i=1,2,\ldots,Q$ について以下の問題に答えてください。
- 問題：整数 $L_i,R_i$ と文字 $C_i$ が与えられる。 $S_{10^{18}}$ の $L_i$ 文字目から $R_i$ 文字目までに文字 $C_i$ が何個含まれるか求めよ。

制約

$X,Y$ は英小文字からなる長さ $1$ 以上 $10^4$ 以下の文字列
$1 \leq Q \leq 10^5$
$1 \leq L_i \leq R_i \leq 10^{18}$
$C_i$ は英小文字
与えられる数値は全て整数

解法

S1  abc
S2  de
S3  deabc
S4  deabcde
S5  deabcdedeabc
...

上例のように、$S_i$（$i \ge 3$）は $S_{i-1}$ をprefix として持つ。

クエリは $10^{18}$ の範囲にしか飛んでこないので、 $S_{10^{18}}$ の代わりに $|S_{i}| \ge 10^{18}$ となるような $S_i$ を考えてよい。
$X,Y$ が1文字でも、$S_{88}$ で長さは $10^{18}$ を超える。

フィボナッチ数列を $F=(F_1,F_2,...)=(0,1,1,2,3,5,8,...)$ とする。

少し実験すると、以下の事実が分かる。

$S_i$（$i \ge 2$）には、$F_i$ 個の $Y$ と、$F_{i-1}$ 個の $X$ が含まれる

                      含まれる個数
                           X    Y   |Si|
S1  abc                   (1)   0    3
S2  de                     0    1    2
S3  deabc                  1    1    5
S4  deabcde                1    2    7
S5  deabcdedeabc           2    3   12
S6  deabcdedeabcdeabcde    3    5   19

関数 $f$ を、$|S_i|$ が $10^{18}$ を超えるような最小の $i$ から再帰的に呼ぶことで求められる。

$f(i,l,r,c):=S_i$ の $[l,r)$ 文字目に含まれる文字 $c$ の個数（0-indexed）

$[l,r) = [0, |S_i|)$ の時
- $S_i$ の全てが対象となる。
- $S_i$ には $F_i$ 個の $Y$ と $F_{i-1}$ 個の $X$ が含まれることを利用して、その場で答えを確定できる。
$r \le |S_{i-1}|$ の時
- $f(i-1,l,r,c)$
$|S_{i-1}| \le l$
- $f(i-1,l-|S_{i-1}|,r-|S_{i-1}|,c)$
その他（$[l,r)$ が $S_{i-1}$ と $S_{i-2}$ の境界を跨ぐ）
- $f(i-1,l,|S_{i-1}|,c)+f(i-2,0,r-|S_{i-1}|,c)$

Python3

def solve(x, y, q, queries):
    fib_len = [len(x), len(y)]
    fib_count = [1, 1]
    while fib_len[-1] <= 10 ** 18:
        fib_len.append(fib_len[-2] + fib_len[-1])
        fib_count.append(fib_count[-2] + fib_count[-1])
    n = len(fib_len)

    x_acc = [[0] * (len(x) + 1) for _ in range(26)]
    y_acc = [[0] * (len(y) + 1) for _ in range(26)]
    for i in range(len(x)):
        c = ord(x[i]) - 97
        for k in range(26):
            if c == k:
                x_acc[k][i + 1] = x_acc[k][i] + 1
            else:
                x_acc[k][i + 1] = x_acc[k][i]
    for i in range(len(y)):
        c = ord(y[i]) - 97
        for k in range(26):
            if c == k:
                y_acc[k][i + 1] = y_acc[k][i] + 1
            else:
                y_acc[k][i + 1] = y_acc[k][i]

    # print(fibonacci)
    # print(len(fibonacci))

    def sub(fi, l, r, c):
        if fi == 0:
            return x_acc[c][r] - x_acc[c][l]
        if fi == 1:
            return y_acc[c][r] - y_acc[c][l]
        if l == 0 and r == fib_len[fi]:
            xc = x_acc[c][-1]
            yc = y_acc[c][-1]
            return fib_count[fi - 2] * xc + fib_count[fi - 1] * yc
        # print(f'{fi=} {l=} {r=} {c=}')
        if r <= fib_len[fi - 1]:
            return sub(fi - 1, l, r, c)
        if l >= fib_len[fi - 1]:
            return sub(fi - 2, l - fib_len[fi - 1], r - fib_len[fi - 1], c)
        res1 = sub(fi - 1, l, fib_len[fi - 1], c)
        res2 = sub(fi - 2, 0, r - fib_len[fi - 1], c)
        return res1 + res2

    buf = []
    for l, r, c in queries:
        l = int(l) - 1
        r = int(r)
        c = ord(c) - 97
        ans = sub(n - 1, l, r, c)
        buf.append(ans)
    return buf


x = input()
y = input()
q = int(input())
queries = [input().split() for _ in range(q)]
ans = solve(x, y, q, queries)
print('\n'.join(map(str, ans)))

F - Strongly Connected 2

問題文

辺と頂点に番号がついた $N$ 頂点 $N-1+M$ 辺の有向グラフがあります。
$1 \leq i \leq M$ に対し辺 $i$ は頂点 $X_i$ から頂点 $Y_i$ への有向辺であり、$1 \leq i \leq N-1$ に対し辺 $M+i$ は頂点 $i+1$ から頂点 $i$ への有向辺です。
辺 $1,2,\dots,M$ のうちいくつか( $0$ 個でもよい) の辺を選ぶ方法は $2^M$ 通りありますが、そのうち選んだ辺を削除したあとのグラフが強連結となるものは何通りありますか。$998244353$ で割った余りを求めてください。

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq M \leq 2\times 10^5$
$1 \leq X_i \lt Y_i \leq N$
入力は全て整数

解法

削除する組の個数を求めるが、裏を返せば採用する組の方を数えるとしても変わらない。

辺は $Y_i$ の昇順でソートしておく（indexも振り直す）。$Y_i$ が同じものについては適当な順でいい。

以下のDPを定義する。

$\mathrm{DP}[i,j]:=i$ 本目の辺まで考慮して、頂点 $j$ がその時点で $1$ から辿り着ける最も大きな頂点であるような、$i$ 本の辺の採用方法の数

$\mathrm{DP}[0,1]=1$ で初期化する。
$i$ 番目の辺が $x→y$ を結ぶとする。以下の遷移・更新が発生する。

$i-1$ までで $x～y$ まで辿り着けていて、辺 $i$ を採用したら、辿り着ける最大頂点は $y$ になる
$i-1$ までで $x～y$ まで辿り着けていて、辺 $i$ を採用しなかったら、辿り着ける最大頂点は変わらない
$i-1$ までで $x$ には辿り着けていないとき、辺 $i$ の採用有無にかかわらず、辿り着ける最大頂点は変わらない

つまり、$\mathrm{DP}[i]=\mathrm{DP}[i-1]$ としたものをベースとして、

$\displaystyle \mathrm{DP}[i,y] += \sum_{j=x}^{y}\mathrm{DP}[i-1,j]$
$1 \le j \lt x$ なる $j$ に対しては、$\mathrm{DP}[i][j] = \mathrm{DP}[i-1][j] \times 2$

という更新が発生する。

                   x              y
          1  2  3  4  5  6  7  8  9
                    `-------------^  辺i
DP[i-1]   1  0  2  5  7  0  1  0  0
                  |                     x 以降の値の総和が y の位置に加算される 
DP[i]     2  0  4 |5  7  0  1  0 13     x より前の値はそれぞれが2倍になる

これは、区間乗算、1点更新、区間和取得ができればよいので、遅延セグメント木で実装できる。
$i$ の次元は省略し、$j$ の次元をセグ木に持たせて破壊的に更新していける。

Python3

from atcoder.lazysegtree import LazySegTree


def solve(n, m, edges):
    in_links = [[] for _ in range(n)]
    for x, y in edges:
        x -= 1
        y -= 1
        in_links[y].append(x)

    MOD = 998244353

    def merge(a, b):
        return (a + b) % MOD

    def mapping(a, b):
        return a * b % MOD

    def composition(a, b):
        return a * b % MOD

    lst = LazySegTree(merge, 0, mapping, composition, 1, n)
    lst.set(0, 1)
    for v in range(1, n):
        tmp = 0
        for u in sorted(in_links[v]):
            tmp += lst.prod(u, v) + tmp
            tmp %= MOD
            lst.apply(0, u, 2)
        lst.set(v, tmp)
    ans = lst.get(n - 1)
    return ans


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

G - Random Subtraction

問題文

長さ $N$ の非負整数列 $A$ が与えられます。
$A$ の要素数が $1$ になるまで、以下の操作を繰り返し行います。
- $1 \leq i,j \leq |A|$ を満たす相異なる $2$ 整数 $i,j$ を一様ランダムに選ぶ。
- $A_i,A_j$ をそれぞれ $a,b$ と置く。
- $A$ から $i$ 番目の要素と $j$ 番目の要素を削除する。
- $A$ の末尾に $a-b$ を追加する。

最終的な $A$ の唯一の要素を $x$ とします。
$x^2$ の期待値を $\mod 998244353$ で求めてください。

制約

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

エスパー解法

実験結果からのエスパー解法が、わりと素直な考察で使えてしまう。（だから配点も若干低めなのかな）
とりあえず、「全ての操作の $x^2$ の総和」を求め、最後に「全ての操作方法の個数」で割って期待値にすることにする。

全ての操作方法の個数は、1回目 $N(N-1)$ 通り、2回目 $(N-1)(N-2)$、、、$N-1$ 回目 $2 \times 1$ の選択肢があり、それぞれ独立なので $N!(N-1)!$ となる。

操作を全探索し、$A=(a,b,c,d,e)$ など、変数に具体的な値を入れないまま多項式として結果の2乗を合計する。
Pythonでは、変数含みの多項式を計算するのは sympy.Symbol 等が使える。

結果、以下のようになる。
表の a^2 とは、各項の2乗が正で答えに寄与するときの係数である。
ab とは、相異なる2数の積が、負で答えに寄与するときの係数である。

N                  a^2      ab   全ての結果のx^2の合計
2  (a,b)              2       4     2*(a^2 + b^2)             -   4*ab
3  (a,b,c)           12       8    12*(a^2 + b^2 + c^2)       -   8*(ab + bc + ca)
4  (a,b,c,d)        144      64   144*(a^2 + b^2 + c^2 + d^2) -  64*(ab+ac+ad+bc+bd+cd)
5  (a,b,c,d,e)     2880     960  2880*(a^2+b^2+c^2+d^2+e^2)   - 960*(...)
6  (a,b,c,d,e,f)  86400   23040 86400*(...)                   -23040*(...)

操作には対称性があるので、変数によらず係数は全て同じとなる。

ここで、a^2 の係数は、$N!(N-1)!$ となっている。

ab の法則を見つけるのが若干難しいが、比を取っていくと、$N \ge 3$ で $\dfrac{4}{3}N!(N-2)!$ となっていることが推察できる。

$\displaystyle X=\sum_{i=1}^{N} A_i^2$、$\displaystyle Y=\sum_{i\neq j}A_iA_j$ とする。これらは $O(N)$ で計算できる。

答えは、$N \ge 3$ の時、$\dfrac{X \times N!(N-1)! - Y \times \frac{4}{3}N!(N-2)!}{N!(N-1)!} = X-Y \times \dfrac{4}{3(N-1)}$ として求められる。

Python3

ちゃんと解く

操作はUnion-Find のようにイメージすることができて、

頂点 $1～N$ がある。
- 始めは全てバラバラであり、各々が根である。
- 頂点は、“符号” という値 $\{+1,-1\}$ を持っていて、始めは全て $+1$ である。
ランダムに2つの根を選び、一方を他方の子とする。
- その際、子となった方の全ての頂点の符号は反転する。

連結成分が1つになるまで操作した後の頂点 $i$ の符号を $c_i$ とすると、$x=\sum_i c_iA_i$ である。
つまり $x$ は、$A_1-A_2+A_3+A_4-A_5+...$ のように、全て係数が $+1$ か $-1$ の、$A$ の線形結合となる。

$\displaystyle x^2 = \sum_{i} A_i^2 + 2\sum_{i \neq j}c_ic_jA_iA_j$ の期待値を考えたい。

$A_i^2$ の方は、2乗すると $c_i$ の影響が消えるため、操作方法によらず定数と見なせる。問題は $c_ic_jA_iA_j$ の方である。

$c_1c_2$ の期待値 $E[c_1c_2]$ がどうなるか考えればよい。操作は対称的なので、他のペアも全て同じ期待値となることから、$\displaystyle 2E[c_1c_2]\sum_{i \neq j}A_iA_j$ のように計算できる。

最初のUnion-Findのイメージにおいて、

頂点1と2の初めて選ばれたタイミングが同じ（2つが同時にはじめて選ばれた）とき、必ず符号が異なり、以降もその関係は変わらない。
- この時 $c_1c_2=-1$ となる
そうでない時、先に選ばれた方の符号が + になるか - になるかの確率は等しく、どちらになってもそれ以降で取れる操作は変わらない
- つまり全体を通して $c_1c_2=1$ となるケースと $c_1c_2=-1$ となるケースは同数となり、期待値において相殺される。

よって「頂点1と2の初めて選ばれたタイミングが同じ」となる操作方法の個数が分かれば、その $-\dfrac{1}{N!(N-1)!}$ 倍が期待値 $E[c_1c_2]$ となる。

$k$ 回目の操作で頂点1と2が同時に選ばれるとすると、

$i=1,...,k-1$ 回目の操作
- ボール1と2以外から選び続ける
- $(N-2)(N-3) \times (N-3)(N-4) \times ... \times (N-k)(N-k-1) = \dfrac{(N-2)!}{(N-k-1)!} \cdot \dfrac{(N-3)!}{(N-k-2)!}$

$k$ 回目の操作:
- ボール1と2から選ぶ。どちらが先になるかで2通り

$k+1$ 回目以降の操作
- 自由。$(N-k)!(N-k-1)!$

これを掛け合わせると、$C(k)=2\cdot (N-2)! \cdot (N-3)! \cdot (N-k)(N-k-1)$

$k=1,...,N-2$ について合計すると以下のように表せる。

$\displaystyle \sum_{k=1}^{N-2}C(k) = 2\cdot (N-2)! \cdot (N-3)! \cdot 2\binom{N}{3}$
参考: ホッケースティック恒等式

これを整理すると、$\dfrac{2}{3}N!(N-2)!$ が現れる。

目次

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

E - Fibonacci String

問題文

制約

解法

F - Strongly Connected 2

問題文

制約

解法

G - Random Subtraction

問題文

制約

エスパー解法

ちゃんと解く