358.1

比較的やるだけセット。結果的にどうやっても通ってしまう感じ。

250

ある数字を作りたいが、使って良い数字が指定されており、後はinc/dec操作しかできない。数字指定とinc/dec操作の必要な最小回数を答えよ、という問題。

作りたい数字が比較的小さいので、その倍くらいまでの全部の数字を指定できるか試し、指定した後にinc/decだけで目的の場所に移動することを考えれば良い。明らかに遠いところに行く必要はないので、適当に打ち切る。打ち切らなくても間に合うけれども。

500

重さの指定された重りがある。同じ重さであればいくつでも使って良いので、天秤に乗せて他の重りすべての代替ができるような重りの集合の最小要素数を答えよ、という問題。

重り集合の全部の重りのgcdが等しい限り、代替は可能。なので、0から開始して、可能なgcdをBFSして、すべての重りのgcdに到達するまでの最小距離(必要な重りの最小数)を求めれば良い。gcdなので余りたくさんの種類は出現しない。

1000

共食いする動物がいる。食べるか否かの関係が与えられ、高々2匹しか食べないとして、生き残る最小数を答えよ、という問題。

単純な最大流の問題。食べる関係にループができるが、そこを適当に解消すれば通る。食べる関係は、3つのパラメータが広義に大きいことなので、お互いに食べる関係にあるときは3つのパラメータが等しい時だけ。なので、IDという4つ目のパラメータをこのときだけ持ち出してやれば、変な循環は起きないので、安心して最大流できる。