Branched Evolution

Competitive Programming in Python

AtCoder DP まとめコンテストまとめ（A~V）

動的計画法

Educational DP Contest / DP まとめコンテストの問題を解いていく。

A - Frog 1
B - Frog 2
C - Vacation
D - Knapsack 1
E - Knapsack 2
F - LCS
G - Longest Path
H - Grid 1
I - Coins
J - Sushi
K - Stones
L - Deque
M - Candies
N - Slimes
O - Matching
P - Independent Set
Q - Flowers
R - Walk
S - Digit Sum
T - Permutation
U - Grouping
V - Subtree

A - Frog 1

$i$ 番の足場に行くには $i - 1$ 番から行く場合と $i - 2$ 番から行く場合があり小さい方を選択する。
したがって、$DP[i]$ を $i$ 番の足場までのコストの最小値とすると、 $$ \begin{aligned} DP[i] = \mathrm{min} \{ & DP[i-2] + | H _ {i} - H _ {i - 2} |, \\ & DP[i-1] + | H _ {i} - H _ {i - 1} | \} \end{aligned} $$

提出コード

n = int(input())
*H, = map(int, input().split())
DP = [0 for i in range(n)]
DP[1] = abs(H[0]-H[1])
for i in range(2, n):
    DP[i] = min(DP[i-2]+abs(H[i]-H[i-2]), DP[i-1]+abs(H[i]-H[i-1]))
print(DP[n-1])

B - Frog 2

$i$ 番の足場に行くには $i - 1,\ldots, i - k$ 番から行く場合がありその中で最小のものを選択する。
したがって、$DP[i]$ を$i$ 番の足場までのコストの最小値とすると、 $$ DP[i] = \mathrm{min} \{ DP[i - j] + | H _ {i} - H _ {i - j} | \mid j = 1,\ldots,\mathrm{min} \{i,k\} \} $$

提出コード

n, k = map(int, input().split())
*H, = map(int, input().split())
DP = [0 for i in range(n)]
for i in range(1, n):
    DP[i] = min([DP[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(i, k)+1)])
print(DP[n-1])

C - Vacation

$i$ 番目で $A$ を選んだ場合の最大値は「 $i-1$ 番目で $A$ 以外を選んだ場合の最大値」 $+$ 「$i$ 番目の $A$ の幸福度」であるので、$i$ 番目で $A,B,C$を選んだ場合の最大値をそれぞれ $DP[i][0],DP[i][1],DP[i][2]$ とすると、 $$ \begin{aligned} DP[i][0] &= \mathrm{max} \{ DP[i - 1][1],DP[i - 1][2] \} + A _ {i}\\ DP[i][1] &= \mathrm{max} \{ DP[i - 1][2],DP[i - 1][0] \} + B _ {i}\\ DP[i][2] &= \mathrm{max} \{ DP[i - 1][0],DP[i - 1][1] \} + C _ {i} \end{aligned} $$ 提出コード

n = int(input())
ABC = [tuple(map(int, input().split())) for i in range(n)]
A = [a for a, b, c in ABC]
B = [b for a, b, c in ABC]
C = [c for a, b, c in ABC]
DP = [[0 for j in range(3)] for i in range(n+1)]
for i in range(1, n+1):
    DP[i][0] = max(DP[i-1][1], DP[i-1][2])+A[i-1]
    DP[i][1] = max(DP[i-1][2], DP[i-1][0])+B[i-1]
    DP[i][2] = max(DP[i-1][0], DP[i-1][1])+C[i-1]
print(max(DP[n]))

D - Knapsack 1

最初の $i$ 個を使って容量 $j$ 以内で最大価値を得るには、 $i$ 個目の重さを $w$ とすると、「$i$ 個目を使って $i - 1$ 個を容量 $j - w$ で最適化する場合」と「$i$ 個目を使わず $i - 1$ 個を容量 $j$ で最適化する場合」の価値が大きくなる方を選べばよい。
最初の $i$ 個を使って容量 $j$ 以内で得る最大価値を $DP[i][j]$ とすると、
$j < W _ {i - 1}$ の場合 $$ DP[i][j] = DP[i - 1][j] $$ $j \geq W _ {i - 1}$ の場合 $$ DP[i][j] = \mathrm{max} \{ DP[i - 1][j], DP[i - 1][j - W _ {i - 1}] + V _ {i - 1} \} $$

