問題
エスカレーターの前にn人並んでいる。先頭の人は1分毎に確率pで勇気を振り絞ってエレベーターに乗り、1-pでその場にとどまる。エレベーターに乗れるのは先頭の人だけ。また、一度乗ったエレベーターは二度とおりることはない(こわい)この時、t分後にエレベーターに乗っている人数の期待値を求める問題。
解法
前からi番目の人がt分以内に乗る確率をDPで求めて足す。
登録:
コメントの投稿 (Atom)
Håstadのスイッチング補題
回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...
-
0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます. 1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ... -
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで... -
1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...
0 件のコメント:
コメントを投稿