271.1

250

整数配列の各要素を0にすることを考える。一度の操作で一つの要素から高々Nだけ減算することができる。一回の操作のコストを、0でない要素に対応する値の合計とするとき、最小コストを答えよ、という問題。

要素数が10なので10!試すだけ。

500

チェスのルークとナイトの両方の動きができる駒を交互に置いていくとき、最初に置けなくなるプレイヤーはどちらか答えよ、という問題。

盤面は高々7x7なのでlongでビット演算すれば良さそう。(そもそも49^7程度の探索なのでどうでもいいような気もする。)取り敢えずメモする必要すらなかった。

1000

矩形の中に入る各頂点が格子点上にある凸包の頂点数の最大値を答えよ、という問題。

矩形の各辺にそれぞれ点を置くことにして、それらの2点間の遷移を事前に計算しておいてDPするだけ。2点間の遷移もDPで求めることができ、互いに素な(a,b)ベクトルをできるだけ多く使うことを考えれば良い。