1/24 日記

ねむねむにゃんこ

今日はあまり問題数をこなせなかったけど、黄diffを二つ撃破できたからよしとする。

F - Sugoroku2 (atcoder.jp)

昨日のABC-F。

すごろく系で期待値を求める問題なので、まずは漸化式を立てる。

振り出しに戻るマスの集合をAとすれば、マス i にいるときの期待値dp[i]は

dp[i]=( (1/M) ∑ ( ( j=i+1~i+M )/{A} ) dp[j] ) +( (1/M) ∑ ( j ∈A ) dp[0] ) +1

と表される。

ここで問題になるのはMが大きいという点だけど、dp[j]は何度も計算に使われるから累積和を取りたくなる。後ろから見たときの累積和を rui 、j∈Aとなる j の個数を cnt とすれば、

dp[i]=(1/M)*(rui[i+1]-rui[i+M]) + cnt*dp[0] /M +1

となる。dp[0]の分は別に累積和をとって、dp[0]を求めるときに左辺に寄与分を移行してあげればいい。

F - Distributing Integers (atcoder.jp)

ちょっと悩んだけど構造は意外と単純だった。

頂点vの子をch 1, ... ch kとし、頂点 i の部分木のサイズをsz[i]すると、

頂点vの部分木に整数を書き込む場合の数dp[v]は

dp[v]=(sz[v])! * ∏dp[ch]/(sz[ch])!

と書ける。(色が着いた球の順列の個数の数え上げを思い出してみよう)

なので、O(N^2)で解ける。これをO(N)で解きたいので、例によって全方位木DPをする。

この問題ではdpとszはともに根とする頂点によって値が変わるため、この二つの値をpairにして全方位木DPをすればいい。

・作問

ちょっとサボっていたけど、今日はテストケースを見直してyukicoderに問題文とテストケースをアップした。明日もう一度見直す予定。

流れが分かったからどんどん問題を作りたいな。

 

みんな好き。おやすみなさい。