AtCoder Regular Contest 115 A,D,E問題メモ

「おっ、そういえば今日は開始が1時間早いんやったか。うっかりして10分遅刻やけどまぁええやろ！」で参加したら怒濤の速解き回でエラい目に遭った。

A - Two Choices

問題

$N$ 人が、0,1の2択で解答する $M$ 問からなるテストを受ける
$i$ 番目の人の解答は $S_i$ で与えられる
2人ペア $\dfrac{N(N-1)}{2}$ 個のうち、以下の条件を満たすものの個数を求めよ
- 正答をどのように決めても、絶対に2人の正解の数が同じにならない
$2 \le N \le 10^5$
$1 \le M \le 20$

解法

正答を都合よく決めていいので、わりと正解数は近づけられる。

人 $i$ と $j$ について、2人の解答が一致する箇所で正解数に差はつけられない。
異なる箇所で差がつくが、これは正答をどう決めても1問あたり「1人が正解、1人が不正解」なので、異なる箇所数が偶数個の時に一致させることができ、奇数個の時に一致させるのが不可能となる。

               0010011  正解数が等しくなる正答の例
i 0011010  →  oooxoox
j 1010111  →  xoooxoo

しかし全てのペアを調べるとTLEとなる。

ある問題の解答が2人で異なるとは、2人のその問題に対する解答 $(0,0),(0,1),(1,0),(1,1)$ の4通りのうち、$(0,1)$ か $(1,0)$ になった時である。
これが偶数個なら正解数を同じにできるので、結局、2人の'1'の合計が偶数個なら正解数を同じにでき、奇数個なら不可能となる。

そして、これは各 $S_i$ についてそれぞれ単独で「'1' が偶数個あるか奇数個あるか」を求めておけば、奇数個から1人と偶数個から1人の組み合わせの数が答えとなる。

Python3

n, m = map(int, input().split())
odd = 0
even = 0
for _ in range(n):
    if input().count('1') % 2 == 0:
        even += 1
    else:
        odd += 1
print(even * odd)

D - Odd Degree

問題

$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられる
- 辺 $i$ は $a_i$ と $b_i$ を結ぶ
$G$ から0本以上の辺を選び、他の辺を削除したグラフ（全域部分グラフ）は $2^M$ 通りある
$k=0～N$ それぞれについて、「次数が奇数となる頂点がちょうど $k$ 個の全域部分グラフ」の個数を $\mod{998244353}$ で求めよ
$1 \le N \le 5000$
$0 \le M \le 5000$

解法

サイクル基底あたりのワードを知っていればひらめきやすかったか。

まず、$k$ が奇数の時は0になる。
1本の辺は2頂点の次数を1ずつ上げるので、頂点全体の次数の総和は偶数となる。「次数が奇数となる頂点が奇数個ある」ことは絶対にない。

また、$G$ で異なる連結成分に属する頂点・辺は互いに影響しないので、連結成分毎に考える。

$k=0$ の時

サイクル基底と呼ばれる概念があり、それを使えば簡単に求められる。

以下、「全ての頂点の次数が偶数であるグラフ」を「偶グラフ」と呼ぶことにする。

ある $n$ 頂点 $m$ 辺の単純連結無向グラフが与えられたときに、偶グラフとなるような全域部分グラフは何通りあるか?

$n-1$ 本の辺を使って適当な全域木を作り、そこに含まれない辺を1本追加した時、閉路がちょうど1つできる。
含まれない辺は $m-n+1$ 本あるので、 $m-n+1$ 個の相異なる閉路ができる。

この時、この $m-n+1$ 個の閉路集合が「サイクル基底」となる。
はじめの全域木の取り方により複数考えられるが、どれでもよい。

「基底ベクトル」という概念があるが、これは「基底ベクトルを合成すれば、与えられたベクトル空間のあらゆるベクトルを作ることができるし、あるベクトルを基底ベクトルだけで表現する方法は一意に決まる」ようなベクトル集合を指す。たとえば2次元空間の基底ベクトルの一例は $(0,1)$ と $(1,0)$ である。

基底_(線型代数学)

