184.1

この前のは壊滅的に間違っていた...。概ねうまくいくけれど、完全には動作しないルーチンを書くことが多い気がする今日この頃...。

250

ある距離を移動するのにかかる時間は、2回の移動の結果が得られていればそれを利用して見積もることができる。N回の移動の結果が与えられるので、他の移動結果からの見積もりと実際の結果との最大誤差が最小のものを答えよ、という問題。

実際には問題文にはもっと書いてあるので、書いてある通りに実装しましょう。誤差は正負をそのまま残すことに注意。

500

ある袋の中にいくつかのものが入っていて、一つものを取ると確率的に中のものが高々一つ消える。このとき取り出すことのできるものの価値の期待値を答えよという問題。消える確率は中のものの重さによって決まる。

今残っているものの集合を状態としてDPする。今残っているものからあるものを除いた時に起こりうる状態から期待値が求まるので、何を除いたら期待値が最大になるかを各状態について考えれば良い。

1000

有向グラフのすべての点について、自分へのパスがあるようにするために追加する最小枝数を答えよという問題。

それぞれの点について、自分へのパスがあるかどうかはWarshall-Floydで求めることができる。後は残った点についてグラフを変形して最大流か何かで求まるんだろうと思うけれど、変形が思い付かない...。ちなみに最長パスを拡張していくという方式である程度はうまくいくけれど、完全にはうまくいかない。