ctyl's problem solving

競技プログラミングが主な話題です。

SRM #673 Div.2 Hard BearPermutations2

このレベルの問題を1時間で解くにはまだ修行が足りないと感じました．

解法はDP(Editorialを大分参考にしました)．

要素数 $n$ の場合のスコアを $dp[n$ ]とする．求めるべきは $dp[N$ ]．

下の図のようなシチュエーションである頂点から左A個のヒープと右B個のヒープに分断されるケースを考える．こうなるケースは $_{n-1}C_{A}$ 通りの組み合わせがある． $A>0$ かつ $B>0$ のときは必ず最初の分岐のスコアが左右のヒープの中のスコアに合算される．(AとBどちらかが0のときは $dp[n-1$ ]が足される．)最初の分岐のスコアは根(図の丸)からそれぞれのヒープまでの距離として独立に計算できる．

ヒープAに関連するスコア

ヒープAのみのスコアは $_{n-1}C_{A} \cdot {B!} \cdot dp[A$ ]

根からヒープAの根までのスコアは $_{n-1}C_{A} \cdot A! \cdot B! \cdot \frac{A+1}{2}$

ここで $\frac{A+1}{2}$ とは根からヒープAまでの距離の平均である．(1からAの値までが全て同じ数づつ現れるのは明らか)

ヒープBに関連するスコア

ヒープBのみのスコアは $_{n-1}C_{A} \cdot {A!} \cdot dp[B$ ]

根からヒープBの根までのスコアは $_{n-1}C_{A} \cdot A! \cdot B! \cdot \frac{B+1}{2}$

これを全ての $A=0,1,\cdots,n-1$ において合算すると $dp[n$ ]となる．整理すると

$dp[n$ ] $\displaystyle = \sum _{A+B=n-1}^{}$ $_{n-1}C_{A}$ $(B! \cdot$ $dp[A$ ] $+ A!$ $\cdot dp[B$ ] $\displaystyle + A! \cdot B! \cdot \frac{n+1}{2})$

f:id:ctylim:20151121001218p:plain

SRM #673 Div.2 Hard

プラグインをCodeProcessorからKawigiEditに変えてみた．IDEを使っている身としてはこちらの方が断然良いですね！

KawigiEdit Documentation