サイクル基底も同じように、サイクルが1個だけあるグラフというのは必然的に偶グラフだが、「これらの偶グラフを合成すれば、他のあらゆる偶グラフを作ることができ、その表現方法も一意に決まる」ような集合である。（必ずしも結果が連結となるとは限らないため、「サイクル」と言ってしまうとちょっと不正確になる）

ただしグラフの合成とは、辺のXORの操作を指すとする。

サイクル基底・サイクルの個数について - 競プロ練習記録

つまり、偶グラフは $2^{m-n+1}$ 個、存在する。

例えばこのサイクル基底の性質として、グラフ上のある $s→t$ パスを考えたときに、そこに基底サイクルをXORしたものもまた、$s→t$ パスとなるなどがある。

ｓ==○==○==ｔ  →  ｓ==○--○==ｔ
    ｜  ｜              ||  ||
    ○--○              ○==○

$k \ge 2$ の時

$k$ を固定して、次数を奇数としたい頂点集合を決め打つことを考えると、その選び方は ${}_nC_k$。
しかし、1つの頂点集合に複数の実現方法があったりして、辺の選び方を具体的に数えようとすると手に負えない。

①--②--③--④    ①⑥を奇次数の頂点としたい場合、
｜  ｜／｜        採用する辺は ①-②-⑥、①-⑤-⑥、①-②-③-⑥ などがあり、
⑤--⑥  ⑦        また①-⑤-⑥の場合に限り、②-③-⑥の閉路を追加してもよい

                  ①②③⑥を奇次数としたい場合、
                  (①-⑤-⑥, ②-③) としてもよいし、
                  (①-②, ③-⑥) としてもよく、ペアの作り方も様々ある。

ここで、サイクル基底の時にも出てきた辺のXORの考え方が使える。

ある頂点集合について、条件が満たされている状態を1つ構築できれば、後はそこに偶グラフをXORしたものもまた、異なる辺の選び方として条件を満たすことがいえる。（XORによって、各頂点の次数の偶奇は変わらない）

また逆に、もし奇次数となる頂点集合が同じような、相異なる2つの辺の選び方がある場合、その選び方同士のXORは必ず偶グラフとなり、サイクル基底から作れる $2^{m-n+1}$ 個に含まれているはずである。

つまり、ある奇次数としたい頂点集合を1つ決めて、それを実現する方法を1つ見つけることができれば、具体的な辺の選び方を求めずとも、実現方法は $2^{m-n+1}$ 通りあることがわかる。

で、ある頂点集合が実現できるかだが、これは必ず実現できる。

方法の一例を示すと、元のグラフから適当な全域木を作り、適当に根を決める。各頂点、「自身を含めた自身以下の部分木で、頂点集合に含まれる頂点が奇数個なら、親との辺を採用する」ことを繰り返していくと、解の1つが得られる。

よって、$n$ 頂点 $m$ 辺の連結成分について、奇次数の頂点が $d$ 個あるようなものは、${}_nC_d 2^{m-n+1}$ 個あることになり、1つの連結成分について答えが求まる。

後は、各連結成分についてこれをたたみ込めばよい。FFTなど使わなくても制約が小さいので愚直に $O(N^2)$ で通る。

サイクル基底の概念を使わなくても、以下の考え方でもアプローチできたかも。いずれにしろ、全域木がポイント。

全域木を取り、奇次数となる頂点集合を決めると、辺の採用方法は一意に決まる
全域木に含まれない辺を1本ずつ追加していくと、全域木とその1本によってできる閉路の採用状態をまるっと反転させても各頂点の次数の偶奇は不変
つまり1個追加する毎にパターンが倍々になる

Python3

import os
import sys

import numpy as np


