AtCoder Regular Contest 171 B,C,D問題メモ
B - Chmax
問題
(1,2,...,N) の順列 P に対して、以下を F(P) と定義する
長さ N の数列 A=(A1,...,AN) が与えられるので、F(P)=A となるような P の個数を求めよ
1≤N≤2×105
1≤Ai≤N
例
文章としては複雑だけど、要は B の各要素に対して b→max(b,Pb) という置換を繰り返していけばよい。
i 1 2 3 4
P 2 4 3 1 に対するF(P)の求める手順
B 1 2 3 4
... B[1]=1 < P[B[1]]=2 なので、B[1]←2に置換
B 2 2 3 4
... B[1]=2 < P[B[1]]=4 なので、B[1]←4に置換
B 4 2 3 4
... B[2]=2 < P[B[2]]=4 なので、B[2]←4に置換
B 4 4 3 4
... もう置き換えられるものはないので、終了
解法
まず、B は必ず大きい値に置き換えられるので、
初期状態 B=(1,2,...,N) のうち、Ai<Bi となるものがあったら無理。(0通り)
そうでない場合、A にはいくつかの同じ値が含まれている。それ毎にグループ化する。
i 1 2 3 4 5 6 7 8
A 6 6 8 4 5 6 8 8
6 6 6
8 8 8
4
5
置換配列 P は順列なので、異なる i から同じ数字 Pi に置換できない。
例えば上記では、1→6 と 2→6 という“直接の”置換を両立するような P は存在しない。
置換の法則から、値の位置 i によらず、ある時点の Bi と Bj が同じ値ならその後同じ変化をし、最終的に同じ値に行き着く、という点は重要。
また、置換は値が大きくなる方向にのみ行われる。
よって、必ず 1→2→6 というように、小さい方から同じ値になるindexを辿って置換されていく必要がある。
すると、P に求められる条件が決まってくる。
グループ6に着目して、あり得るPとして決まった箇所
i 1 2 3 4 5 6 7 8
P 2 6 ^
6以下の値
グループの中で最大の位置は、置き換えられてはいけない。
例えば、上記で P6=7 だったりすると、P1,P2 も7まで置換が進んでいないとおかしいことになる。
よって、i≥Pi という制約がかかる。
同じ理由から、各グループの最大の位置 i について i=Ai でない場合、答えは0通りとなる。
以下、A はそれを満たすとする。
グループ6と同様に、他のグループについての制約を全て適用すると、以下のようになる。
i 1 2 3 4 5 6 7 8
P 2 6 7 ^ ^ ^ 8 ^
4 5 6 8 ←○以下の値しか入れられない、という制約
まだPに使われていない値: 1,3,4,5
まだPに使われていない値は、各グループで一番左の i となる。
各グループの中で最大の位置 I={4,5,6,8} に、使われていない値 R={1,3,4,5} を、
i≥Pi となるように埋める方法の個数が、答えとなる。
R の大きい方から埋められる箇所の個数を求めていけばよい。
r=5 置けるIの箇所は3箇所 → 3
r=4 置けるIの箇所は4箇所だが、1箇所は既に埋まっている → 3
r=3 置けるIの箇所は4箇所だが、2箇所は既に埋まっている → 2
r=1 置けるIの箇所は4箇所だが、3箇所は既に埋まっている → 1
3*3*2*1 = 18 通り
O(N) や O(NlogN) で解ける。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
from bisect import bisect_left
def solve(n, aaa):
not_changed = set ()
changed = set ()
remaining = set ( range ( 1 , n + 1 ))
for i, a in enumerate (aaa, start = 1 ):
if i = = a:
not_changed.add(a)
elif i > a:
return 0
else :
if aaa[a - 1 ] ! = a:
return 0
if a in changed:
remaining.discard(i)
else :
changed.add(a)
remaining - = changed
ans = 1
MOD = 998244353
not_changed = sorted (not_changed)
m = len (not_changed)
assert m = = len (remaining)
for i, a in enumerate ( sorted (remaining, reverse = True )):
k = bisect_left(not_changed, a)
ans * = m - i - k
ans % = MOD
return ans
n = int ( input ())
aaa = list ( map ( int , input ().split()))
ans = solve(n, aaa)
print (ans)
|
C - Swap on Tree
問題
N 頂点の木があり、最初、頂点 i にコマ i が置かれている
以下の操作を0回以上、好きな回数おこなえる
辺を1つ選び、両端に置かれているコマを入れ替える
その後、選んだ辺を削除する
操作後の頂点 1,2,...,N に置かれたコマを A=(a1,...,aN) としたとき、A としてあり得るものの個数を \mod{998244353} で求めよ
1 \le N \le 2 \times 10^5
解法
操作によって木は分断され、その後2つの連結成分内のコマは入れ替わることはない。
よって、ある辺を使う場合と使わない場合では、別の A となる。
①--②--③--④--⑤--⑥
③-④の辺を選ぶ場合
①②③頂点にあるコマの集合は、「①②③から2個と、④⑤⑥から1個」
④⑤⑥頂点にあるコマの集合は、「④⑤⑥から2個と、①②③から1個」
③-④の辺を選ばない場合
①②③頂点にあるコマの集合は、「①②③」
④⑤⑥頂点にあるコマの集合は、「④⑤⑥」
また、ある頂点 v から出る辺について、異なる順で選んだ操作列で A が同じになることはない。
雑な証明
①--②--③--④--⑤ 操作列(選んだ辺の列)が決まっていて、
| その中で ③-②, ③-④, ③-⑥ がともに出てくるとする
⑥--⑦ (各辺を (2) (4) (6) と呼ぶことにする)
単純化のため、この3辺以外の操作を行わない場合、
(2)→(4)→(6) の順に操作 ①--③--⑥--②--⑤
└--④--⑦
(6)→(4)→(2) の順に操作 ①--④--②--⑥--⑤
└--③--⑦
この入れ替わり方が、辺の選び方の順(今回の場合6通り)全て異なる。
選んだ順に、頂点 ③②④⑥ にあるコマが ⑥③②④ のように、シフトする。
この3辺以外の操作も行う場合でも、連結成分にあるコマの集合で考えれば同様に考えられる。
頂点を ③、①②、④⑤、⑥⑦グループに分ける。
それぞれG3 G2 G4 G6 とする。
最初 G3,G2,G4,G6 の頂点集合にあったコマの集合は
たとえば (2)→(4)→(6) の順に操作した場合、以下のように移動する
G3から1頂点→G2に移る
G2から1頂点→G4に移る
G4から1頂点→G6に移る
G6から1頂点→G3に移る
この移動の仕方が辺の選び順に対応し、異なる選び順では異なる A となる
(省略するが本来は、以上で A が異なる条件は全てであるという証明も必要。公式Editorial参照。帰納法でできるみたい)
頂点 v について、「v から出る辺のうち、どの辺がどの順で選ばれるか」のパターンを P(v) とする。
矛盾しないように定めることができる全頂点のパターンの組 (P(1),P(2),...,P(N)) の個数が、求めるものとなる。
(※矛盾しない=全ての辺 (u,v) について、P(u) と P(v) で辺 (u,v) を選ぶ/選ばないが一致している)
根を適当に決めて、以下のDPをする。
DP[v,k]= 頂点 v 以下の部分木に含まれる全頂点についての矛盾しないパターンの組 (P(v),P(w),P(x),P(y),...) の個数
(v)
/ | \
(w) (x) (y)
: : :
DP[v] を計算するため、以下のDPをする。
k:0 1 2 3
DP2[0] = [1, 0, 0, 0] と初期化する。kはvの子の数まで用意する。
子頂点を1つずつ採用/不採用を決めていく。
1つめの子の DP[w] = [5, 9, 3] だとして、
辺 v-w を選ぶ場合の係数:
DP[w,k] で子を k 個選んでいる中の、どこに v-w 辺を挿入するか、という場合分けが増える。
k に対して (k+1) 通りなので、
t = Σ_k( DP[w,k] * (k+1) ) = 5*1 + 9*2 + 3*3 = 32
辺 v-w を選ばない場合の係数:
v-w 辺を選ばない場合には、k での場合分けは不要。単純に w 以下の決め方となる。
s = sum(DP[w]) = 17
DP2[0] から DP[1] の遷移は、↓選ばない場合 s 倍、↘選ぶ場合 t 倍となる。
DP2[0] = [1, 0, 0, 0]
↓
DP2[1] = [17, 32, 0, 0]
他の子についても同様に遷移していき、最終的に DP2[vの子の数] が得られる。
ここに、各 k につき子の選び順 k! をかけたものが、DP[v] となる。
全体を O(N^2) で計算できる。
二乗の木DPは、各頂点に付き「部分木の頂点数」分の配列を持ってマージしていっても O(N^2) で収まるという理論だが、
この問題では、各頂点に付き「子の頂点数」分の配列しか不要だし、マージも子ごとに独立に計算できるので、
ランダムなケースでの平均計算量はより少なく済む。
1つの根が N-1 個の子を持つようなヒトデグラフなど、特殊な場合の最悪計算量として O(N^2) かかる感じ。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
def precompute_factorials(n, MOD):
f = 1
factorials = [ 1 ]
for m in range ( 1 , n + 1 ):
f = f * m % MOD
factorials.append(f)
f = pow (f, MOD - 2 , MOD)
finvs = [ 1 ] * (n + 1 )
finvs[n] = f
for m in range (n, 1 , - 1 ):
f = f * m % MOD
finvs[m - 1 ] = f
return factorials, finvs
n = int ( input ())
MOD = 998244353
facts, finvs = precompute_factorials(n, MOD)
links = [ set () for _ in range (n)]
for _ in range (n - 1 ):
u, v = map ( int , input ().split())
u - = 1
v - = 1
links[u].add(v)
links[v].add(u)
q = [ 0 ]
status = [ 0 ] * n
dp = [[] for _ in range (n)]
while q:
u = q[ - 1 ]
if status[u] = = 0 :
status[u] = 1
for v in links[u]:
links[v].remove(u)
q.append(v)
else :
q.pop()
ch_cnt = len (links[u])
dp_u = [ 0 ] * (ch_cnt + 1 )
dp_u[ 0 ] = 1
for i, v in enumerate (links[u]):
dp_v = dp[v]
s = sum (dp_v) % MOD
t = 0
for j, val in enumerate (dp_v):
t + = (j + 1 ) * val
t % = MOD
dp_u[ch_cnt] * = s
for j in range (i, - 1 , - 1 ):
dp_u[j + 1 ] + = dp_u[j] * t
dp_u[j] * = s
dp_u[j + 1 ] % = MOD
dp_u[j] % = MOD
for i in range (ch_cnt + 1 ):
dp_u[i] * = facts[i]
dp_u[i] % = MOD
dp[u] = dp_u
ans = sum (dp[ 0 ]) % MOD
print (ans)
|
D - Rolling Hash
問題
非負整数列 X=(x_1,...,x_n) に対して、以下を hash(X) とする
M 個の区間 (L_i,R_i) が与えられる
次の条件を満たす、長さ N の非負整数列 A=(A_1,...,A_N) があるか判定せよ
1 \le N ale 16
1 \le B \lt P \le 10^9
P は素数
解法
以下、添字が合わないのが気持ち悪いので、A の添字を0始まりとし、
ローリングハッシュも逆に(先頭が下の位になるように)計算することにする。
クエリ L,R も、元の位置から、逆転させたこの並びの位置に対応させれば、元の問題と変わらない。
先頭からこれの累積和を取ったものを C とすると、
C[-1] = 0 (便宜的にC[-1]を0とする)
C0 = A0B^0
C1 = A0B^0 + A1B^1
C2 = A0B^0 + A1B^1 + A2B^2
: :
C[N-1]= A0B^0 + A1B^1 + A2B^2 + ... + A[N-1]B^(N-1)
区間 (L,R) を抜き出した文字列のハッシュは、C を使って表せる。
P が素数で \dfrac{1}{B^{L}} = B^{-L} \not\equiv 0 \mod{P} なので、modで考えても上の式がゼロ除算で計算できなくなることはない。
よって、これが0になる時というのは、C_R \equiv C_{L-1} \mod{P} のときに限られる。
つまり、C[-1] も合わせて全部で N+1 個の頂点があって、
「こことここは同じになってはいけない」という条件が M 個与えられる、と考えられる。
これは、グラフの頂点彩色の問題に言い換えられる。
A にはどんな数でも置けるので、上手く調整すれば C の各項は 0 \le C_i \le P-1 の P 個の値を好きに設定できる。
(言い換えると、各要素が 0 \le C_i \le P-1 である任意の C に対して、対応する A が存在する)
ここで、もしグラフを塗り分けるのに P+1 以上の色が必要となった場合、どうしてもどれかは被ってしまい、アウトとなる。
逆に P 色以下なら、可能となる。
頂点彩色数は、bitDPで O(N2^N) や O(3^N) で計算できる。
P の制約はやたらでかいくせにほとんどの場合Yesで、求めるのが難しいのは P \le 13 の時のみという、なかなか癖のある問題。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
def bruteforce(p, b, n, aaa):
for i in range (n):
for j in range (i + 1 , n + 1 ):
ccc = aaa[i:j]
rh = 0
for c in ccc:
rh = (rh * b + c) % p
if rh = = 0 :
return False
return True
def bruteforce_test():
from itertools import product
n = 5
p = 5
b = 4
ok = 0
ng = 0
for aaa in product( range ( 1 , p), repeat = n):
if bruteforce(p, b, n, aaa):
ok + = 1
print (aaa)
else :
ng + = 1
print (ok, ng)
def chromatic_number(n, links) - > int :
n2 = 1 << n
dp = [ 0 ] * n2
pm = [ 0 ] * n2
pm[ 0 ] = 1
for i in range ( 1 , n2):
lsb = i & - i
pm[i] = pm[i ^ lsb] * - 1
pm.reverse()
dp[ 0 ] = 1
for i in range ( 1 , n2):
lsb = i & - i
j = lsb.bit_length() - 1
dp[i] = dp[i ^ lsb] + dp[(i ^ lsb) & ~links[j]]
for k in range ( 1 , n):
res = 0
for i in range (n2):
cur = pm[i] * dp[i]
pm[i] = cur
res + = cur
if res > 0 :
return k
return n
p, b, n, m = map ( int , input ().split())
n + = 1
n2 = 1 << n
links = [ 0 ] * n
for _ in range (m):
l, r = map ( int , input ().split())
l - = 1
links[l] | = 1 << r
links[r] | = 1 << l
if n < = p:
print ( 'Yes' )
exit()
cn = chromatic_number(n, links)
if p > = cn:
print ( 'Yes' )
else :
print ( 'No' )
|