Codeforces/BetaRound62/62D

出展 †

• Codeforces Beta Round #62 (Problem D) (問題文)

問題 †

高さhの完全2分木が与えられる．この木に対し，2種類の操作を行う．

• add v q : ノードvに電荷qを追加する
• decay : ランダムに1つの葉を選び，根からその葉に至るパス上にある枝を全て除く．
  連結成分ごとに属するノードの電荷量の和をとったとき，その最大値の期待値を求める．

解法 †

• 各ノードvについて，vおよびvの子孫の電荷量の総和Svを求めておく
  • add v qで，vの祖先すべてにqを加えれば良い
• ノードvを根とする部分木について，すでに作った連結成分の最大値がlowerであるときの期待値を考える．
  • vが葉であるとき，期待値はmax(lower, Sv)である．
  • vが葉でないとき
    • Svがlower以下であれば，lowerを超える連結成分は出来ないので期待値はlower．
    • そうでなければ，0.5*(右側の枝を除いた期待値+左側の枝を除いた期待値)
    • vの子v1への枝を除いた期待値は，lower=max(lower, Sv-Sv')として再帰的に求めれば良い．
    • vの子をv1, v2とすると，Sv-Sv1≧Sv2，Sv-Sv2≧Sv1のどちらかは必ず成り立つので，再帰しても状態数は爆発しない．

回答 †

• 62D_pes.cpp - ↑解法の通り(pes)