def solve(inp):
    UNION_FIND_TABLES = []
    UNION_FIND_EDGES = []

    def union_find_init(n):
        UNION_FIND_TABLES.append(np.full(n, -1, np.int64))
        UNION_FIND_EDGES.append(np.zeros(n, np.int64))
        return len(UNION_FIND_TABLES) - 1

    def union_find_root(ins, x):
        stack = []
        table = UNION_FIND_TABLES[ins]
        while table[x] >= 0:
            stack.append(x)
            x = table[x]
        for y in stack:
            table[y] = x
        return x

    def union_find_unite(ins, x, y):
        table = UNION_FIND_TABLES[ins]
        edges = UNION_FIND_EDGES[ins]
        r1 = union_find_root(ins, x)
        r2 = union_find_root(ins, y)
        if r1 == r2:
            edges[r1] += 1
            return
        d1 = table[r1]
        d2 = table[r2]
        if d1 <= d2:
            table[r2] = r1
            table[r1] += d2
            edges[r1] += edges[r2] + 1
        else:
            table[r1] = r2
            table[r2] += d1
            edges[r2] += edges[r1] + 1

    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:
            if n & 1:
                r = (r * y) % m
            y = y * y % m
            n >>= 1
        return r

    def get_primitive_root(m):
        if m == 2: return 1
        if m == 167772161: return 3
        if m == 469762049: return 3
        if m == 754974721: return 11
        if m == 998244353: return 3
        divs = [2]
        x = (m - 1) // 2
        while x & 1 == 0:
            x >>= 1
        i = 3
        while i * i <= x:
            if x % i == 0:
                divs.append(i)
                x //= i
                while x % i == 0:
                    x //= i
            i += 2
        if x > 1:
            divs.append(x)
        g = 2
        while True:
            ok = True
            for d in divs:
                if pow_mod(g, (m - 1) // d, m) == 1:
                    ok = False
                    break
            if ok:
                return g

    def butterfly_prepare(mod, primitive_root):
        sum_e = np.zeros(30, np.int64)
        sum_ie = np.zeros(30, np.int64)
        es = np.zeros(30, np.int64)
        ies = np.zeros(30, np.int64)
        cnt2 = bit_scan_forward(mod - 1)
        e = pow_mod(primitive_root, (mod - 1) >> cnt2, mod)
        ie = pow_mod(e, mod - 2, mod)
        for i in range(cnt2, 1, -1):
            es[i - 2] = e
            ies[i - 2] = ie
            e = e * e % mod
            ie = ie * ie % mod
        now_e = 1
        now_ie = 1
        for i in range(cnt2 - 1):
            sum_e[i] = es[i] * now_e % mod
            sum_ie[i] = ies[i] * now_ie % mod
            now_e = now_e * ies[i] % mod
            now_ie = now_ie * es[i] % mod
        return sum_e, sum_ie

    def butterfly(aaa, mod, sum_e):
        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, mod, sum_ie):
        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

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

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = pow_mod(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    MOD = 998244353
    n = inp[0]
    m = inp[1]
    uft = union_find_init(n)
    for i in range(m):
        a = inp[2 * i + 2] - 1
        b = inp[2 * i + 3] - 1
        union_find_unite(uft, a, b)

    facts, finvs = prepare_factorials(n, MOD)

    conv = np.ones(1, np.int64)
    table = UNION_FIND_TABLES[uft]
    edges = UNION_FIND_EDGES[uft]
    for i in range(n):
        if table[i] >= 0:
            continue
        x = -table[i]
        y = edges[i]
        cycles = pow_mod(2, y - x + 1, MOD)
        conv2 = np.zeros(x // 2 + 1, np.int64)
        for j in range(0, x + 1, 2):
            conv2[j // 2] = facts[x] * finvs[j] % MOD * finvs[x - j] % MOD
        conv2 = conv2 * cycles % MOD
        conv = convolution(conv, conv2, MOD)

    ans = np.zeros(n + 1, np.int64)
    ans[:2 * conv.size:2] = conv

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

E - LEQ and NEQ

問題

長さ $N$ の数列 $A_1,A_2,...,A_N$ が与えられる
次の条件をいずれも満たす数列 $X_1,X_2,...,X_N$ の個数を $\mod{998244353}$ で求めよ
条件
- $1 \le X_i \le A_i$（各要素は $1$ 以上 $A_i$ 以下）
- $X_i \neq X_{i+1}$（隣り合う2項は同じにならない）
$2 \le N \le 5 \times 10^5$
$1 \le A_i \le 10^9$

解法

問題設定はシンプルだが。。。

包除で考える。

愚直なDP

まず愚直なDPを考える。素案なので $DP_0$ としておく。

$DP_0[i][k]=i$ 番目の要素までを考えたとき、「確実に」$X_i=X_{i+1}$ となってしまう要素が $k$ 個の時の数列の個数

包除原理を使う時によく出てくる考え方だが、「確実」な $k$ 個以外の箇所は同じでも同じで無くてもよい。

初期状態は $DP_0[0][0]=1$ として、どのような形になるかだけ示すと、次のようになる。

i    0   1   2   3   4   5   6
Ai       2   3   2   4   1   3

DP
k=0  1   2   6  12  48  48 144
k=1  0   0   2   8  44  56 216
k=2  0   0   0   2  16  30 146
k=3  0   0   0   0   2   8  54
k=4  0   0   0   0   0   1  11
k=5  0   0   0   0   0   0   1

こうした時、包除原理より、右端の $144-216+146-54+11-1=30$ が答えとなる。

遷移に際して注意が必要なのは、例えば $X_i=X_{i+1}=...=X_{j}$ のように一致してしまう場所が連続する場合、$X_i$ が取れる最大値は $A_i～A_j$ の最小値まで。このために各2項間について個別に考えてよいわけでは無く、同じになる箇所がどこからどこまで連続するか、気にする必要がある。

例えば上記で $i=3$ の時を考える。

$k=0$ の時、$DP_0[2][0]$ から次の数字を $1～3$ で好きに選んでよいので、$3 \times DP_0[2][0]$。

$k=1$ の時、同様に $DP_0[2][1]$ から次の数字を選ぶのに加え、$X_2=X_3$ とする選択肢が採れる。
その場合、$X_1$ までを同じ箇所が無いように選んで（$DP[1][0]$）、そこから $X_2,X_3$ は $\min(A_2,A_3)$ である $2$ 通りの決め方がある。
あわせて $3 \times DP_0[2][1] + 2 \times DP_0[1][0]$。

$k=2$ の時、さらに $X_1=X_2=X_3$ の選択肢が採れる。
同様にして $3 \times DP_0[2][2] + 2 \times DP_0[1][1] + 2 \times DP_0[0][0]$。

こうして、各 $DP_0[i][k]$ の更新は、$DP_0[i-1][k]$ からナナメ左上に並ぶ要素（$DP_0[i-2][k-1],DP_0[i-3][k-2],...$）が遷移元となる。
$DP_0[j][l]$ を遷移元とする場合、それが寄与するのは $\min(A_{j+1},A_{j+2},...,A_{i}) \times DP_0[j][l]$ となる。

このままでは、$DP_0[i][k]$ を求めるのに $k$ 箇所からの遷移が必要となり、minも求めないといけないので、全体で $O(N^3)$ となってしまう。

偶奇をまとめる

最終的に包除原理を適用するためのDPでは、$k=偶数$ の要素から $k=奇数$ の要素を引けばよいため、遷移次第で偶奇でまとめられることがある。
今回の場合も当てはまる。

たとえば $k=偶数$ のとき、

$DP_0[i-1][k=偶数]$ の要素 $\times A_i$
$DP_0[i-2][k=奇数]$ の要素 $\times \min(A_{i-1}, A_i)$
$DP_0[i-3][k=偶数]$ の要素 $\times \min(A_{i-2}, A_{i-1}, A_i)$
…

となっていく。$k=奇数$ の時も同様なので、偶奇でまとめられたDPでも遷移は変わりなくできることがわかる。

$DP[i][k:0/1]=i$ 番目の要素までを考えたとき、確実に $X_i=X_{i+1}$ となってしまう要素の $\mod{2}$ が $k$ 個の時の数列の個数

これで計算量は $O(N^2)$ になった。が、まだ多い。

累積和もまとする

上記までは遷移先の $i$ を固定してその $i$ を更新するために必要な遷移元を見ていたが、更新の仕方を工夫すると、同じ値を連続した区間に足し込む操作とすることができ、imos法の累積和が使える。

$i$ の昇順に、$A_i$ が区間minとなる範囲（$A_i=\min(A_l,...,A_i,...,A_r)$ となる $l,r$）をまとめて更新する。

まず、各 $A_i$ が、自身を含む区間で最小となる左端 $l_i$ と右端 $r_i$ を求めておく。
（stackを使えば、事前に求めなくても $i$ をイテレートしながら求められるらしいが、まぁ最初に求めても問題ない）

この時、同じ値を含む場合は適当に順位付けしておく。（昇順sortした時に偶然そうなった順などでよく、特にどれを先にするか気にする必要は無い）

i    0   1   2   3   4   5   6    便宜的にA1>A3とする
Ai       2   3   2   4   1   3

li       1   2   1   4   1   6
ri       2   2   4   4   6   6

$A_i$ についての更新時、「$i-1～l_i-1$ をジグザグにたどった箇所」の和× $A_i$ の値をもって、「$i～r_i-1$ をジグザグにたどった箇所」に加算する。

     li-1            i-1   i             ri-1
k=0   ○  ... ○  □  ○   ●  ■  ● ... ■
k=1   □  ... □  ○  □   ■  ●  ■ ... ●

○の和 × $A_i$ を、●のそれぞれに加算
□の和 × $A_i$ を、■のそれぞれに加算

この方法も、愚直にやると全体で $O(N^2)$ は変わらないものの、同じ値を加算する操作に言い換えられたので

○について、既に計算済みのDPのジグザグの累積和
●について、範囲加算はimos法に置き換える

のように計算することで、$O(N)$ に落とせる。
以下のようにする。

○の区間和を取得
$A_i$ を乗じて、●に加算する値 $x$ を確定
$DP[i]$ に $x$ を加算、$DP[r_i]$ に減算することで、imos法による区間加算を表現
$DP[i]$ が確定（もう $DP[i]$ に遷移してくるパターンは挙げ終わった）
- ●のimos法は、$i-1$ までは累積和を取り終えており、$i$ 以降は足し込みはしたがまだ累積和を取っての復元が終了していない状態
- →$i$ について、累積和を取って復元
- ○の累積和を、$i$ について更新

Python3

import sys
from operator import itemgetter

n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353

# 自身より小さい値が出てくる最も近いindex
lll = [0] * (n + 1)
rrr = [0] * (n + 1)
left = list(range(-1, n + 1))
right = list(range(1, n + 3))
for i, a in sorted(enumerate(aaa), key=itemgetter(1), reverse=True):
    l = left[i]
    r = right[i]
    lll[i] = l
    rrr[i] = r
    left[r] = l
    right[l] = r

dp1 = [[0] * (n + 5), [0] * (n + 5)]
dp2 = [[0] * (n + 5), [0] * (n + 5)]
dp2[0][0] = 1

for i, a in enumerate(aaa):
    l = lll[i]
    r = rrr[i]
    i0 = (i - 0) // 2 * 2
    i1 = (i - 1) // 2 * 2 + 1
    l0 = (l - 0) // 2 * 2
    l1 = (l - 1) // 2 * 2 + 1
    r0 = (r + 2) // 2 * 2
    r1 = (r + 1) // 2 * 2 + 1

    tmp00 = dp2[0][i0] - dp2[0][l0]
    tmp01 = dp2[0][i1] - dp2[0][l1]
    tmp10 = dp2[1][i0] - dp2[1][l0]
    tmp11 = dp2[1][i1] - dp2[1][l1]
    tmp0 = (tmp01 + tmp10) * a % MOD
    tmp1 = (tmp00 + tmp11) * a % MOD
    dp1[0][i0 + 2] += tmp0
    dp1[0][r0] -= tmp0
    dp1[0][i1 + 2] += tmp1
    dp1[0][r1] -= tmp1
    dp1[1][i0 + 2] += tmp1
    dp1[1][r0] -= tmp1
    dp1[1][i1 + 2] += tmp0
    dp1[1][r1] -= tmp0
    dp1[0][i + 1] = (dp1[0][i + 1] + dp1[0][i - 1]) % MOD
    dp1[1][i + 1] = (dp1[1][i + 1] + dp1[1][i - 1]) % MOD
    dp2[0][i + 1] = (dp1[0][i + 1] + dp2[0][i - 1]) % MOD
    dp2[1][i + 1] = (dp1[1][i + 1] + dp2[1][i - 1]) % MOD

ans = (dp1[0][n] - dp1[1][n]) % MOD
print(ans)

目次

AtCoder Regular Contest 115 A,D,E問題メモ

A - Two Choices

問題

解法

D - Odd Degree

問題

解法

$k=0$ の時

$k \ge 2$ の時

E - LEQ and NEQ

問題

解法

愚直なDP

偶奇をまとめる

累積和もまとする