ABC165 C - Many Requirements
考えられる数列Aをdfsによって全探索し，得点の最大値を求める．
解答例を2つ示す
-
解答例1-dfsを再帰関数で実装
- calc関数
数列Aから得点の計算をする関数
- dfs関数
考えられる数列Aをdfsによって全探索しつつ，得点の最大値を求める関数
数列Aの長さがNなら得点を計算した後，今までの最高得点と比較，最高得点を記録
それ以下の長さなら，数列Aの制約を満たす様に要素を1つ追加して再帰
Aが空リストなら$x=1$を，それ以外なら$A[-1]\leqq x\leqq M$の$x$をAに追加して再帰
- calc関数
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()
- 解答例2-itertools.combinations_with_replacement(iterable, r)
itertools.combinations_with_replacementをつかって，数列Aを全探索する
公式ドキュメントによると，itertools.combinations_with_replacement(iterable, r)は，入力iterableから，それぞれの要素が複数回現れることを許して長さrの要素の部分列をタプルで返す
test.py
# itertools.combinations_with_replacement(iterable, r)の使用例
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
上記の関数を用いると，解答は以下の様に書ける
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()
参考URL
- あっとのTECH LOG
ABC165 C - Many Requirements
https://at274.hatenablog.com/entry/2020/05/20/213705 - けんちょんの競プロ精進記録
よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜
https://drken1215.hatenablog.com/entry/2020/05/04/190252 - Python 3.8.5 ドキュメント
効率的なループ実行のためのイテレータ生成関数
https://docs.python.org/ja/3/library/itertools.html#itertools.combinations_with_replacement