No.472

問題 $i$ で $k$ 個正答したときの順位を $r(i, k)$, 問題 $i$ まで見たときに正答数が $j$ であるときの合計順位の最小値を $R(i, j)$ とすると,

$$R(i, j) = \min_{k=0,1,2,3} R(i-1, j-k) + r(i, k)$$

となる. これを DP で更新し, $R(N-1, P)/N$ が答えとなる.

$R(i, j)$ はすべてメモリ上に載せようとすると MLE したので, $i-1$ と $i$ の部分だけ保持するようにして使い回す.