303.1

最大流を使って解く500が出るとは思わなかった。

250

螺旋状に数字を並べるとき、Nはどこに配置されるか答えよ、という問題。

0,+1,+1,-2,-2,+3,+3,...みたいなシーケンスが出てくるので、全部計算するだけ。

500

NxNのチェス盤上にナイトがいくつかある。あるナイトが別のナイトを取れないようにするために除去する最小の数を答えよ、という問題。

黒いマスにいるナイトは白いマスにしか移動できず、逆もまたしかり。なのでナイトの位置をマスの色で分離して、取れるかどうかで枝をはれば二部グラフになる。擬似的な始点と終点を付けて考えると、始点から終点に増加路が存在するということは、あるナイトが別のナイトを取れることに等しい。つまり増加路の数を考えれば良いので、後は最大流を求めるだけ。

1000

四方向に移動できる人が四人いる状況で、全員が一か所に集まれるようにするには、道をいくつ追加すれば良いか答えよ、という問題。左端に二人、右端に二人いる。

盤面が横長なので、DPでできそうな感じ。問題はかなり細かいグループに分かれること。横方向に道は4本引けて、それぞれがどれと起源が同じなのかというのを適宜処理しつつ、併合と分離を繰り返せるようにしないとダメ。それに加えて、どの列に誰が行けるのか、ということも覚えておかないといけない。

どう考えてもソースが煩雑になり過ぎるので、もっと簡潔に書ける適切な方法があるんだろうなぁ、という感じ。