2014年04月20日02時58分50秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．
スパムチェッカーが $N$ 個の項目について，あるメールがスパムっぽいかどうかをチェックしていく．
その都度，スパムっぽくないと思われる場合は，点数を $G$ 点だけ加算し，
スパムっぽい思われる場合は，点数を $B$ 点だけ引く．
最初 $0$ 点であるとして，どこかの瞬間で点数が負になるとスパムメールと判定する．
$N$ 個の項目についての結果が全部与えられるので，このメールがスパムかどうかを判定する問題．
やるだけ．
$R$ 行 $C$ 列の盤面が与えられる．
各マスは，空か，動物Aがいるか，動物Bがいる，のどれかである．
行と行の間か，列と列の間にフェンスを建てることができる．交わっても良い．
フェンスで仕切られた各区画には，高々1種類の動物しかいないようにしたい．
最小で何個のフェンスを建てれば良いかを求める問題．
横向きのフェンスはどこに作るかを $2^{R-1}$ 通り全部試し，縦向きのフェンスはGreedyに建てる．
横向きのフェンスが無いと決めた場所については，その上下の行を合体させる．
その際，2種類の動物が混在するセルができるようならば，そのような横向きのフェンスの建て方は不可能．
縦向きのフェンスは，左から建てるかどうかを決めて行って，ここで建てないなら2種類の動物が混在する，という場合だけ建てるようにする．
$N$ ノードの根付き木が与えられる．
最初は，どのノードにも人はいない．
これから，$K$ 人が来て $1$ 人ずつ以下の動作をする．
最後の $K$ 人目の人が，どこかのノードに居座ることができる確率を求める問題．
全てのノードに対して，最後の人がそのノードに居座る可能性を別々に計算して，和を取る（ことにする）．
まず，最初に，全てのノードが埋まっていると仮定した時，それぞれのノードまで人が来る可能性があるという確率を計算しておく．
そして，あるノードに居座る可能性を計算するのは，DPを使う．
ルートからそのノードまでのパスを求めて，状態を（今何人動作をしたか，そのパスの何番目のノードまで埋まっているか）と取り確率を計算する．
ノードごとに求めて和を取らなくても，木のままDPすれば，一度に計算することもできる．
Current time: 2024年05月03日21時28分55秒
Last modified: 2014年04月20日02時58分50秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)