257.1

300

直前の5個の値を使って、次の値を予測するという方式のうち、最近N個のデータに適用した際の差分が最小のものの差分を答えよ、という問題。

可能な予測方式すべてについて計算するだけ。

450

各瞬間のある商品の売値と買値が提示される。それぞれの瞬間において、任意の商品のうち一番高い買値と一番安い売値のいずれかが更新された場合、その差分の平均値を答えよ、という問題。(ついでにすべての商品の売値と買値の差分の平均値も求める。)

長々と英語が書いてあるので、ちゃんと英語読めますか？という問題。

1000

N個のものをMグループに分ける。各グループには少なくともK個必要で、異なる個数のグループとは少なくともD個違うようにしないといけない。このとき、分け方は何通りあるか答えよ、という問題。

単純にDPをやろうとすると、今いくつのグループができたか、最後に作ったグループはいくつ持っているか、後いくつ残っているか、の三つを覚えておかないといけなくて、メモリが足りなくなる。実際には、最後に作ったグループがいくつでも関係なくて、あるグループに対して直前のグループよりもX個多く割り当てるなら、残りのグループに対してもそれが適用されるので、次のステップにいく前にその分削減しておけば良い。この手のDPでは結構見かけるパターン。...すぐには浮かばなかったけど。