Codeforces #396 Div. 2 E: Mahmoud and a xor trip

とりあえず1を根とする根付き木として考える。

f[i][j][k] := 頂点iについて、頂点iの子孫のうち、iからその子孫までのパスの距離のjビット目がkであるような子孫の数

とする。これをメモ化再帰で解く。

ある頂点uについて

uが最も根に近い頂点であるようなパスは、uと子孫との関係から3パターンがある。

つまりvとwをuの子孫として(u,v,wはすべて異なる)

(1) v <=> u<=> w

(2) u <=> v

(3) u

これらを

f[u][j][k]を計算しながら、uが最も根に近い頂点であるようなパスの距離の和g[u]を求める。Σ(g[u])が解

Codeforces #396 Div. 2 D: Mahmoud and a Dictionary

等しい要素は、素集合データ構造でくっつけていく。

また、互いに素なAとBが反意語であることを示すのに

an[A] = Bかつan[B] = A

のような配列を使う。(unifon find木の各集合を代表する頂点を使えば単なる配列になる。)

あとは問題文に従ってこれらを操作するだけだが、矛盾する場合のチェックはすこし分かりづらかった。以下のとおり。

f:id:parukii:20170209144350j:plain

 

Codeforces #396 Div.2 C: Mahmoud and a Message

解法

まず、[l,r)の部分文字列を作れるかどうか判定するのに

各文字のカウント部分和を計算しておき、

文字iについては

cnt[i][r] - cnt[i][l]

で数えられる。つまり[l,r)の範囲に文字iがあるかどうかわかる。

[l,r)の範囲にあるすべての文字iについて

r-l >= a[i]

が成り立つかチェックする。これで[l,r)の範囲の部分文字列の判定はできた。

あとはこれを使って2種類のDPを解く。

f[x文字目まで見た][直前j個は連続] = 場合の数

g[i文字目まで見た][直前j個は連続] = 部分文字列の数の最小値

文字列全体について、分割の仕方の数と部分文字列の数の最小値は求まった。

最長の部分文字列はDPの更新時についでに計算できる。

SRM 547 DIV2 Hard: RelativelyPrimeSubset

解法

Sの要素が100以下と小さいので100以下の素因数でビットDPを試みたい。しかし、100以下の素数の個数は25個なので

2^25 * |S| <= 2^25*50 = 1.6777216 × 10^9

で間に合わない。

ここでたかだか25個の素数を列挙してみると

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

このうち53,59,61,67,71,73,79,83,89,97の10個の素数については

53*2>100より

Sの要素xが53以上の素因数をもつとき、xは素数。

よって53以上の素数は別個にカウントすれば良い。

25-10 = 15個の素数についてビットDPすれば

2^15*|S| <= 2^15 * 50 = 1638400

で間に合う。

SRM 548 DIV2 Hard: KingdomAndPassword

解法

oldPasswordが新しいパスワードにもなる場合がコーナーケース。

そうでない場合を考える。

先頭からi桁が等しいとする。つまり、新しいパスワードがoldPasswordと異なる最上位の桁をi(0-indexed)とする。この桁の値によって新しいパスワードがoldPasswordより大きいか小さいかが確定する。

(1)新しいパスワードのほうが大きい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最小値

(2)新しいパスワードのほうが小さい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最大値

の2種類のDPを解けば答えが求まる。

iは総当たりで固定。各iについてビットDPするので全体で

O(2^n＊n^2)

 

ミス

1<=oldPassword<=10^16-1

なのでoldPasswordは最大16桁ある。

配列を1<<15のサイズしか確保してなかった。

AtCoder AGC010 C - Cleaning

エディトリアルの判定

L>=min(max(c[i]), Σ(c[i])/2)
がよくわからなかった。

以下、条件判定の考察のみ
変数名はエディトリアルのものを踏襲

葉ではない頂点をv、
m = max(c[i])
とする。

T >= 0 (1)
は自明。

A[v]が最大になるのは
子供=>v=>親　を含む経路がすべてで
子供x=>v=>子供y (x!=y) を含む経路が１つもない場合であり、
A[v] <= Σ(c[i]) (2)
が成り立つ。

m = c[u] を満たす頂点uについて
u=>v=>x (xはvの親またはuでないvの子供)
を含む経路がc[u]個あるので
vを含む経路の数A[v]は
m<=A[v] (3)
を満たす。

逆に(1)～(3)が成り立つと仮定する。
T + (Σc[i]-T)/2 = A[v]
を整理すると
T = 2A[v] - Σc[i]
よって
L
= (Σc[i]-T)/2
= (Σc[i]-(2A[v]-Σc[i]))/2
= (2Σc[i]-2A[v])/2
= Σc[i]-A[v]
L個以上のペアが作れるかどうか判定したいのだった。
これは
ペアとならないものがH=Σc[i]-2L　個以下である
ことと同値。
H
= Σc[i]-2L
= Σc[i]-2*(Σc[i]-A[v])
= 2A[v]-Σc[i]
ここで
(2),(3)より
m<=Σ(c[i])
なので
H<=2A[v]-m (4)

ペアとならないものは
H' = m
個以下にすることができる。
vの子をc[i]の昇順に見ていく。
簡単のためi<jならばc[i]<=c[j]とする。
l個まで子を見たとき、子i<=lについてペアとならないものがc[l]個以下となるようにペアを作れる
これは帰納法で示せる。
よってすべての(k個の)子供を全部見たとき
ペアとならないものをH'個以下にできている。

H'<=H
を示す。
H-H'
= (2A[v]-m) - m
= 2(A[v]-m)
>= 2(m-m) // (3)より
= 0
∴ H>=H'
ペアとならないものをH個以下にできた。

以上から、条件判定は(1)～(3)だけでよい。

 

解法まとめ

根付き木にして各頂点とその親をつなぐ辺を頂点ごとに処理する。根の処理だけ特殊なので注意。