提出コード

n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
DP = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(W[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(W[i-1], m+1):
        DP[i][j] = max(DP[i-1][j], DP[i-1][j-W[i-1]]+V[i-1])
print(DP[n][m])

E - Knapsack 2

D問題とまったく同じ問題だが、制約が異なる。最初の $i$ 個を使って価値 $j$ 以上を得るのに必要な最小の容量を $DP[i][j]$ とすると、$n$ 個全部使って容量 $ m $ 以内で得られる価値の最大値は $DP[n][j] \leq m $ をみたす最大の $j$ である。
$j < V _ {i - 1}$ の場合 $$ DP[i][j] = DP[i - 1][j] $$ $j \geq V _ {i - 1}$ の場合 $$ DP[i][j] = \mathrm{min} \{ DP[i - 1][j], DP[i - 1][j - V _ {i - 1}] + W _ {i - 1} \} $$

提出コード

n, m = map(int, input().split())
WV = [tuple(map(int, input().split())) for i in range(n)]
W = [w for w, v in WV]
V = [v for w, v in WV]
inf = 10**10
sumV = sum(V)
DP = [[inf for j in range(sumV+1)] for i in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    for j in range(V[i-1]):
        DP[i][j] = DP[i-1][j]
    for j in range(V[i-1], sumV+1):
        DP[i][j] = min(DP[i-1][j], DP[i-1][j-V[i-1]]+W[i-1])
for j in range(sumV, 0, -1):
    if DP[n][j] <= m:
        print(j)
        exit()

F - LCS

まず最長共通部分列の長さを求めてから、復元する。
$S[:i]$ と $T[:j]$ の最長共通部分列の長さを $DP[i][j]$ とする。
$S[i - 1] = T[i - 1]$ の場合 $$ DP[i][j] = DP[i - 1][j - 1] + 1 $$ $S[i - 1] \neq T[i - 1]$ の場合 $$ DP[i][j] = \mathrm{max} \{ DP[i][i - 1], DP[i -1][j] \} $$ $DP[m][n]$ を求めたあと、遷移を逆順に辿ることで最長共通部分列を復元することができる。

提出コード

S = input()
T = input()
m, n = len(S), len(T)
DP = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if S[i-1] == T[j-1]:
            DP[i][j] = DP[i-1][j-1] + 1
        else:
            DP[i][j] = max(DP[i][j-1], DP[i-1][j])
i, j = m, n
X = ''
while len(X) < DP[m][n]:
    if S[i-1] == T[j-1]:
        X = S[i-1] + X
        i -= 1
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    elif DP[i][j] == DP[i][j]:
        j -= 1
print(X)

G - Longest Path

$i$ を始点とする最長パスの長さを $DP[i]$、$i$ の行き先を$G[i]$ とすると、 $$ DP[i] = \mathrm{max} \{ DP[j] + 1 \mid j \in G[i] \} $$ メモ化再帰で実装した。

提出コード

import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
G = [[] for i in range(n)]
for j in range(m):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
DP = [None for i in range(n)]
def dp(i):
    if DP[i] != None:
        return DP[i]
    ret = 0
    for j in G[i]:
        ret = max(ret, dp(j)+1)
    DP[i] = ret
    return ret
print(max([dp(i) for i in range(n)]))

H - Grid 1

$(i,j)$ への経路の数を $DP[i][j]$ とすると、 $$ DP[i][j] = DP[i -1][j] + DP[i][j -1] $$ ただし、$(i -1,j)$ や $(i, j-1)$ が通れるマスのときだけ足す。

提出コード

h, w = map(int, input().split())
p = 10**9+7
S = [input() for i in range(h)]
DP = [[0 for j in range(w)] for i in range(h)]
DP[0][0] = 1
for i in range(h):
    for j in range(w):
        if i > 0 and S[i-1][j] == '.':
            DP[i][j] += DP[i-1][j]
        if j > 0 and S[i][j-1] == '.':
            DP[i][j] += DP[i][j-1]
        DP[i][j] %= p
print(DP[h-1][w-1])

I - Coins

最初の $i$ 枚中表が $j$ 枚出る確率を $DP[i][j]$ とすると、これは $i - 1$ 枚中 $j -1$枚表が出て $i$ 枚目で表が出る確率と $i - 1$ 枚中 $j$枚表が出て $i$ 枚目で裏が出る確率の和になるので、
$j > 0$ のとき $$ DP[i][j] = DP[i-1][j] \times (1 -P _ {i -1}) + DP[i -1][j -1]\times P _ {i -1} $$ $j = 0$ のとき $$ DP[i][j] = DP[i-1][j] \times (1 -P _ {i -1}) $$

提出コード

n = int(input())
*P, = map(float, input().split())
DP = [[0.0 for j in range(n+1)] for i in range(n+1)]
DP[0][0] = 1.0
for i in range(1, n+1):
    DP[i][0] = DP[i-1][0]*(1-P[i-1])
    for j in range(1, n+1):
        DP[i][j] = DP[i-1][j]*(1-P[i-1])+DP[i-1][j-1]*P[i-1]
print(sum(DP[n][(n+1)//2:]))

J - Sushi

寿司が $3,2,1$ 個乗っている皿の枚数が $i,j,k$ 枚の状態を $(i,j,k)$ と表すと、$(i,j,k)$ からそれぞれ確率 $\displaystyle\frac{n - (i +j+k)}{n},\displaystyle\frac{i}{n},\displaystyle\frac{j}{n},\displaystyle\frac{k}{n}$ で $(i,j,k),(i -1,j +1,k),(i,j -1,k +1),(i,j,k -1)$ に遷移する。遷移時に操作回数の期待値が $1$ 増えるので、$(i,j,k)$ から $(0,0,0)$ へ遷移するための操作回数の期待値を $DP[i][j][k]$ とすると、 $$ \begin{aligned} DP[i][j][k] = 1 &+ DP[i][j][k] \times \left( 1 - \frac{i+j+k}{n} \right) \\ &+ DP[i - 1][j + 1][k] \times \frac{i}{n} \\ &+ DP[i][j - 1][k] \times \frac{j}{n} \\ &+ DP[i][j][k - 1] \times \frac{k}{n} \end{aligned} $$ が成り立つ。これを変形して、 $$ \begin{aligned} DP[i][j][k] = n &+ DP[i - 1][j + 1][k] \times \frac{i}{i+j+k} \\ &+ DP[i][j - 1][k] \times \frac{j}{i+j+k} \\ &+ DP[i][j][k - 1] \times \frac{k}{i+j+k} \end{aligned} $$

提出コード

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(3), A.count(2), A.count(1)
DP = [[[0.0 for k in range(a+b+c+1)] for j in range(a+b+1)] for i in range(a+1)]
for i in range(a+1):
    for j in range(a-i+b+1):
        for k in range(a-i+b-j+c+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            if i > 0:
                DP[i][j][k] += i*DP[i-1][j+1][k]
            if j > 0:
                DP[i][j][k] += j*DP[i][j-1][k+1]
            if k > 0:
                DP[i][j][k] += k*DP[i][j][k-1]
            DP[i][j][k] /= i+j+k
print(DP[a][b][c])

K - Stones

残り $i$ 個から始めた場合に先手が勝つかの真偽値を $DP[i]$ とすると、先手が負ける個数に $A$ の要素を加えた個数なら先手が勝つので、各 $i$ と $a\in A$ について $DP[i]$ が False なら $DP[i + a]$ が True である。

提出コード

n, k = map(int, input().split())
*A, = map(int, input().split())
DP = [False] * (k+1)
for i in range(k+1):
    for a in A:
        if i+a <= k and not DP[i]:
            DP[i+a] = True
if DP[k]:
    print('First')
else:
    print('Second')

L - Deque

$A[i:j]$ を使ったときの解を $DP[i][j]$ とすると、先手が $A[i]$ または $A[j -1]$ を取ったらそこから先手と後手が逆になったゲームがはじまるので、 $$ DP[i][j] = \mathrm{max} \{ A[i] - DP[i +1][j], A[j -1] - DP[i][j -1] \} $$

提出コード

n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        j = i+l
        DP[i][j] = max(A[i]-DP[i+1][j], A[j-1]-DP[i][j-1])
print(DP[0][n])

M - Candies

先頭 $i$ 人で $j$ 個の飴を分け合う場合の数を $DP[i][j]$ とすると、$i$ 人目に配る飴は $0,\ldots,\mathrm{min} \{ j, A _ {i - 1} \}$ 個がありえるから、 $$ DP[i][j] = \sum _ {k=0} ^ { \mathrm{min} \{ j, A _ {i - 1} \}} DP[i - 1][j - k] $$ これを変形して、
$j\leq A _ {i -1}$ のとき $$ DP[i][j] =DP[i -1][j] + DP[i][j -1] - DP[i -1][j -1 - A _ {i -1}] $$ $j > A _ {i -1}$ のとき $$ DP[i][j] =DP[i -1][j] + DP[i][j -1] $$

提出コード

n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9+7
DP = [[None for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
    DP[i][0] = 1
for j in range(1, k+1):
    DP[0][j] = 0
for i in range(1, n+1):
    for j in range(1, k+1):
        DP[i][j] = (DP[i][j-1]+DP[i-1][j]) % p
        if j > A[i-1]:
            DP[i][j] = (DP[i][j]-DP[i-1][j-1-A[i-1]]) % p
print(DP[n][k])

N - Slimes

区間 $[i,j)$ における最小コストを $DP[i][j]$ とすると、$k \in [i+1,j)$ を選んで、$[i,k)$ と $[k,j)$ でそれぞれ最適ににまとめて最後に $2$ つをまとめればよい。最後にまとめるときのコストは$A[i:j)$ の和であるから、あらかじめ累積和をとっておいて $S[j] - S[i]$ を使う。
遷移式は $$ DP[i][j] = \mathrm{min} \{ DP[i][k] + DP[k][j] \mid k \in [i+1,j) \} + \sum _ {k = i} ^ {j - 1} A _ {k} $$

提出コード

n = int(input())
*A, = map(int, input().split())
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if j <= i+1:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = S[j]-S[i]+min([dp(i, k)+dp(k, j) for k in range(i+1, j)])
    return DP[i][j]
print(dp(0, n))

O - Matching

女性の部分集合 $S \subset \{ 0,\ldots,n - 1 \}$ を使ってできる組合せの個数を $DP[S]$、男性 $i$ と相性の良い女性の集合を $A _ i$ とする。このとき $|S|$ 組のペアができるので、 $(|S| -1)$ 番目の男性が $S \cap A _ {|S| -1}$ のどの女性を選ぶかによって分けて考えることで、 $$ DP[S] = \sum _ {i \in S \cap A _ {|S| -1}} DP[S - \{i\} ] $$ 集合を表現するときはビット演算を使う。例えば、$\{0,2,3\}$ は $2 ^ 0 + 2 ^ 2 + 2 ^ 3 = 13$ と表す。

提出コード

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [-1 for s in range(1<<n)]
DP[0] = 1
def dp(s, l):
    if DP[s] != -1:
        return DP[s]
    tmp = 0
    for i in range(n):
        if s & (1<<i) and A[l-1][i]:
            tmp += dp(s & ~(1<<i), l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1<<n)-1, n))

P - Independent Set

頂点 $i$ を白、黒に塗り、$i$ を根とする部分木に対する塗り方の総数をそれぞれ $DP[i][0],DP[i][1]$ とする。$i$ の子の集合を $C _ i$ とすると、親が白なら子は白黒どちらでもよいが、親が黒なら子は白でなければならないから、 $$ \begin{aligned} DP[i][0] &= \prod _ {j \in C _ i} ( DP[j][0] + DP[j][1]) \\ DP[i][1] &= \prod _ {j \in C _ i} DP[j][1] \end{aligned} $$

提出コード

import sys
sys.setrecursionlimit(100000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print((dp(0, 0)+dp(0, 1))%p)

Q - Flowers

花の高さはあらかじめ $1$ 引いておく。左から $i$ 本の花を使って、一番右の花の高さが $j$ であるときの美しさの最大値を $DP[i][j]$ とすると、 $$ \begin{aligned} DP[i][H _ i] &= \mathrm{max} \{ DP[i - 1][j] \mid j = 0,\ldots H _ i - 1 \} \\ DP[i][j] &= DP[i -1][j] \end{aligned} $$ $DP$ は長さ $n$ の配列とし、$i$ ごとに $DP[H _i]$ のみを更新していけばよい。配列の更新と区間内の最大値の取得を $n$ 回行う必要があるので、$DP$ をセグメント木で管理する。

提出コード

class SegmentTree:
    def __init__(self, A, n=18, inf=10**20):
        l = len(A)
        self.size = n
        self.array = [inf]*(2**(n+1)-1)
        for i in range(l):
            self.array[i+2**n-1] = A[i]
        for i in range(2**n-2, -1, -1):
            self.array[i] = max(self.array[2*i+1], self.array[2*i+2])

    def _subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return 0
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_max = self._subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_max = self._subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return max(l_max, r_max)

    def max(self, l, r):
        return self._subquery(l, r, 0, 0, 2**self.size)

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = c
        while tmp > 0:
            tmp = (tmp - 1) // 2
            l = self.array[2 * tmp + 1]
            r = self.array[2 * tmp + 2]
            self.array[tmp] = max(l, r)

n = int(input())
*H, = map(lambda x: int(x)-1, input().split())
*A, = map(int, input().split())
DP = SegmentTree([0]*n)
for i in range(n):
    tmp = DP.max(0, H[i])
    DP.update(H[i], tmp+A[i])
print(DP.max(0, n))

R - Walk

$x$ から $y$ へ行く長さ $k$ のパスが $DP[x][y][k]$ 通りあるとすると、 $$ DP[x][y][k] = \sum _ {z \in P _ y} DP[x][z][k -1] $$ ただし、$ P _ y$ は $y$ への辺が存在する点の集合である。$z \in P _ y$ は $A _ {zy} = 1$ と同値なので、 $$ DP[x][y][k] = \sum _ {z = 0} ^ {n -1} DP[x][z][k -1]\times A _ {zy} $$ と変形できる。また、$DP[x][y][1] = A _ {xy}$ より、 $$ DP[x][y][k] = (A ^ k) _ {xy} $$ が成り立つ。$A ^ k$ は繰り返し二乗法で求められる。

提出コード

def product(A, B):
    C = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = sum([A[i][k]*B[k][j] for k in range(n)]) % p
    return C

def matpow(A, k):
    if k == 1:
        return A
    if k % 2 == 0:
        B = matpow(A, k//2)
        return product(B, B)
    return product(A, matpow(A, k-1))

n, k = map(int, input().split())
p = 10**9+7
A = [list(map(int, input().split())) for i in range(n)]
B = matpow(A, k)
print(sum([sum(B[i]) for i in range(n)]) % p)

S - Digit Sum

$0$ 以上 $n$ 以下で、各桁の和を $d$ で割った余りが $k$ である整数の個数を $DP(n,k)$ とする。$10n+r$ の各桁の和は $ n $ の各桁の和と $r$ を足したものになるので、$10n+r$ の各桁の和を$d$ で割った余りが $k$ になるための必要十分条件は $n$ の各桁の和を$d$ で割った余りと $r-k$ を$d$ で割った余りが等しくなることである。よって、 $$ DP(10n+r,k) = \sum _ {i=0} ^ {r}DP(n,i-k) + \sum _ {i=r + 1} ^ {9}DP(n-1,i - k) $$ が成り立つ。
この式から、$DP(n,k)$ を求めるには $n$ の下 $1$ 桁を除いた数とそこから $1$ 引いた数に対する情報があれば十分であることがわかる。

提出コード

N = [int(n) for n in list(input())]
d = int(input())
p = 10**9+7
DP = [[0]*d, [0]*d]
DP[1][0] = 1
for n in N:
    DP_ = [[0]*d, [0]*d]
    for i in range(2):
        for j in range(d):
            for k in range(n+i):
                DP_[i][j] += DP[1][(j-k) % d] % p
            for k in range(n+i, 10):
                DP_[i][j] += DP[0][(j-k) % d] % p
            DP_[i][j] %= p
    DP = DP_
print((DP[1][0] + p - 1) % p)

T - Permutation

$0$ から $n - 1$ の数字を使って長さ $i$ の配列を作ることを考える。長さ $i$ の配列で、その末尾の数字より大きくて使っていない数字が $j$ 個あるようなものの個数を $DP[i][j]$ とする。
最後の不等号が $<$ のとき、$j = 0,\ldots,n-i$ に対して、長さ $i - 1$ の時点でその末尾の数字より大きくて使っていない数字が $j + 1$ 個以上あれば、残っている数字のうち最小のものを末尾に追加することで、長さ $i$ でその末尾の数字より大きくて使っていない数字が $j$ 個あるような配列を作れるから、 $$ DP[i][j] = \sum _ {k = j + 1} ^ {(n - i) + 1} DP[i -1][k] \ \ (j = 0,\ldots,i - 1 ) $$ 最後の不等号が $>$ のとき、$j = 0,\ldots,n - i$ に対して、長さ $i - 1$ の時点でその末尾の数字より大きくて使っていない数字が $j$ 個以下であれば、残っている数字のうち最大のものを末尾に追加することで、末尾の数字より小さくて使っていない数字が$j$ 個あるような配列を作れるから、 $$ DP[i][j] = \sum _ {k = 0} ^ {j} DP[i -1][k] \ \ (j = 0,\ldots,i - 1 ) $$

提出コード

n = int(input())
S = input()
p = 10**9 + 7
DP = [[0 for j in range(n + 1)] for i in range(n + 1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n + 1):
    A = [0]
    for j in range(n):
        A.append(A[-1] + DP[i - 1][j])
    for j in range(n - i + 1):
        if S[i - 2] == '<':
            DP[i][j] = (A[n - i + 1 + 1] - A[j + 1]) % p
        else:
            DP[i][j] = A[j + 1] % p
print(DP[n][0])

U - Grouping

$S \subset \{0, \ldots , n - 1 \}$ をいくつかのグループに分けて得られる得点の最大値を $DP[S]$ とする。$S$ を $1$ つのグループにする場合と $S$ の空でない部分集合 $T$ をとって $T$ と $S-T$ を分離し、それぞれで最適化する場合の大きい方をとればよいから、$i,j$ の相性を $A _ {ij}$ として、 $$ DP[S] = \mathrm{max} \left \{ \sum _ {i,j \in S} A _ {ij}, \mathrm{max} \{ DP[T] + DP[S - T] \mid T \subsetneq S \} \right \} $$

提出コード

n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
DP = []
for s in range(2**n):
    bit = bin(s)[2:].zfill(n)
    tmp = 0
    for i in range(n):
        for j in range(i + 1, n):
            if bit[i] == '1' and bit[j] == '1':
                tmp += A[i][j]
    DP.append(tmp)
    t = s
    while t:
        DP[s] = max(DP[s], DP[t] + DP[s - t])
        t = (t - 1) & s
print(DP[-1])

V - Subtree

$0$ を根として考えたとき、$x$ を根とする部分木について $x$ が黒であるような色の組合せを $DP _ {0} [x]$ とし、$x$ の子 $y$ に対して辺 $(x,y)$ を除いたときの色の組合せを $DP _ {1} [x][y]$ とする。$x$ の子の集合を $C(x)$ として、 $$ \begin{aligned} DP _ {0} [x] &= \prod _ {y \in C(x)} (1 + DP _ {0} [y]) \\ DP _ {0} [x][y] &= \prod _ {z \in C(x) \setminus \{y\}} (1 + DP _ {0} [z]) \end{aligned} $$ を葉から順に計算し、その後根から順に $x$ の親 $p(x)$ を子として以下のようにマージする。 $$ \begin{aligned} DP _ {0} [x] &\leftarrow DP _ {0} [x] \times (1 + DP _ {1} [p(x)][x]) \\ DP _ {1} [x][y] &\leftarrow DP _ {1} [x][y] \times (1 + DP _ {1} [p(x)][x]) \end{aligned} $$

提出コード

n, m = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    tree[x - 1].append(y - 1)
    tree[y - 1].append(x - 1)
# 0を根とする根付き木にする
child = [[] for _ in range(n)]
parent = [None] * n
order = []
queue = [0]
for x in queue:
    order.append(x)
    for y in tree[x]:
        if y == parent[x]:
            continue
        child[x].append(y)
        parent[y] = x
        queue.append(y)
# 葉から順にx以下の部分木の計算
dp0 = [1] * n
dp1 = [{} for _ in range(n)]
for x in order[::-1]:
    left, right = [1], [1]
    for y in child[x]:
        left.append(left[-1] * (1 + dp0[y]) % m)
    for y in child[x][::-1]:
        right.append(right[-1] * (1 + dp0[y]) % m)
    right.reverse()
    dp0[x] = right[0]
    for i, y in enumerate(child[x]):
        dp1[x][y] = left[i] * right[i + 1] % m
# 根から順にxを根とする場合の計算
for x in order[1:]:
    dp0[x] = dp0[x] * (1 + dp1[parent[x]][x]) % m
    for y in child[x]:
        dp1[x][y] = dp1[x][y] * (1 + dp1[parent[x]][x]) % m
print(*dp0, sep="\n")