Edit

【pythonでABC165を解説】C - Many Requirements

問題概要

問題ページ

C - Many Requirements
C - Many Requirements

問題ページへ移動する

問題文

正整数 \(N\) , \(M\) , \(Q\) と、\(4\) つの整数の組 ( \(a_i\) , \(b_i\) , \(c_i\) , \(d_i\) ) \(Q\) 組が与えられます。

以下の条件を満たす数列 \(A\) を考えます。

  • \(A\) は、長さ \(N\) の正整数列である。
  • \(1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M\)

この数列の得点を、以下のように定めます。

  • \(A_{b_i} - A_{a_i} = c_i\) を満たすような \(i\) についての、 \(d_i\) の総和 (そのような \(i\) が存在しないときは \(0\))

\(A\) の得点の最大値を求めてください。

制約

  • 入力は全て整数
  • \(2 ≤ N ≤ 10\)
  • \(1 \leq M \leq 10\)
  • \(1 \leq Q \leq 50\)
  • \(1 \leq a_i < b_i \leq N\) ( \(i = 1, 2, ..., Q\) )
  • \(0 \leq c_i \leq M - 1\) ( \(i = 1, 2, ..., Q\) )
  • \((a_i, b_i, c_i) \neq (a_j, b_j, c_j)\) ( \(i \neq j\) のとき)
  • \(1 \leq d_i \leq 10^5\) ( \(i = 1, 2, ..., Q\) )

問題の考察

ACコード

import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m, q = list(map(int, readline().split()))
    ad = [list(map(int, readline().split())) for _ in range(q)]
    mx = 0
    for v in itertools.combinations_with_replacement(range(1, m + 1), n):
        total = 0
        for i in range(q):
            total += ad[i][3] if v[ad[i][1] - 1] - v[ad[i][0] - 1] == ad[i][2] else 0
        mx = max(mx, total)
    print(mx)


if __name__ == '__main__':
    solve()

-Edit