AtCoder Beginner Contest 469 D,E,F,G問題メモ

AtCoder Beginner Contest 469

D - The Big Two

• $M$ 個の整数のペア $(A_i,B_i)$ が与えられます。$A_i,B_i$ は $1$ 以上 $N$ 以下で、相異なります。
• 以下の条件を満たすような $2$ 整数 $x,y$ の組がいくつあるかを求めてください。
  • $1 \leq x \lt y \leq N$
  • どのペアにおいても、$x$ と $y$ の少なくとも一方はペアに含まれる

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \lt B_i \leq N$
• 入力される値はすべて整数

「$A_1$ か $B_1$ のいずれかは $x$ か $y$ でないといけない」というところから、2通りを試せばよい。

問題中の定義とは異なるが、以下の説明で $x,y$ は単に「ペアの片割れ」を意味するとし、大小関係は特に考慮しないものとする。

仮に $x=A_1$ とする。$x$ が含まれないペアを $(A_{i1},B_{i1}),...,(A_{ik},B_{ik})$ とする。
$y$ の候補は、「これら $k$ 個のペアの全てに共通して出現する値」である必要がある。

ただし、$x$ が含まれないペアが存在しない（全ペアに $x$ が含まれる）場合は、$y$ は $1～N$ のうち $x$ 以外の全ての値を取り得る。

これを $x=B_1$ の場合も試し、合計個数が答えとなる。

ただし、テストケースによっては $(x,y)=(A_1,B_1),(B_1,A_1)$ が重複して数えられる。
この1パターンは、もし存在すれば除かなければならない点に注意。

Python3

def solve(n, m, finalists):
    a, b = finalists[0]
    a_cand = set(range(1, n + 1)) - {a}
    b_cand = set(range(1, n + 1)) - {a, b}
    for i in range(1, m):
        c, d = finalists[i]
        if a != c and a != d:
            a_cand.intersection_update((c, d))
        if b != c and b != d:
            b_cand.intersection_update((c, d))
    ans = len(a_cand) + len(b_cand)
    return ans


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

E - Pro Exam Eligibility

• o と x からなる長さ $N$ の文字列 $S$ が与えられます。
  • ただし、$S$ には o が $K$ 個以上含まれることが保証されます。
• o を $K$ 個以上含む区間の中で、密度の最大値を求めてください。
• 具体的には、
  • 以下の条件を満たすような $2$ 整数 $l,r$ を一つ選びます。
    • $1 \leq l \leq r \leq N$
    • $S$ の $l$ 文字目から $r$ 文字目までで o が $K$ 個以上ある
  • このとき、$\dfrac{区間に含まれる o の個数}{区間長 r-l+1}$ の最大値を求めてください。
• 真の答えとの絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解として扱われます。

• $1 \leq K \leq N \leq 10^6$
• $N$ と $K$ は整数
• $S$ は o と x からなる長さ $N$ の文字列
• $S$ は o を $K$ 個以上含む

x$=0$、o$=1$ と置き換えた上で、「連続部分列の平均値の最大化」に帰着できる。

平均値の最大化は、以下の記事でも紹介されているように典型問題として知られる。 ただ、なかなか知らないと自力では思い浮かびづらい気もする。

• AtCoder ABC 034 D - 食塩水 (1D, 試験管水色) - けんちょんの競プロ精進記録

平均値は「区間内の総和 ÷ 区間の長さ」だが、分子と分母、2つの値が交錯して何が最良かを判断しづらい。

そこで、答え（平均値）を仮決め二分探索する。
以下の2つは同値となる。

• ある区間の平均値が $a$ 以上となる
• ある区間の各要素から $a$ だけ引いたものの総和が $0$ 以上となる

下の方は区間長を考慮しなくてよい。 $a$ を仮決めすることで区間長を式から除外でき、1回の試行を累積和などで効率的に解くことができる。 二分探索で20回ほど繰り返せば、ACできる精度で答えを求めることができる。

$S_l=$o であるとしていい。
$l$ を固定した時、$r$ は「$l$ から数えて $K$ 個目の o 以降」であれば、 「o を $K$ 個以上含む」という制約を満たしている。 各 $l$ に対する最小の $r$ は、$a$ によらず前計算できる。

xを $-a$、oを $1-a$ に置き換えた上で、前から累積和を取り、その後、後ろから「累積和の累積MAX」をとればよい。

