580.1

まじめにやらないとダメ...。

250

区間グラフが与えられるので、二点を選んでできるだけ多くの区間をカバーせよという問題。

区間の両端を全パターン試すだけ。

600

N人の友人関係が区間グラフの交わりで与えられる。全員が全員に情報をブロードキャストしたい。友人への伝達は自動的に行われるとして、手動で行わないといけない伝達は最低いくつか答えよ、という問題。

全体をカバーするように選ぶという作業を延々とやればいいらしい。あんま考えてない。

1000

上以外の方向に盤面を移動していくものを、できるだけ邪魔したい。滞在したマスに書かれている値の合計値が邪魔した度合いになるとして、相手ができるだけ邪魔されないように動く状況で邪魔する値の最大値を答えよ、という問題。邪魔するには下方向への移動をブロックする壁を配置できるが、完全に邪魔してはいけない。

取り敢えず下から順にDPしていく。次の面への遷移のところをまじめにやらないとダメ。左右に移動して通った場所には既に壁があるので、それをうまいこと探索しつつ枝狩りでもすれば良さそうな雰囲気。