■A - Full Moon
while
■B - Overlapping sheets
通常料金を使う日数全探索
■C - Blue Spring
next_permutation
■D - General Weighted Max Matching
ditdp
■E - Sandwiches
算数
■F - Octopus
実装するきにならず
順番が変わるタイミングを列挙して頑張る
適当に倍して整数で扱うなど
■G - Typical Path Problem
勉強になりました
頂点Bから頂点Aへのパス
と
頂点Bから頂点Cへのパス
の組でB以外頂点を共有しないようなものがとれるか？が分かればいい
これはわかるが判定方法が分からなかった。
これはフローで解ける。なるほどね。
■Ex - Count Strong Test Cases
サイクルの数列の集合をCとし、その元をcとする(∀c⇒Σc[i]=n)
cに対するPの並べ方はn!*(Π1/c[i]!)*(Π(c[i]-1)!)
cに対するQの並べ方はn!*(Π1/c[i]!)*(Π(c[i]-1)!)
２つは同じ結果だが(Π(c[i]-1)!)の意味が異なる
上記よりPQの並べ方はn!^2*Π1/c[i]^2
よって答えは、全てのcに対して重複を考慮して総和を求めると
ans=n!^2*Σ(Π(1/c[i]^2)*(1/|c|!))これをfpsとして解釈すると
f(x)=x^i/i^2としてexp(f(x))となり後はライブラリにおまかせ。