Python3

def solve(n, k, s):
    pos = [i for i in range(n) if s[i] == 'o']
    s = [float('xo'.index(c)) for c in s]
    m = len(pos)
    l = 0.
    r = 1.
    for _ in range(25):
        mid = (l + r) / 2
        acc = [0.] * (n + 1)
        for i in range(n):
            acc[i + 1] = acc[i] + s[i] - mid
        bwd_max = [-float('inf')] * (n + 1)
        bwd_max[n] = acc[n]
        for i in range(n, 0, -1):
            bwd_max[i - 1] = max(acc[i - 1], bwd_max[i])
        ok = False
        for i in range(m - k + 1):
            if acc[pos[i]] <= bwd_max[pos[i + k - 1] + 1]:
                ok = True
                break
        if ok:
            l = mid
        else:
            r = mid
    return l


n, k = list(map(int, input().split()))
s = input()
ans = solve(n, k, s)
print(f'{ans:.9f}')

F - GCD Maximum Spanning Tree

• 長さ $N$ の正整数列 $A$ が与えられます。
• $N$ 頂点の重み付き完全無向グラフがあります。各頂点には $1,2,\dots,N$ の番号が付いています。
• $1 \leq i \lt j \leq N$ を満たす $i,j$ について、頂点 $i$ と頂点 $j$ を結ぶ辺の重みは $A_i$ と $A_j$ の最大公約数です。
• このグラフの全域木に含まれる辺の重みの総和としてあり得る値の最大値を求めてください。

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^6$
• 入力される値はすべて整数

愚直に考えると辺数は $O(N^2)$ と多いものの、考慮すべき辺の数をぐっと減らした上でクラスカル法が適用できる。

$M=\max(A)$ とする。$1,2,...,M$ の $M$ 個の箱を用意しておく。
各 $i=1,2,...,N$ につき、$A_i$ の約数の番号の箱全てに、$i$ が書かれたボールを入れていく。

その後、箱を番号が大きい方から調べる。箱 $w$ の中のボール（に対応する頂点）ペアについて、未連結ならコスト $w$ で繋ぐ、ということを全体が連結になるまで繰り返すことで、最大全域木を作れる。

以下の2つは同じである。

• ボール $i$ と $j$ が同じ箱 $w$ に入っている
• $A_i$ と $A_j$ は $w$ を公約数として持つ

同じ箱に入っているからと言って「最大」公約数とは限らないが、 そのような2頂点は最大公約数の時点で既に結ばれているはずなので、誤ったコストで結んでしまうことはない。

連結操作を行う回数は、ボールの個数に比例する。
$10^6$ 以下の整数の約数の個数の最大値は $240$ 個。 しかも $A_i$ は互いに相異なるため、全体ではもっと少ない値が大半を占める。 $A_i$ 全体を通しての約数の総数（ボールの総数）はそこまで大きくならず、全列挙しても制限時間内に処理できる規模だと見積もれる。

なお、$\max(A)$ がメモリに乗る程度の場合の素因数分解・約数列挙は、 SPF（Smallest Prime Factor）を使うことで、$\sqrt{A_i}$ までの試し割りよりも高速におこなえる。

• 複数のクエリの素因数分解を高速に処理する #C++ - Qiita

Python3

from atcoder.dsu import DSU


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_divisors(factors):
    div = [1]
    for p, c in factors:
        pows = [pow(p, i + 1) for i in range(c)]
        for i in range(len(div)):
            d = div[i]
            for k in pows:
                div.append(d * k)
    return div


