JAG2019 Day3 - ferinの競プロ帳

ABC はい
E DP
D 2SAT
H UFマージテク
G 期待値で式変形を頑張る
I 係数がパスカルの三角形になってる FFTでやる
J 行列を構築するやつ
F よくわからん

D

x_i = (iを集合に入れるならtrue) とする
XORについてのclosureを (not x_i) or (not x{i xor X}) と (x_i) or (x{i xor X}) の両方入れないといけないことに注意
AND, ORは部分集合の列挙でO(3ⁿ)でできる

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3883568

E

dp[i問目まで][赤をj個][赤の残量k]
dp[n][i][j] で赤と黒それぞれ足りてれば chmin(ans, dp[n][i][j])
足りてるやつがなければ-1

累積和のindexでごちゃごちゃやるの初心者か？

https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3883738

H

c_iとd_iをつないだグラフで \sum_連結成分 min(頂点数,辺数) が答え
各頂点を根とする部分木を表すUnionFindと辺の集合を持ってマージテクでマージする
UnionFind全てにK色分の情報をもたせると終わるのでmapかunordered_mapで必要なところだけもつ

dfsの内部のマージ処理をmerge関数に切り分けたらREが消えた
RE: https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884172
AC: https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884159

スタック領域を広げるやつを使ったけどREだった
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884229
構造体をswapするのがまずいのかと思って参照渡ししてswapするのを書いたけどRE
https://onlinejudge.u-aizu.ac.jp/beta/review.html#JAGSummerCamp19Day3/3884250

わからん

G

連結成分の個数 = 頂点数 - 辺数
確率変数として

$X_{v_i} =$ 木 $T$ の頂点 $v_i$ が残るなら1で残らないなら0
$X_{e_i} =$ 木 $T$ の辺 $e_i$ が残るなら1で残らないなら0

と定める． $U$ についても $Y_{v_j}, Y_{e_j}$ を同様に定める．期待値の線形性より
$E \lbrack (\sum_{i} X_{v_i} - \sum_{i} X_{e_i}) \times (\sum_{i} X_{v_i} - \sum_{i} X_{e_i}) \rbrack = \sum_{i,j} E \lbrack X_{v_i} Y_{v_j} \rbrack - E \lbrack X_{v_i} Y_{e_j} \rbrack - E \lbrack X_{e_i} Y_{v_j} \rbrack + E \lbrack X_{e_i} Y_{e_j} \rbrack$
となる．
$X_{v_i} Y_{v_j}$ は $v_i = v_j$ のとき0， $v_i \neq v_j$ のとき1/4となる．
$X_{v_i} Y_{e_j}$ は $e_j$ の端点に $v_i$ があるとき0，ないなら1/8となる．
$X_{e_i} Y_{e_j}$ は $e_i$ と $e_j$ の端点に共通する頂点番号があれば0，ないなら1/16となる．