275.1

難易度的にはかなりやさしめ。1000は典型的な問題だろうなぁ。

250

整数配列に対して、先頭から二つずつ要素を取り、その和の配列とその差の配列を作る。和の配列について、先頭から二つずつ要素を取り、その和の配列とその和の配列を作る。以下和の配列について同様に繰り返す。Nステップ後の和の配列と、Nステップ後の差の配列、N-1ステップ後の差の配列、...最初の差の配列が与えられるので、元の配列を復元せよ、という問題。

実装するだけ。

500

N個の真偽値が与えられ、そのうち連続してあっているのは高々A個で、連続して間違っているのは高々B個のとき、全体で真となる値の数の最大値を答えよ、という問題。

今までに連続していくつあっているか、あるいは間違っているか、という情報と、いくつチェックしたかについて最大スコアをDPしていけば良い。適当に実装したらひどい目にあった。

1000

N人の人がいて、N個のものがある。それぞれの人についてそれぞれのものの評価値が与えられる。最初i番目の人にi番目のものを割り当てるようにしていたが、そのうちのK人の間で適当に交換を行うと、K人の全体としての評価値が上がるという状況が起こるのならば、最小のKを答えよ、という問題。その時の評価値の増加分として最大のものも答える。

交換という操作は人のループを作る操作なので、結局はコストが正の最短閉路を求める問題に他ならない。従って、初期状態からグラフを作り、そのグラフを順次更新していって、コストが正のループができた時点で、そのループ長とコストの最大値を求めれば良い。

グラフの更新の仕方は、たとえば4人で交換したときにi->jへのコストの最大値がAで、もともとj->kへのコストの最大値がBならば、5人で交換したときにi->kへのコストはA+Bか4人以内で交換したときのi->kへのコストのどちらか、というのをすべてのi,j,kについてやるだけ。N^4でN<=50なので問題なく終わる。

最小平均最短路とかなんとかの問題があって、それをいじればN^3になるっぽい。開始点を1点に固定しても、すべてのループを検出するのに必要なステップ数は高々Nなので、二次元のグラフを持つ必要はなく、その分だけ早く終わる。ただしループができたかどうかの判定が若干面倒なので、余り得策ではないかも。