ABC165 C. Many Requirements
問題
長さNの数列Aで、以下の条件を満たすものを考える。
- 1 <= A_1 <= ... <= A_N <= M
また、Q個の(a_i, b_i, c_i, d_i)が与えられる。
スコアを「A_{b_i} - A_{a_i} = c_iを満たすd_iの総和」とするとき、スコアの最大値を求めよ。
制約
- 2 <= N <= 10
- 1 <= M <= 10
- 1 <= Q <= 50
- 1 <= a_i <= b_i <= N
- 0 <= c_i <= M-1
- (a_i, b_i, c_i) != (a_j, b_j, c_j) (i != j)
- 1 <= d_i <= 10^5
解法
数列Aの個数は、M個から重複ありでN個選んでそれを昇順に並べれば生成できるので、重複組合せで求めることができる。
おおよそ、10_H_10 = 19_C_10で、大きそうに見えるが、実際はそんなに多くない。
(だいたいの見積もりとして、「Σ_{0<=y<=x} x_C_y = 2^x」から「x_C_y <= 2^x」と考えられる。)
2^20 = 1,048,576 = 10^6
2^24 = 16,777,216 = 1.6 * 10^7
全数列が列挙できるので、それに対してQ個の条件を満たすものの和を計算すればよい。
