537.1

やるだけ。できないけど。

275

AとBの線形結合でできる値をすべて作れるようなXとYの組のうち、Xが指定された値のものは何通りあるか答えよ、という問題。

要はXとYでAとBをそれぞれ表現できるか否か。(Xだけで表現できるならYはどうでもいいので無限通り。)

500

見てない。

925

有向グラフの辺ごとに通って良い回数が指定されている。どの辺も最低一度は通らないといけないとき、最長のループの長さを答えよ、という問題。

最初の一回目の重みをとても大きい負の値にして、二回目以降の重みを-1にする。このグラフの最小費用流を求めてやると、とても大きい負の値が辺の数だけと、それ以外の負の値がいくらか、になる。なのでこれから使った辺の数を求めてやれば良い、とかどうとか。始点と終点の付け方が不明...。

(追記)

グラフの作り方が分かったのでメモ。

まず、行和と列和をそれぞれ求める。(これをノードと思って二部グラフを作る。)

行和と列和の差分が正のヤツには、始点からその値だけ流す。負のヤツにはそいつから終点までその値だけ流す。このときの重みは0で良い。行列上に流量があるヤツは1減算して流量を決め、重み1の辺を作成する。同じ行番号、列番号の間では重み0の辺を流量無限で作成する。後は最小費用流。

これの最小費用が何を意味するかというと、行和と列和というのは入ってくる流量と出て行く流量のことで、これが一致するようにできるだけ少ない辺を除去したときの辺の数になる。このとき(無向グラフでいうとすべてのノードの次数が偶数なので)始点と終点が一致する一筆書きができる。(除去した辺数が最小なので、一番長いループに相当するはず。)

ただし、連結されていないと複数のループであるので、どこかでWarshall-Floydか何かで連結チェックだけしておく必要がある。