371.1

リハビリ...。

250

W*Hの大きさの盤面を螺旋状に移動したときの、最後の位置を答えよ、という問題。

一番外側を一周したところで、問題サイズを2ずつ小さくして考えることができるので、再帰的にやる。最終的にはWかHのいずれかが高々2になっているので、パターンを列挙するだけ。(そのサイズなら愚直にシミュレーションもできる。)

500

N人ずついる二つのチームで、一人一回ずつ対戦を行う。能力があらかじめ分かっていて、能力が高い方が勝ち、同じなら引き分ける。勝った場合には2点、引き分けの場合には1点もらえるとき、一つ目のチームが獲得できる最高得点を答えよ、という問題。

ソートしてDPとか色々解き方はありそうだけれど、何も考えずに最小費用流を使うのが楽。

900

N人の人が競争したときに、特定の二人についてどちらの方が順位が良かったかという情報がいくらか与えられる。同着はないものとして、最終順位として考えられるものは何通りあるか答えよ、という問題。

可能な勝敗の情報は高々15個なので、勝敗を考慮すべき人間の集合を考えると、それの大きさは高々16になる。その中での順位の全パターンについては、上位から割り当てた人数と割り当て済みの人集合を状態にしたDPで求めることができる。これを各勝敗を考慮すべき集合について計算してやって、後はそれらの間で可能な順番の組み合わせすべてを乗じてやれば良い。これは組み合わせ全列挙でできる。