ARC115
https://gyazo.com/b8d7fb3553b8ace653c7aceddae22b35
A - Two Choices
https://gyazo.com/212f28de9c9de61956362931745f2ad3
SiとSjの回答が食い違っている箇所は$ S_i \oplus S_j
食い違ってる箇所が偶数なら正解数が一致する可能性があり、奇数なら可能性がない
というわけで各桁についてxorを取って1かどうかを見れば良い: $ \bigoplus (S_i \oplus S_j)
ここで、xorは結合法則を満たす演算だから順番を変えてもよい: $ \bigoplus (S_i) \oplus \bigoplus (S_j)
これではまだiとjについてループするので10^10回の計算が必要になってしまう
これをどうするか？
→典型的アプローチ頻度表
値の種類KがNよりだいぶ少ないときに使えるテクニック
$ O(N) 払って種類ごとの個数を先に求める
そうすると同じ値の組み合わせの計算はまとめて実行可能になるので、$ O(N^2) \to O(K^2)となる
今回はK=2
$ O(N) 払って$ \bigoplus (S_i) が1であるものの個数xを先に求める
$ \sum_{ij} \left(\bigoplus S_i\oplus \bigoplus S_j\right) = x^2(1 \oplus 1) + x(N-x)(1 \oplus 0) + (N-x)x(0 \oplus 1) + (N-x)^2(0 \oplus 0) = 2x(N-x)
これはi, jの大小を区別してないので行列の半分にして答えが求まる
code: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
https://gyazo.com/a694c4a33447bb3a70860025f720bf3f
条件を満たすA, Bが存在するなら $ R_j = \sum_i C_{ij} = \sum_i A_i + NB_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_{i1} - B_1
求めたA, Bで再度Cを求めて、正しく構築できてるか確認する
code: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 - AS0 for x in CS0]
if any(x < 0 for x in BS):
return ()
NCS = [tuple(ASi + BSj for j in range(N)) for i in range(N)]
if NCS != CS:
return ()
return (AS, BS)
C - ℕ Coloring
https://gyazo.com/286922e95294477de92fa09d8e95ba10
まず小さい方から考える
https://gyazo.com/7cd9acefc328bf0af985f0ba690b1463
ここまで描いた時点で「ああ、素因数の個数ね」と気づく
証明
素因数の個数がK個であるもの同士は互いに約数になることはない
だから同じ色で塗って良い
素因数の個数がK個であるものは素因数の個数がK未満の約数を必ず1つ以上持つ
だからそれらと異なる色でなければならない
code: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
https://gyazo.com/bb3e3f994e962d2cb44889a9428d5ff3
しばらく眺めて「連結成分を求める必要がありそうだな」とは思ったがそこから先がわからないのでまず全探索で解くコードをつくった
code: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 = edgelistj
dega += 1
degb += 1
r = sum(x % 2 for x in deg)
retr += 1
return ret
観察してわかったこと
https://gyazo.com/c07f96ce39dd2afdbcf7bda1862bf1e9
https://gyazo.com/36e9f877df3d307abe3561d27a346dcd
連結でない場合はそれぞれを求めて畳み込み
実装
UnionFindで連結成分の頂点と辺の数を数える
逆数・階乗テーブルを作って置いて連結成分ごとに計算
それぞれを畳み込み
結果TLE
コンテスト後AC
TLEの原因: 畳み込みの計算にFFTライブラリを使ったこと
素朴なループで畳み込めばACだった
code: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_edgesx, num_vertexx))
MOD = 998_244_353
comb = CombinationTable(N + 10, MOD).comb
ret = None
for e, v in comps:
xs = 0 * (v + 1)
xs0 = 1
for i in range(1, (v // 2) + 1):
xsi * 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)):
reti + j += xsi * ysj
reti + j %= MOD
return ret