AtCoder Regular Contest 115 A,D,E問題メモ
A - Two Choices
問題
$N$ 人が、0,1の2択で解答する $M$ 問からなるテストを受ける
$i$ 番目の人の解答は $S_i$ で与えられる
2人ペア $\dfrac{N(N-1)}{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$ が与えられる
$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-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$ パスとなるなどがある。
s==○==○==t → 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)$ で通る。
サイクル基底の概念を使わなくても、以下の考え方でもアプローチできたかも。いずれにしろ、全域木がポイント。
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}$ で求めよ
条件
$2 \le N \le 5 \times 10^5$
$1 \le A_i \le 10^9$
解法
愚直なDP
まず愚直なDPを考える。素案なので $DP_0$ としておく。
包除原理を使う時によく出てくる考え方だが、「確実」な $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でも遷移は変わりなくできることがわかる。
これで計算量は $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]$ に遷移してくるパターンは挙げ終わった)
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)