Many Requirements（全探索）

問題

正整数 $ N, M, Q $ と、４つの整数の組（ $ a_i, b_i, c_i, d_i $ ）が $ Q $ 組与えられます。

以下の条件を満たす長さ $ N $ の整列 $ A_1, A_2, …, A_N $ （数列の添字は 1 始まり）を考えます。

🔹 $ A_i $ は正の整数
🔹 $ 1 \leqq A_1 \leqq A_2 \leqq … \leqq A_n \leqq M $

この数列のスコアを「 $ A_{b_i} - A_{a_i} = c_i $ を満たす $ i $ について $ d_i $ の総和 」とします。

数列 $ A $ の最大スコアを求めて下さい。

解法・ソースコード

この問題は、数列 $ A $ を全探索 すれば解くことができます。

次の条件を満たす長さ $ N $ の数列を全列挙します。

🔹 $ 1 \leqq A_i \leqq M $
🔹 $ A_1 \leqq A_2 \leqq … \leqq A_N $

この数列に対しスコアを計算し、最大値を出力すればよいことになります。

数列の全列挙には combinations_with_replacement関数 を使っています。（24行目）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from itertools import combinations_with_replacement
#--------- 入力例 ----------
n, m, q = 3, 4, 3
a = [1, 1, 2]
b = [3, 2, 3]
c = [3, 2, 2]
d = [100, 10, 10]
#---------------------------
# 添字(a, b)を0始まりにする
for i in range(q):
    a[i] -= 1
    b[i] -= 1

# 数列Ａのスコアを算出
def calc_score(A):
    score = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A [ai] == ci:
            score += di
    return score

res = 0     # 最大値
# 数列Ａを全探索する
for A in combinations_with_replacement(range(1, m + 1), n):
    x = calc_score(A)
    print(A, x)
    res = max(res, x)
print('------------------')
print('解（最大値）：', res)

[実行結果]

(1, 1, 1) 0
(1, 1, 2) 0
(1, 1, 3) 10
(1, 1, 4) 100
(1, 2, 2) 0
(1, 2, 3) 0
(1, 2, 4) 110
(1, 3, 3) 10
(1, 3, 4) 110
(1, 4, 4) 100
(2, 2, 2) 0
(2, 2, 3) 0
(2, 2, 4) 10
(2, 3, 3) 0
(2, 3, 4) 0
(2, 4, 4) 10
(3, 3, 3) 0
(3, 3, 4) 0
(3, 4, 4) 0
(4, 4, 4) 0
------------------
解（最大値）： 110

$ A = [1, 2, 4] $ または $ A = [1, 3, 4] $ とする場合に最大となり、この数列のスコアは 110点 となります。