ARC115

SiとSjの回答が食い違っている箇所は $S_{i} \oplus S_{j}$
食い違ってる箇所が偶数なら正解数が一致する可能性があり、奇数なら可能性がない
というわけで各桁についてxorを取って1かどうかを見れば良い: $⨁ (S_{i} \oplus S_{j})$
ここで、xorは結合法則を満たす演算だから順番を変えてもよい: $⨁ (S_{i}) \oplus ⨁ (S_{j})$
これではまだiとjについてループするので10^10回の計算が必要になってしまう
- これをどうするか？
  - →典型的アプローチ頻度表
    - 値の種類KがNよりだいぶ少ないときに使えるテクニック
    - $O (N)$ 払って種類ごとの個数を先に求める
    - そうすると同じ値の組み合わせの計算はまとめて実行可能になるので、 $O (N^{2}) \to O (K^{2})$ となる
- 今回はK=2
- $O (N)$ 払って $⨁ (S_{i})$ が1であるものの個数xを先に求める
  - $\sum_{ij} (⨁ S_{i} \oplus ⨁ S_{j}) = x^{2} (1 \oplus 1) + x (N - x) (1 \oplus 0) + (N - x) x (0 \oplus 1) + (N - x)^{2} (0 \oplus 0) = 2 x (N - x)$
  - これはi, jの大小を区別してないので行列の半分にして答えが求まる python

def main():
    N, M = map(int, input().split())
    s1 = 0
    for i in range(N):
        S = input().strip()
        s = S.count(b"1")
        if s % 2:
            s1 += 1
    print(s1 * (N - s1))

B - Plus Matrix

条件を満たすA, Bが存在するなら $R_{j} = \sum_{i} C_{ij} = \sum_{i} A_{i} + N B_{j}$
$min (R_{j}) = \sum_{i} A_{i} + N min (B_{j})$ だが、 $min (B_{j}) = 0$ として構わない
- $min (B_{j}) = m > 0$ の時、すべてのBからmを引いて、すべてのAにmを足しても結果が変わらないから
というわけで $min (R_{j}) = \sum_{i} A_{i}$ だから、 $B_{j} = (R_{j} - min (R_{j})) / N$ 、 $A_{i} = C_{i 1} - B_{1}$
求めたA, Bで再度Cを求めて、正しく構築できてるか確認する python

def solve(N, CS):
    sums = [sum(row) for row in CS]
    m = min(sums)
    if any((x - m) % N for x in sums):
        return ()

    AS = [(x - m) // N for x in sums]
    BS = [x - AS[0] for x in CS[0]]
    if any(x < 0 for x in BS):
        return ()
    NCS = [tuple(AS[i] + BS[j] for j in range(N)) for i in range(N)]
    if NCS != CS:
        return ()
    return (AS, BS)

C - ℕ Coloring

まず小さい方から考える
- ここまで描いた時点で「ああ、素因数の個数ね」と気づく
証明
- 素因数の個数がK個であるもの同士は互いに約数になることはない
  - だから同じ色で塗って良い
- 素因数の個数がK個であるものは素因数の個数がK未満の約数を必ず1つ以上持つ
  - だからそれらと異なる色でなければならない python

def main():
    N = int(input())
    ret = []
    for i in range(1, N + 1):
        f = get_factors(i)
        x = sum(f.values()) + 1
        ret.append(x)
    print(*ret)

D - Odd Degree

しばらく眺めて「連結成分を求める必要がありそうだな」とは思ったがそこから先がわからないのでまず全探索で解くコードをつくった python

def blute(N,M,edges,edgelist):
    ret = [0] * (N + 1)
    for i in range(2 ** M):
        deg = [0] * N
        for j in range(M):
            if i & (1 << j):
                a, b = edgelist[j]
                deg[a] += 1
                deg[b] += 1
        r = sum(x % 2 for x in deg)
        ret[r] += 1
    return ret

観察してわかったこと
- 連結でない場合はそれぞれを求めて畳み込み
実装
- UnionFindで連結成分の頂点と辺の数を数える
- 逆数・階乗テーブルを作って置いて連結成分ごとに計算
- それぞれを畳み込み
結果TLE
コンテスト後AC
- TLEの原因: 畳み込みの計算にFFTライブラリを使ったこと
  - 素朴なループで畳み込めばACだった py

def solve(N,M,edges,edgelist):
    init_unionfind(N)
    for x, y in edgelist:
        unite(x, y)
    comps = []
    for x in range(N):
        if find_root(x) == x:
            comps.append((num_edges[x], num_vertex[x]))

    MOD = 998_244_353
    comb = CombinationTable(N + 10, MOD).comb

    ret = None
    for e, v in comps:
        xs = [0] * (v + 1)
        xs[0] = 1
        for i in range(1, (v // 2) + 1):
            xs[i * 2] = comb(v, 2 * i)
        if e > v - 1:
            m = pow(2, e - (v - 1), MOD)
            xs = [x * m % MOD for x in xs]
        if ret is None:
            ret = xs
        else:
            ys = ret
            ret = [0] * (len(xs) + len(ys) - 1)
            for i in range(len(xs)):
                for j in range(len(ys)):
                    ret[i + j] += xs[i] * ys[j]
                    ret[i + j] %= MOD
    return ret

🪴 Quartz 4.0

ARC115

Graph View

Backlinks