502.1

比較的良い問題だと思ったけれど、かなり既出だったらしい。

250

見てない。

500

得点が時間で減衰する問題がN問あるとき、それぞれに対しかかる時間と、初期点数、減衰量が分かっているとき、時間T以内に得ることのできる最大得点を答えよ、という問題。

局所的に見ると、二つの問題についてどちらを先に解くべきかはユニークに決まる。また、これらは推移律を満たすので、全体をソートすることができる。後はその順番で解くか解かないかをDPすればおしまい。

1000

0からN-1までの整数K個の合計がNで割り切れるものは何通りあるか答えよ、という問題。

なんらかの分割統治だろうけれど、まったく分からない...。