313.1

確率とか期待値とかは式を立てて愚直に計算(場合によっては行列乗算)するだけなんだけど、式を冷静に立てられる気が余りしない...。

250

文字列の集合が与えられるので、ある要素が他の要素の接頭辞にならないような部分集合のうち最大のものの要素数を答えよ、という問題。

TRIEの葉の数が答え。もし何か他の要素の接頭辞になっているものがあればそれを除外していくだけ。

550

N本の道がスター状に接続されている。ある道の中心の点から遠い方を開始点とする。まず中心に向かい、他のN-1本から1本をランダムで選び、端まで向かうことを繰り返す。もしある道の端に到達したとき、すべての道を通過し終わっていたら終了する。終了するまでに通過する距離の期待値を答えよ、という問題。

現在の状態をK本の道を通過していて位置Pにいる状態とする。1本目の道は問題で与えられるが、他のN-1本については後の処理で任意に選択できるので、平均値としてしまって良い。なのでK本の道のコストの平均値は、1本目の道と他のK-1本の平均値から求められる。注意すべきは現在位置で、そことは違う道を選ぶので、K本の平均値から現在位置の分を除いたもので状態を更新してやらないといけない。

// adv : 他のN-1本の平均
// rest : K本から現在の道のコストを除いたものの平均
exp[i+1] = (exp[i] + adv * 2) * p * (n - i) / (n - 1);
exp[i] += rest * 2;
p *= (i - 1) / (n - 1);

こんな感じのことをpが十分小さくなるまで繰り返す。(1本目の道が固定のために、restが各ステップで変動するため、数式が解ける気がしない。)一つ前のexpに変な更新をしているので、一つ一つのステップはちゃんと別個にやらないとダメ。