470.1

良くできたセットですね。

250

16個のものから任意のものを交互に取り出す。お互いに取り出さないといけないものが別々に指定されており、先に条件を満たした方の勝ちとする。同時なら引き分け。このとき、お互いが最適に取り出すとして、結果を答えよ、という問題。

先手の場合、自分が取り出さないといけない個数が、相手だけが取り出す必要のあるものの個数以下ならば勝てる。逆に後手の場合、自分が取り出さないといけない個数が、相手だけが取り出す必要のあるものの個数よりも小さくないと勝てない。それ以外の状態の場合は引き分けになる。勝てるときは、相手が協力するような取り出し方はしない。

500

見てない。

1000

高々4組の結合したいものと、それを妨げるいくつかの岩がある。岩はそれぞれ破壊するのにかかるコストが指定されている。このとき、最小のコストを求めよ、という問題。

もし、どの岩も壊さずに結合することのできる組があるのならば、それは先に取り除いておく。後は、高々8個のもののうち、ある岩を壊したときに、その岩のあった場所と結合できているもののパターンと最小コストをダイクストラの容量で求めていく。グラフの辺は隣接する岩を壊すときは、パターンは変えずにコストだけを増す(通常のダイクストラと同じ)もので、パターンを変える場合は位置を変更せずに、パターンの融合を行う。この際には破壊した岩の情報の融合も行う。また、パターンの融合の際に、同じ地点が別のパスで到達していることは考慮しなくて良い。(どちらかのパターンから共通にあるものを除去したパターンがそのコストを上回らないので、このようなケースを除去しても網羅されている。)

これにより、すべてのパターンについて、一つの地点に結合させる最低のコストを求めることができるので、後はそれらのパターンを組み合わせて目的の4組を作成し、最小のコストを取り出せばよい。

激しく力技で実装したので、もっと美しい正解があることは間違いないと思う。