読者です 読者をやめる 読者になる 読者になる

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! \cdotdp[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