Posted by 概要
本記事は、AtCoderのABC165に参加した際に回答することができなかったの問題を解説を読んで理解した内容を記載します。C問題で回答できなかったのは久しぶりだったので、しっかりと復習したいと思います。
問題
C – Many Requirements
https://atcoder.jp/contests/abc165/tasks/abc165_c
解説
https://img.atcoder.jp/abc165/editorial.pdf
動画(Youtube)
理解
まず計算量を考える部分ですが、数の組み合わせですが等しい数も選択することができるので、玉を並べてそれらに仕切りを置くようなイメージで算出します。具体的にはN個の仕切りとM-1個の玉からN個を選択するときの組み合わせが総数となります。なので、N+M-1 Choose N となり、今回の最大数は19 Choose 9なので92378通りで全探索でも問題ない処理量と考えられます。
次に全探索のdfs関数についてですが、全探索を考えるときのポイントは以下の2つです。
- 一回のステップでどんな処理をすることで次につなげられるか
- 終了条件をどうするか
今回の実装では、一回の実行ではリストの最後の値をリストに追加する処理を行います。終了条件はリストの長さがNとなると時で、そこでそのリストでの値を計算してmaxをとります。
実装
import copy
N, M, Q = map(int, input().split())
Qj = [list(map(int, input().split())) for i in range(Q)]
ans = 0
def dfs(Aj):
global ans
if len(Aj) == N:
now = 0
for Q in Qj:
if Aj[Q[1]-1] - Aj[Q[0]-1] == Q[2]:
now += Q[3]
ans = max(ans, now)
return;
if len(Aj) == 0:
Aj.append(1)
else:
Aj.append(Aj[-1])
while Aj[-1] <= M:
dfs(copy.deepcopy(Aj))
Aj[-1] += 1
Aj = []
dfs(Aj)
print(ans)