ABC057D - Maximum Average Sets
自分と同じ解法で通してる解説がなくて「？」になったのでやり方を書き残します。
とりあえず「組み合わせにおける個数」「組み合わせに含まれる品物の数」がわかればいいです。なので部分和 dp に個数の軸を加えて
$dp[i][j][k]$ = $i - 1$ 番目までの要素で $j$ 個選び、なおかつ $k=1$ ならば $i$ 番目の要素を選ぶ時の総和の最大
として $dp[n][i][j] (a \leq i \leq b, j \in \{0, 1\})$ を拾っていきます。
ここで、最大値と一緒にその個数も計算することが可能です。
$cnt[i][j][k]$ = $dp[i][j][k]$ に対応する選び方の総数
こちらの更新がちょっとめんどくさいのでこの解法を捨てた方もいるかもしれません。やり方としては ABC211D と同じ発想で「$dp[i][j][k]$ は今の値より小さい値に更新されることは無い」ことを利用します。すなわち
- $dp$ を更新しようとするときに値がより大きい値に更新されるなら、$cnt$ は更新元の値と同じ値になる
- そうでなく、$dp$ の値が完全に等しいならば、$cnt$ は更新元の値との和になる
漸化式でいえば
$cnt[i + 1][j + 1][1] = cnt[i][j][k] (dp[i + 1][j + 1][1] < dp[i][j][k] + v[i])$
$cnt[i + 1][j + 1][1] += cnt[i][j][k] (dp[i + 1][j + 1][1] = dp[i][j][k] + v[i])$
$cnt[i + 1][j][0] = cnt[i][j][k] (dp[i + 1][j][0] < dp[i][j][k])$
$cnt[i + 1][j][0] += cnt[i][j][k] (dp[i + 1][j[0] = dp[i][j][k])$
このように最後まで $dp$ を回すことで、各選ぶ個数について最大ではない組み合わせを全部排除できます。
あとは [(総和 $÷$ 選ぶ個数), (選び方の通り数)] となる map を作って答えます。
コード (解説中の $dp$ が $mx$ で $cnt$ が $dp$ になってます、すみません)
