■A - Find Multiple
全部試す
■B - Base K
愚直にする
■C - Long Sequence
何セットと何個かみたいにやる。
■D - FG operation
単純なdp
dp[i][j]:=i番目まで見た最も左がjな通り数
■E - Distance on Large Perfect Binary Tree
パスは一番高いところから見て、右にxと左にd-xのような形になる
なのでサンプル1だとf(3,0) + f(2,1) + f(1,2) + f(0,3)
のようにしてやればいいい。
fの値は、親頂点の候補数と子の左右の候補数を書き合わせればいい。
■F - Distance Sums 2
僕は、全方位木dpを今週ライブラリ化しました。
■G - Isosceles Trapezium
垂直二等分線が一致し、中点が一致しなければ等脚台形となる。
doubleにして扱うとしんどいので、
0= ax + by + c の形で持つ。
map{{a,b,c},vector<{weight,{cx,cy}}}のような形でもっておき
垂直二等分線が一致するものをグループ分けし、
あとは重みが一番大きいものと、中点が一致しないものの中でもっとも重みが大きいものの組み合わせが答えの候補となる。
■H - Security Camera
フレンズさんの解説がわかりやすいです。
まず成約が、半分全列挙だと囁いているので
dp0[bef]dp1[aft]としそれぞれ前半要素、後半要素から選んだときに
監視している道の数が奇数になるかどうかを調べる。
dp2[bef][aft]はbefとaftをつないでいる道に限定して同じことをやると
dp0[bef] + dp1[aft] -dp2[bef][aft]の遇奇がわかればいいので
dp0[bef] + dp1[aft] + dp2[bef][aft]なので
dpをすべて01で管理すると
ΣΣdp0^dp1^dp2を考えればいい。(問題は偶数になる集合を聞いているので全体からこれを引く)
このままだとdp2の部分がボトルネックなのでもうちょっと頑張る。
あとは解説どおりに頑張る。
解説通りに進めると、アダマール行列と同様の性質を持つ行列の和を求める必要がある。
これはむずかしいが、他でも使えそうな知識なので覚えといたほうが良さげ
検索用：高速アダマール変換
