312.1

解けたけど、解けていないセット...。

250

直方体が二つ与えられるが、一部くっついている場所がある可能性がある。このとき全体の体積を求めよ、という問題。

何も考えずに全部の座標をチェックして、二回目なら無視するという処理をするだけ。

500

N地点あり、有向枝がいくつか付与されている。すべての地点に移動できる(戻ってくるとかは考えない)ように人を配置する。配置するコストは地点ごとに異なるので、コストの平均値を最小化せよ、という問題。

地点Aから地点Bに移動でき、その逆が成り立たないとき、Bには配置する必要がない。地点Aから地点Bに移動でき、その逆も成り立つとき、AかBのどちらかには配置する必要がない。以上のように配置する必要のない点には適当な順序付けができるので、配置しなくてはならない地点と、どれか一つに配置しなくてはならない地点の集合が決定できる。集合からは一番コストが小さい地点を選べばよい。

後は配置していない地点から、コストの小さい順に平均値を小さくする方向で追加していけば良い。(最後の処理は本質でないので、出題の意図としてはかなり不明...。)

1050

二次元の整数配列が与えられる。複数個の隣接する要素からなる集合のうち、総和が最小のものの値を答えよ、という問題。

上の行から順番に集合に入れるものと入れないものを全通り試す。このとき、隣接状態を管理しながら進めていく。すべての要素が隣接していると判定されたものについては最小値をメモしておく。

直前の行の利用状況と隣接状況をうまくエンコードするとかなり小さくなるので...。適当に最適化をするとなんとか通る感じ。想定解法が分からない...。