2017/10/07の精進 & DDCC2017予選

今日も木DPやっていくぞい

・TDPC N 木

結構悩んだけど自力で出来た(わからなくて寝て朝飯食ってたら浮かんだ)

書き方が自由すぎて困るので、制約をつけて

dp[v]=頂点vを含む連結成分を順次大きくしていってsubtree(v)を書く方法は何通りあるか

というDPをする

vの子u[i]について、subtree(u[i])に含まれる辺を書き始めるためには先に辺v-u[i]を書かなくてはならないので、subtree(u[i])に含まれる辺をm[i]本としたとき

(v-u[i])->(subtree(u[i])の辺1)->(subtree(u[i])の辺2)->...(subtree(u[i])の辺m[i])

という順に書いていくことになる

このm[i]+1本の辺の順番を適当なものに固定して、順番を崩さないようにsubtree(v)に含まれる全ての辺を並べることを考えると、(m[0]+1個)個の同じもの (m[1]+1個)個の同じもの...があるときこれらM=(Σm[i]+1)個のものを並べる方法は何通りかを計算すればよく、これは組み合わせでいける

m[i]+1本の辺の順番が何通りあるかはdp[u[i]]でわかるのでdp[v]が計算できた

全ての頂点vについて、vを根としたときの木DPをしてやってdp[v]の和を取ると(答え)×2が出るのでmod 10^9+7における2の逆元をかけておしまい

 ・TDPC P うなぎ

結構悩んだけど自力では出来なかった

dp[i][j][k]=subtree(i)にj本のdistinctなパスがあって頂点iの次数がkになるような書き方が何通りか

というDPをする 各頂点vにおいて

dp2[i][j][k]=i番目の子までで、j本のdistinctなパスがあって親の次数がkになるような書き方が何通りあるか

という補助的なDPをして更新する

頂点vとi番目の子との間に辺を書くか、書いた場合パスの本数と次数がどうなるかを丁寧に場合分けすると出来る

 

夜はDDCCに出た 全完で103位

・A問題

はい

・B問題

タイポに気を付けましょう(BとCを打ち間違えた)

・C問題

ソートして最大と最小を(できるなら)ペアにしていく

・D問題

南北対称→東西対称or東西対称→南北対称と対称にする順を決めると取らないといけない石は簡単にわかるので、なるべくスコアが稼げるような取り方をする(バグりやすい)

とくに競プロらしいテクニックのようなものはなかった