[AtCoder] ABC165C Personal Note [Python]

ABC165 C - Many Requirements

The possible sequence A is fully searched by dfs, and the maximum value of the score is obtained. Show two sample answers

--Answer example 1-Implementing dfs with a recursive function --calc function A function that calculates the score from the sequence A

--dfs function A function that finds the maximum score while searching all possible sequences A by dfs. If the length of the sequence A is N, the score is calculated, then compared with the highest score so far, and the highest score is recorded. If the length is less than that, add one element and recurse so as to satisfy the constraint of sequence A. Recursive by adding $ x = 1 $ if A is an empty list, otherwise $ x $ of $ A [-1] \ leqq x \ leqq M $ to A

main.py

    #!/usr/bin/env python3
    def main():
        import sys

        def calc(A: list):
            score = 0
            for a, b, c, d in lst:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            return score

        def dfs(A: list):
            nonlocal ans
            if len(A) == N:
                ans = max(ans, calc(A))
                return
            for v in range(A[-1] if A else 1, M + 1):
                A.append(v)
                dfs(A)
                A.pop()

        input = sys.stdin.readline

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

        ans = 0
        dfs([])
        print(ans)


    main()

--Answer example 2- itertools.combinations_with_replacement (iterable, r) Search the sequence A completely using itertools.combinations_with_replacement According to the official documentation, itertools.combinations_with_replacement (iterable, r) tuples a subsequence of elements of length r from the input iterable, allowing each element to appear multiple times.

test.py

  # itertools.combinations_with_replacement(iterable, r)Usage example
  from itertools import combinations_with_replacement

  for pattern in combinations_with_replacement('ABCD', 2):
      print(pattern, end='')
  
  # AA AB AC AD BB BC BD CC CD DD

Using the above function, the answer can be written as:

main.py

    #!/usr/bin/env python3
    def main():
        import sys
        from itertools import combinations_with_replacement

        input = sys.stdin.readline

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

        ans = 0
        for pattern in combinations_with_replacement(range(1, M + 1), N):
            res = 0
            pattern = list(pattern)
            for a, b, c, d in lst:
                if pattern[b - 1] - pattern[a - 1] == c:
                    res += d
            ans = max(ans, res)

        print(ans)


    main()

Reference URL

--Atto TECH LOG ABC165 C - Many Requirements
https://at274.hatenablog.com/entry/2020/05/20/213705 --Kenchon's competition professional devotion record How to write a recursive function that you often do ~ Mechanically n-fold for statement ~ https://drken1215.hatenablog.com/entry/2020/05/04/190252 --Python 3.8.5 documentation Iterator generation function for efficient loop execution https://docs.python.org/ja/3/library/itertools.html#itertools.combinations_with_replacement