575.1

重みのないグラフで最小費用流を使うときは、ダイクストラのループを途中で打ち切ってしまっていいはず...。そもそも最大流ライブラリを整備するべき...。

250

ある整数から始めて、交互にその整数の1とその整数以外の約数を引くという操作を適用していく。その操作ができなくなった方が負けとするとき、どちらが勝つか答えよ、という問題。

奇数からは必ず偶数に遷移し、偶数からは2のべき乗でなければ奇数に遷移できる。なので、2のべき乗だけ例外処理する必要があるが、偶奇で勝敗が大体決まる。2のべき乗は交互に適当に頑張る...。

500

見てない。

1000

L字型のブロックを市松模様上の盤面の上に配置することを考える。折れ曲がっている部分は黒いマスにしか置いてはいけない。また、重なってもいけないし、置けないマスがいくつかある。最大でいくつのL字型ブロックを配置できるか答えよ、という問題。

2個の白いマスと1個の黒いマスを占有する。白いマスに着目すると、偶数行目のものと奇数行目のものを一個ずつ占有する形になるので、偶数行目から黒いマスを通って奇数行目へ、という感じのフローにすれば、最大流になる。流量制御のために黒いマスを二重化してやれば良さそうな感じ。