Educational DP Contest N,O,P,Q,Rメモ

N - Slimes

問題

  • $N$ 匹のスライムが横一列に並ぶ
  • 最初の大きさは左から $a_1,a_2,\ldots,a_N$
  • 隣り合う2匹を合成することを繰り返して、1つにまとめる
  • 合成する時、2匹のその時点の大きさの和のコストがかかる
  • 最小コストを求めよ
  • $1 \le N \le 400$

解法

区間DP。ループ回数は多め。

データ

$DP[l][r]=$初期状態で左から $[l, r)$ の区間のスライムを1匹に合成する最小コスト

初期条件

全て0

遷移

例えば$[2, 7)$の区間のスライムを1匹に合成するには、その直前で、$[2,x)$ と $[x,7)$ の2匹に分かれていないといけない。($x$は$3~6$の任意の数)

逆に、$[2,x)$ や $[x,7)$ がどう合成されたものであろうが、それぞれのコストの最小値さえわかっていれば、$[2,7)$ の合成コストは求められる。

この$x$を全て試し、最小を取るとよい。

$DP[l][r]=\min_{l+1 \le x \le r-1}(DP[l][x]+DP[x][r])+([l,r)のスライムの大きさ合計)$

大きさの合計は、最初に累積和$acc$を取っておけば、$acc[r-1]-acc[l-1]$ で求められる。

from itertools import accumulate

n = int(input())
acc = [0] + list(accumulate(map(int, input().split())))
dp = [[0] * (n + 1) for _ in range(n)]
for w in range(2, n + 1):
    for l in range(n - w + 1):
        r = l + w
        dp[l][r] = min(dp[l][m] + dp[m][r] for m in range(l + 1, r)) + acc[r] - acc[l]
print(dp[0][n])

O - Matching

問題

  • $N$ 人の男と $N$ 人の女
  • 相性は $N \times N$ 行列で示される
    • $A_{i,j}=1$ なら$i$ 番目の男と $j$ 番目の女が好相性、0なら相性なし
  • 好相性同士で $N$ 組のペアを作る時、組み方は何通りあるか
  • $1 \le N \le 21$

解法

bitDP。集合をビットフラグで表し、0から積み上げて $2^N$ 通りの集合の値を計算する。

データ

$DP[i][s]=i$ 番目までの男たちが、集合 $s$ で示される女たちとペアになるパターン数

初期条件

$DP[0][0]=1$

遷移

$i-1$ 番目の男まで計算済みとする。

$i$ 番目の男と $j$ 番目の女が好相性の時、

$DP[i-1]$ の中で、まだ $女_j$ が含まれていない集合 $s$ に対して、$DP[i][s|女_j] += DP[i-1][s]$ と遷移する。

たとえば $j=5$ とすると、下から5番目だけ立ったビットフラグ$b=10000$を用意して、

  • 集合 $s=11000$ に対しては、既に5番目のbitが立っている($女_5$ が既に他の男とペアになっている)ので何もしない
  • 集合 $s=00101$ に対しては、ペアが1組作れるので、$DP[i][10101] += DP[i-1][00101]$ と加算する

…という処理を、$DP[i-1]$ に含まれる各 $s$ について行っていく。

計算量

$i$ から $i+1$ への遷移で必要なのは、ビットフラグ $s$ の $N$ 本のビットのうち、立っているのがちょうど $i$ 本のもののみ。 (男が $i$ 人なので、女も同数のもののみ考慮すればよい) そのようなビットは、$\displaystyle {}_NC_{i}$ 通りある。

「立っているのがちょうど$k$本のビットフラグのみのイテレート」はやりにくく、結局は $0~2^N$ を回して条件に合う物のみ処理するのが単純だし早い。 ただ、この問題の場合「立っているのがちょうど$i$本のビットフラグ」は、$i-1$ から $i$ への遷移の際に新しく作られた $s$ に他ならない。 これを記録しておくことで、$DP[i+1]$ の計算時に過不足のないイテレートが可能となる。 代わりに記録するコストがかかるので、言語によっては却って遅くなるかも知れないが……。

ともかく、$\displaystyle {}_NC_{i}$ 通りのそれぞれで、$男_i$ と相性のよい女(最大 $N$人)の遷移を行うので、全体での計算量は

$\displaystyle \sum_{i=0..N-1} N \times {}_NC_{i}$ となる。これは、$N=21$ で約 $4.4 \times 10^7$ となる。

n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for i in range(n):
    compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
    nxt = set()
    for k in curr:
        p = dp[k] % MOD
        for c in compatibilities:
            if k & c:
                continue
            dp[k | c] += p
            nxt.add(k | c)
    curr = nxt
print(dp[(1 << n) - 1] % MOD)

P - Independent Set

問題

  • $N$ 頂点の木を、白か黒に塗り分ける
  • 辺で直接結ばれた2頂点を同時に黒で塗ってはいけない
  • 塗り方は何通りか、$\mod{10^9+7}$ で求めよ

解法

木DP。適当な頂点を根として、部分木の解を求めていく。

どの頂点から先に計算すれば良いかわかりづらいので、再帰関数で書くのがやりやすい。

一応、DFSで計算順序を求め、その順にDP配列を埋めていくやり方でボトムアップでも可能。PyPyは再帰が遅いので、PyPyの速度が必要な場合はそのようなやり方をする。

データ

$DP[i][w]=$頂点1と根とした時、頂点 $i$ 以下の部分木で、頂点 $i$ 自身の色が$w=白/黒$だった場合のパターン数

$DP[1]$ を再帰で求める

初期条件(末端条件?)

葉のパターン数: (白,黒) = (1,1)

遷移

