C - Many Requirements

[hxrxchang]

https://atcoder.jp/contests/abc165/tasks/abc165_c

問題概要

• 長さNで、各項が1~M の単調増加列を作れ。
• ただし、Q個ある入力である (a, b, c, d) について、A[b] - A[a] == c となると得点dがもらえる。得点の合計を最大化できるAを考えよ。

ダメ解法

一瞬dが大きい順に並べ替えて、決めていけばいいのでは？と考えたが当然だめ。 a[i], b[i]は重複する可能性があるので、同じ値となるa[i], b[i]が複数あると逆転することがあり得る。

解法

数列Aを全列挙して、各数列の得点を計算して最大のものが分かればいい。 数列Aは単調増加列なので、全列挙したときのパターンは M ** N ではなく、M+N-1 choose N になる。 https://chat.openai.com/share/9f8a2824-c67c-4c9e-a655-f2d1f872d065

pythonだと itertools.combinations_with_replacement で単調増加列を列挙できる。 https://docs.python.org/ja/3/library/itertools.html#itertools.combinations_with_replacement

from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())

conditions = [list(map(int, input().split())) for _ in range(Q)]

sequences = list(combinations_with_replacement(range(1, M + 1), N))

ans = 0
for s in sequences:
    score = 0
    for a, b, c, d in conditions:
        if s[b - 1] - s[a - 1] == c:
            score += d
    ans = max(ans, score)

print(ans)

https://atcoder.jp/contests/abc165/submissions/52158972