503.1

手も足も出ず...。

250

見てない。

500

連結なN都市にM都市を追加して全部連結にしたい。M都市からランダムに選び、一番近い連結な都市と結合させる。(結合した後は連結になっているので、新たに選んだ都市と結合できるようになる。)このとき、結合距離の期待値を答えよ、という問題。

ある都市について、追加するときのコストは、N都市の一番近い都市か、M都市のうちのより近い都市によって決定する。M都市のうちのK都市が影響するのであれば、(K+1)!通りについて吟味する必要がある。実際には、一番近い都市が先に選ばれていれば、他のK-1都市は影響しないので、そのような状況は1/2の確率で起きる。二番目に近い都市が影響するのは、追加する都市が最初に追加される場合以外なので、1/2-1/3の確率で起きる。後はこれらの事象は独立なので足し合わせるだけ。

1000

二つのビルの間に斜めに橋をかける。橋の傾きは45度で、それぞれのフロアか既設の橋にちょうど当たるようにしかかけられない。橋をかけて連結させたいフロアが指定されるので、最小のコストを求めよ、という問題。

何も浮かばず...。