583.1

かなり簡単な問題だったのに、解けなかったのでどうしようもない。

250

見てない。

500

木の枝を目的の状態になるようにフリップしたい。始点と終点を決めて、そのパス上の枝をフリップする操作を最低何回やる必要があるか答えよ、という問題。

一つの枝を二回フリップする状況があると仮定すると、その枝を使おうとする二本のパスをつなぎ変えてやると、その枝を通らない別の二本のパスに作り変えることができる。なので、一つの枝を二回フリップしない状況にできる。

ということなので、後は適当に探索しながら、子で必要な回数と、自分経由したがる本数から、自分で必要な回数と親を経由したいかを返してやればおしまい。

950

二次元平面状に各行各列に一個ずつものを置きたい。各マスに置く確率が与えられるので、同じマスに繰り返し置くことがあり得る状況で、条件を満たすのに必要な期待値を答えよ、という問題。

盤面の幅か高さが高々12なので、それを使って頑張れば良いっぽい。後は知らない。