2011-11-30 Re: the Princess (ZOJ Problem Set - 3560) ZOJ Online Judge http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3560 問題 n人の人がいて掲示板に発言を書きこんでいく。それぞれの人はsignatureと発言を持っている。掲示板に発言を書きこむのは直前の発言をした人以外で出てきた人である。次に書きこむ確率は(その人が直前の発言で出てきた回数)/(直前の発言に出ている発言者以外のsignatureの個数)である。0番目の人から発言を開始した時、発言はいくら続くか期待値を求めよ。 1<=n<=100 解法 無限に続くかどうかの判定はdfsで行い、期待値は連立方程式を作ってガウスの消去法で求める。