何故かreturn true;と書いた場所があり
そのせいでREが出ていたが、それに気がつくのに13分かかるなどした。
それもあって6完しても微冷え。
result:oooooo--(105分(87分+3WA))
perf:1894(1924->1921)
87分で6完(277位)でperf:2000
■A - Water Pressure
double
■B - Election
map
■C - Counting 2
lower_bound
■D - Neighbors
パスでないと駄目(孤立点含む)
適当にdfsしてvisitedに戻ってこないかと、edgeが2本以下かを確認する。
■E - Minimal payments
ABC182F - Valid payments(当時のdiffは2121,今回は1740)
メモ化再帰。
■F - Jealous Two
ソートして座圧してセグ木。
コーナーケースはサンプルにある。
■G - Balls in Boxes
形式的べき級数で考える。
sumple2で考えると
(1/0!+2/1!*x+3/2!*x^2)*(2/0!+3/1!*x+4/2!*x^2)*2!
をn^kで割ればいい
つまり
[x^k]Π(Σ(A_i+j)/(j!)*x^j)*(k!/n^k)
が求まればいい。
ここまではコンテスト中でもわかった。
[x^k]Π(Σ(A_i + j)/(j!)*x^j)を高速で求める必要がある。
Σ(Ai+j)/(j!)*x^j=AiΣ(1/j!)*x^j + Σ(1/(j-1)!)x^jなので
=Ai*e^x+x*e^x=(Ai+x)*e^xとなるので
Π(Σ(Ai+j)/(j!)*x^j)=e^nx*Π(Ai+x)
Π(Ai+x)のパートはO(n^2)で求まる(2乗の木dpで出てくる形)
最後にk!や1/(k-i)!なんて計算できないよ！となるが
そのあたりは外に出した定数を中に入れたりすると片付く。
Σ(A_i + j)/(j!)*x^j=(Ai+x)*e^x
の変形ができてないの反省だよね。
■H - Minimum Coloring
最小費用流。
二部グラフの最小重み辺被覆
公式解説の言い換えはなれてないと難しい気がする。
E1に属する辺が、端点を共有しなくてもいいようにしてるとことか
noshi91さんのユーザー解説の解き方がめっちゃ賢い
流量下限付きの最小費用流問題の解法
S->Lに(n,INF)と(1,0)の辺を貼る
L->Rに(1,c)の辺を貼る
R->Tに(n,INF)と(1,0)の辺を貼る
S->Tに(n,2*INF)の辺を貼る
こうしてn流すと
2*INFか0orINF+c+0orINF
の流れ方をするので0を使えるなら使っとけ！という話になり
絶対に通るので流量下限が満たされる。
これで求まったcostにn*2*INF-(h+w)*INFを引けばいい