頂点 $i$ を黒にするには、子供が全部白でなくてはならない。逆に頂点 $i$ が白なら、子供は白でも黒でもよい。

\begin{eqnarray} DP[i][白] &=& \prod_{c \in iの子供} (DP[c][白]+DP[c][黒]) \\ DP[i][黒] &=& \prod_{c \in iの子供} DP[c][白] \end{eqnarray}

import sys

sys.setrecursionlimit(100005)
MOD = 1000000007


def dfs(v, a):
    w, b = 1, 1
    for u in links[v]:
        if u == a:
            continue
        cw, cb = dfs(u, v)
        w *= cw + cb
        b *= cw
        w %= MOD
        b %= MOD
    return w, b


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)

print(sum(dfs(0, None)) % MOD)

Q - Flowers

問題

  • $N$ 本の花が横1列に並ぶ
  • 花の高さは左から $h_1,h_2,\ldots,h_N$ で、これは $\{1,2,\ldots,N\}$ を並び替えたものである
    • つまり、$1~N$ の高さの花が1本ずつある
  • 花の価値は、左から $a_1,a_2,\ldots,a_N$
  • 何本かの花を摘み取り、左から高さが単調増加になるようにしたい
  • 残る花の価値を最大化せよ

解法

セグメント木上でのDP

データ

$DP[i]=$左から $1~i$ 本目までの花だけを考慮し、$i$ 番目の花は必ず残す場合の、残る花の価値の最大値

セグメント木上で実装し、更新・取得をそれぞれ $\log{N}$ で行えるようにする

  • 更新(i, x): DP[i] を xにする
  • 取得(i): DP[1]~DP[i] の最大値を取得する

初期条件

全て0

遷移

$DP[i-1]$ まで確定して、$i$ 番目の花を残すときを考える。

この時、「左から $1~i-1$ 番目に位置し、かつ $h_i$ より低い高さである花のうち、$DP[j]$ が最大のもの」に、$a_i$ を加えたものが $DP[i]$ となる。

                    ↓いまここ
     1   2   3   4   5   6
 h   1   5   3   6   4   2
 a  10  20  30  40  50  60
DP  10  30  40  70

$i=5$ より左にあり、$h_5=4$ より低い花の中で、$DP$ が最大のものは、$DP[3]=40$。よって、$DP[5]=40+50=90$ となる。(花1,3,5を残す時にこれが実現できる) 4より高い花が左にあると置けなくなってしまうので、自分より低い花の中から最大値を探すことになる。

位置と高さを両方考えるのはややこしいので、事前に$h_i$でソートしておき、低い方から処理していくと、高さは無視できる。 花 $i$ を処理時点での $DP$ の値は必ず$h_i$ より低い花のみを考慮した値となっている。

                    ↓いまここ
     1   2   3   4   5   6
 h   1   5   3   6   4   2
 a  10  20  30  40  50  60
DP  10      40          70

セグメント木に対する更新は点更新、取得は必ず$[1, k)$ の形となるので、簡略化した形で書ける

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        while i >= 0:
            if data[i] < x:
                data[i] = x
            else:
                break
            i = (i - 1) // 2

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            # 自身が右枝の場合のみ、左枝と比較
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))

R - Walk

問題

  • $N$ 頂点の単純有向グラフ
  • 辺の有無は行列の形で与えられる
    • $1 \le i,j \le N$ について、$a_{i,j}=1$ なら $i→j$ の辺が存在し、0なら存在しない
  • 長さ $K$ の有効パスは何通りあるか求めよ
    • 同じ辺を複数回通ってもよい
  • $1 \le N \le 50$
  • $1 \le K \le 10^{18}$

解法

行列累乗

データ

現在考慮中のパス長が $k$ として、

$DP[i][j]=$ 頂点$i$から$j$ へ、パス長がちょうど $k$ の行き方の通り数

初期条件

全て0

遷移

有向グラフの経路パターン数は、辺の有無を0-1行列にし、累乗することで算出できる。

①-->②<->③
 <------->

        1 2 3
     1| 0 1 1
A^1  2| 0 0 1
     3| 1 1 0

     1| 1 1 1
A^2  2| 1 1 0
     3| 0 1 2

     1| 1 2 2
A^3  2| 0 1 2
     3| 2 2 1

$A^3_{1,2}$ を例に取ると、

  • $A^1$ より、
    • 1→1 への長さ1の経路が0通り(A)
    • 1→2 への長さ1の経路が1通り(B)
    • 1→3 への長さ1の経路が1通り(C)
  • $A^2$ より、
    • 1→2 への長さ2の経路が1通り(A)
    • 2→2 への長さ2の経路が1通り(B)
    • 3→2 への長さ2の経路が1通り(C)

(A)(B)(C) それぞれ同士を掛け合わせて合計すればよいが、この計算が行列の積算と一致する。

$A^3_{1,2} = A^1_{1,1}A^2_{1,2}+A^1_{1,2}A^2_{2,2}+A^1_{1,3}A^2_{3,2} = 2$

ただし、行列の積算は1回に $N^3$ かかり、とても$10^{18}$回は計算できない。 繰り返し二乗法を用いると、計算回数を $\log{10^{18}}$ に減らせる。

行列演算ならNumPyを使いたくなるが、オーバーフローするのかWAになる。以外と競プロでNumPy使う機会って無い。

def dot(a, b):
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ret[i][j] = sum(a[i][k] * b[k][j] for k in range(n)) % MOD
    return ret


n, k = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(n)]
ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1
MOD = 1000000007
while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, dp)
    dp = dot(dp, dp)
print(sum(sum(a) % MOD for a in ans) % MOD)

programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2.txt · 最終更新: 2019/01/17 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0