AtCoder Grand Contest 024 E - Sequence Growing Hard

ほげほげ(ポエム)


最近割と解説みて「はあ?」ってなるなること減ってきた気がする。
いや、これ普通にできなかったけれどね。【言われてみれば】妥当な進め方だよなあとか思う感じ。
まあでも、操作を整理してから木を数えるのと同義ですよね、ってのはちと距離があるね。順番を考慮しないといけないこととか余計に難しい。
公式解説は英語の方を読みました。りんごさんが書いたのかなー?



解説放送で木の数を求めればいいというところまでいったらあとはもう簡単でと言っていましたが私はずいぶんそこに時間を費やしました。
これはよくある話なんですね。
まあ。DPをぐっとにらめば累積和が見えてくる、とか数えるときにな何か一つを特別扱いしてあげないと重複して数えてしまうだとか。(伝わる気がしないけれど、木のDP遷移を考えるときに掛ける係数がcomb(n-2.k-1)なのがわからなくって、付け加える方の木の根元を一番最初に数えてあげないと重複が起こるよってところの話、ちなみにこのコンビネーションは木をマージする際にどの順番でどっちの木の頂点を選ぶかの組み合わせだよね、今回数えるのは木の形と頂点の選び方で二つの木をマージするときにはそれぞれの順番は決まっているので)
典型的な考え方なんだよなあ、とか思いつつバカみたいに時間を溶かしていた。DPはすぬけさんのコードがいい感じにわかりやすい。



でもこれが1200の平均的な難易度ならばだいぶ光が差してきたかもしれないね。
かんばっていきませう。