戦略ミス
■A - Four Digits
stringで適当に
■B - Failing Grade
forとif
■C - Swiss-System Tournament
書いてるとおりにやるだけ、適当にsort関数を自作する。
■D - Between Two Arrays
累積和dp
■E - Red and Blue Tree
まずどの辺を何回使用するかを列挙する。
これはlca等を行えばいい。
サンプル1だと{2,3,1}
これを+か-かすることで0(=k)を作ればいい
{-2,2}+{-3,3}+{-1,1}=0
これは
{0,4}+{0,6]+{0,2} = 0+2+3+1
なので適当にナップサックすればいい。
ただ右辺が負になると答えを求めるときに配列外参照するので注意。
■F - Expensive Expense
こっちを先にすればよかった。
全方位木dpの左右累積パターン。
典型的な貼るだけ問題。
■G - 222
絶対に解けると思って特攻するも死亡。
kが偶数のときに2で割ることや
kに9を掛ける必要があることや
kが2の倍数や5の倍数のときなときに不可な事はコンテスト中にわかった。
それが最小とは限らないが、オイラーφ関数のときに満たすのもわかる。
そこからで詰まっていたが
よく考えるとphi(k)の約数しか候補となりえないので全て調べればいいだけだった。。
■H - Beautiful Binary Tree
形式的べき級数っぽいやつ。
公式解説にある通りごちゃごちゃやると
f(x) = x(1+3f(x)+f^2(x))^2となるのがわかる
g(x) = x/(1+3x+x^2)^2と置くと
g(f(x))=xとなるので
ラグランジュの反転公式を使うと
f(x)のn次の項はx/g(x)より求められる。
なので答えは1/n[x^(n-1)](1+3x+x^2)^2n
これは
1/n[x^k]Σbiom(2n,i)x^(2*i)*(1+3x)^(2*n-i)
=1/nΣ[x^(k-2*i)]biom(2n,i)*(1+3x)^(2*n-i)
=1/nΣbiom(2n,i)*biom(2*n-i,k,2*n-i)*3^(k-2*i)