def solve(n, aaa):
    ma = max(aaa)
    spf = get_spf(ma)

    divisors = [[] for _ in range(ma + 1)]

    for i in range(n):
        a = aaa[i]
        pf = prime_factorize(a, spf)
        for d in get_divisors(pf):
            divisors[d].append(i)

    dsu = DSU(n)
    count = 0
    ans = 0
    for d in range(ma // 2, 1, -1):
        if len(divisors[d]) <= 1:
            continue
        leaders = set(dsu.leader(a) for a in divisors[d])
        if len(leaders) <= 1:
            continue
        x = leaders.pop()
        for y in leaders:
            dsu.merge(x, y)
            count += 1
            ans += d

    ans += n - 1 - count

    return ans


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

G - K-nacci Operations

• a, b からなる $K$ 個の文字列 $S_1, S_2, \ldots, S_K$ が与えられます。
• また、$i \gt K$ なる整数 $i$ に対し、文字列 $S_i$ を $S_{i-1}, S_{i-2}, \ldots, S_{i-K}$ をこの順に連結した文字列として定めます。
• あなたは、文字列 $T$ に対して以下の操作を行います。
  • $|S_N|$ を $S_N$ の長さとして、$j = 1, 2, \ldots, |S_N|$ に対し以下の操作を順に行う。
    • $S_N$ の $j$ 文字目が a のとき、$T$ の先頭の文字を末尾に移動させる。
    • $S_N$ の $j$ 文字目が b のとき、$T$ 全体を反転させる。すなわち、$T$ の文字の並びを逆にする。
• 一連の操作を終えた後の文字列 $T$ を求めてください。

• $2 \leq K \leq 100$
• $K$ は整数
• $S_i$ は a, b からなる空でない文字列 $(1 \leq i \leq K)$
• $S_1, S_2, \ldots, S_K$ の長さの和は $2 \times 10^5$ 以下
• $1 \leq N \leq 10^{18}$
• $N$ は整数
• $T$ は英小文字からなる長さ $1$ 以上 $2 \times 10^5$ 以下の文字列

制約メタ読みで行列累乗っぽいことは分かっても、タネとなる行列をどう設定すればよいのか？が難しい。

まず、文字列の表す操作を簡単な2つの値に置き換える。 操作は $S$ がどれだけ長くなっても「反転の有無 $a$（$0/1$）」と 「シフト回数 $b$（$0～|T|-1$）」の組 $(a,b)$ で表現できる。

• $(a,b)$ が表す操作:
  • $b$ 回、先頭の文字を末尾に移動させたあと、$a=1$ なら反転させる（$a=0$ ならそのまま）

操作の合成、つまり $(a_1,b_1)$ の後に $(a_2,b_2)$ を行う場合、合成された操作は、以下のように求められる。

• $a_1=0$ の場合、$(a_1 \oplus a_2, b_1+b_2)$
• $a_1=1$ の場合、$(a_1 \oplus a_2, b_1-b_2)$
• 言い換えると、$(a_1 \oplus a_2, b_1 + (-1)^{a_1}b_2)$

以下、特に明記がなくても、$a_i$ は $\bmod{2}$、$b_i$ は $\bmod{|T|}$ の世界で考える。

まず、$a$ の方は、単独で加算されていくのみである。以下の2つの差分を考えると、

• $a_i = a_{i-1} \oplus a_{i-2} \oplus ... \oplus a_{i-K}$
• $a_{i-1} = a_{i-2} \oplus a_{i-3} \oplus ... \oplus a_{i-K-1}$

これより、$a_i=a_{i-K-1}$ となり、「$a_i$ は $K+1$ の周期を持つ」ことがわかる。

K=3
a   0  0  1
b   1  2  0
        ↓               この後を求めていくと、a は K+1=4 周期で繰り返される
a   0  0  1  1  0  0  1  1  0  0  1  1 ...
b   1  2  0 -3  ?  ?  ?  ?  ?  ?  ?  ? ...

一方、$b_i$ の方を求めるには、$b_{i-1},...,b_{i-K}$ に加え 遡っていく方向に累積和を取った $a_{i-1},...,a_{i-K}$ の値も重要となる。

i   1  2  3  4  5
a   0  0  1  1  0  ┌   (-1)^(0)     * b4
b   1  2  0 -3  ^─┼ + (-1)^(a4)    * b3
                   └ + (-1)^(a4+a3) * b2
                   -----------------------
                                       b5

$b_5$ を求める時に、$b_2,b_3,b_4$ それぞれにかける係数を、$c_{5,2},c_{5,3},c_{5,4}$ のように表す。
$b_5=c_{5,2}b_2+c_{5,3}b_3+c_{5,4}b_4$ という線形結合の形で表せる。

1つ進めて $b_6=c_{6,3}b_3+c_{6,4}b_4+c_{6,5}b_5$ だが、この $b_5$ に上記を代入すると、これも $b_2,b_3,b_4$ の線形結合で表せる。
同様に、$b_7,b_8$ も $b_2～b_4$ の線形結合の形で表せることもわかる。

また、ここで $a_i$ が周期 $K+1$ を持つという事実が役に立つ。$c$ は $a$ に依存して決定されるので、

• $b_5$ を求める時に、$b_2,b_3,b_4$ それぞれにかける係数 $c_{5,2},c_{5,3},c_{5,4}$
• $b_9$ を求める時に、$b_6,b_7,b_8$ それぞれにかける係数 $c_{9,6},c_{9,7},c_{9,8}$
• $b_{13}$ を求める時に、$b_{10},b_{11},b_{12}$ それぞれにかける係数 $c_{13,10},c_{13,11},c_{13,12}$
• :

これらは縦に並んだもの同士、全て同じになる。（例）$c_{5,2}=c_{9,6}=c_{13,10}$
さらに進めて、「$b_2～b_4$ の線形結合で $b_5～b_8$ を作る時のそれぞれの係数」と「$b_6～b_8$ の線形結合で $b_9～b_{12}$ を作る時のそれぞれの係数」は、 計算処理の内容が全く同じなので、一致する。

よって、$(b_1,b_2,b_3,b_4)^T$ に乗じることで $(b_5,b_6,b_7,b_8)^T$ を求める行列を $A$ とすると、

\[ A \begin{pmatrix} b_1\\ \vdots\\ b_4 \end{pmatrix} = \begin{pmatrix} b_5\\ \vdots\\ b_8 \end{pmatrix} \]

$A$ をさらに乗じていくと $(b_9,...,b_{12})^T,(b_{13},...,b_{16})^T,...$ のように $K+1$ 周期で $b$ を先に進めることができる。

この $A$ をまず愚直に求め、$\left \lfloor \dfrac{N-1}{K+1} \right \rfloor$ だけ累乗し、$(b_1,...,b_{K+1})^T$ に乗じた後、必要な $b_N$ を読み取ればよい。

$A$ を求めるのに $O(K^3)$、累乗に $O(K^3 \log{N})$ の計算量がかかり、十分高速に動作する。

Python3

def mul_mat(aaa, bbb, mod):
    n = len(aaa)
    m = len(aaa[0])
    assert len(bbb) == m
    l = len(bbb[0])
    result = [[0] * l for _ in range(n)]
    for i in range(n):
        for k in range(l):
            for j in range(m):
                result[i][k] += aaa[i][j] * bbb[j][k]
                result[i][k] %= mod
    return result


def pow_mat(aaa, exp, mod):
    n = len(aaa)
    assert len(aaa[0]) == n
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        result[i][i] = 1
    while exp:
        if (exp & 1) == 1:
            result = mul_mat(result, aaa, mod)
        exp >>= 1
        if exp > 0:
            aaa = mul_mat(aaa, aaa, mod)
    return result


def solve(k, sss, n, t):
    m = len(t)
    l = k + 1

    aaa = []
    bbb = []
    for s in sss:
        rev = 0
        sft = 0
        for c in s:
            if c == 'a':
                if rev == 0:
                    sft += 1
                else:
                    sft -= 1
            else:
                rev ^= 1
        aaa.append(rev)
        bbb.append(sft % m)

    k1a = 0
    k1b = 0
    for i in range(k - 1, -1, -1):
        if k1a == 0:
            k1b += bbb[i]
        else:
            k1b -= bbb[i]
        k1a ^= aaa[i]
    aaa.append(k1a)
    bbb.append(k1b % m)

    mat = [[0] * l for _ in range(l)]
    for i in range(l):
        mat[i][i] = 1
    for i in range(l):
        row = [0] * l
        for j in range(l):
            sgn = 1
            for _k in range(1, l):
                row[j] += sgn * mat[-_k][j]
                if aaa[i - _k] == 1:
                    sgn *= -1
            row[j] %= m
        mat.append(row)
    mat = mat[l:]

    d, rem = divmod(n - 1, l)
    mat = pow_mat(mat, d, m)
    b = sum(bbb[i] * mat[rem][i] % m for i in range(l)) % m
    a = aaa[rem]
    if b < 0:
        b += m

    ans = (t + t)[b:b + m]
    if a == 1:
        ans = ans[::-1]
    return ans


k = int(input())
sss = [input() for _ in range(k)]
n = int(input())
t = input()
ans = solve(k, sss, n, t)
print(ans)