Magicode logo
Magicode
0
10 min read

DPまとめコンテスト(EDPC)全部通す。(M, N, O, P)

はじめに

ABC261 で自分に DP 力が足りていない事に気づいたので、EDPC を一通りやります。解説 AC ありありです。
競プロフレンズさんの解説 がとても素晴らしいので、
私の解説は不要・・・だとは思いますが、Python 実装と私が自分で理解できるように競プロフレンズさんの解説を噛み砕いた部分が誰かの役に立つと信じてこの記事を書きます。

この記事では M, N, O, P を解説します。

N - Slimes

競プロフレンズさんの解説 (EDPC解説 M~T (応用編))

考察

  • N <= 400 なので、O(N^2) くらいであれば通る
  • 合体の回数は必ず N-1 回
    • 「合体させる」というのは「まだ指定していないスライムとスライムの間を指定して、その両側のスライムをくっつける」という動作。
    • 「全てのスライムを合体させる」というのは ↑ の動作を全てのスライムとスライムの間に対して行うこと。
  • コストの最小値が聞かれているので、当然スライムをくっつける順番によってコストが変わる
    • 例えば N = 3 の時、a1, a2, a3 のスライムをくっ付ける時、((a1, a2), a3) の順番でくっ付けると、(a1+a2) + ((a1+a2) + a3) = 2*a1 + 2*a2 + a3 のコストがかかる。
      • a1 と a2 が 2 回、a3 が 1 回と、それぞれ重みが変わることがわかる。
    • より大きい ai にかかる重みが小さくするようにしたい。=> 大きい ai が含まれるスライムが結合される回数を少なくすると良さそう。
  • 上記のコスト計算をする時に、合体順序を表す ((a1, a2), a3) という表記が現れたが、これが示唆的
    • 全体のコストは、<a1 と a2 が合体したスライムと a3 を合体させるコスト> + <a1 と a2 を合体させるコスト> になる。
    • もっと数を増やして、N = 5、(((a1, a2), a3), (a4, a5)) を結合する時は下図のような感じになる。
    • ここで注目したいのが、((a1, a2), a3)(a4, a5) の部分のコストは他の区間から独立していて、それぞれ独立して考えられるということである。
    • いわゆる区間 DP というものを使えば良さそう。
  • 区間 DP を考える。
    • 半開区間 l, r に含まれるスライムを結合するコストを cost(l, r) と表すと、cost(l, r) = cost(l, n) + cost(n, r) + sum(A[l:r]) と書ける。(ここで n は l+1 ~ r-1 の値をとる)
    • sum(A[l:r]) は l, r 毎に固定値なので、cost(l, r) を最小化したいのであれば cost(l, n) + cost(n, r) が最小となる n を見つければ良い。
    • なので、cost(l, r) = min(cost(l, n) + cost(n, r) for n in range(l+1, r)) + sum(A[l:r]) を再帰的に計算すれば良さそう。
    • n の総当たりで間に合うか? => 間に合う。メモ化再帰を行えばざっくり N^2 回程度の計算しか行わないはず。
      • 競プロフレンズさんの解説だと O(N^3) だった。計算量について考える。
      • l, r の選び方は N*(N-1)/2 (O(N^2))
      • l, r を選んだ時に、cost(l, n) + cost(n, r) が最小となる n を見つける計算が O(N)
      • 全体で O(N^3)

実装

def resolve():
  from itertools import accumulate # 累積和作るやつ
  N = int(input())
  A = [int(x) for x in input().split(" ")]

  # accA : A の累積和
  # 考察に書いてある sum(A[l:r]) を毎回行うのは無駄なので、累積和を取って O(1) で区間和を出せるようにしておく。
  accA = [0] + [x for x in accumulate(A)]

  # memo[l][r] := 区間 l, r のコストの最小値
  # メモ化再帰をするために使う。(みなさんが変数名をどうしているか気になるのでコメントで教えていただけるとありがたいです。)
  memo = [[None]*(N+1) for _ in range(N)]
  def cost(l, r):
    # r-l == 1 というのは区間の長さが 1、つまりスライムが一匹だけしかいないので合体できない => コスト 0 を返す
    if r-l == 1:
      return 0
    # 再帰で区間 l, r のコストを求める。
    if memo[l][r] is None:
      memo[l][r] = min(cost(l, n) + cost(n, r) for n in range(l+1, r)) + accA[r] - accA[l]
    return memo[l][r]

  print(cost(0, N))

resolve()

O - Matching

競プロフレンズさんの解説 (EDPC解説 M~T (応用編))

解説 AC です。

考察

  • N の制約を見ると、N <= 21 でとても小さいのでそれを利用しそう。
  • 「10^9 + 7 で割った余りを求めてください」と書いてあるので愚直に探索すると間に合わない。
    • 例えば、N 人の女性を一列に並ばせる時、その組み合わせは N! 通りある。
    • この N! の組み合わせを列挙して、列の 1 番目女性は 1 番目の男性と、列の 2 番目の女性は 2 番目の男性と... とペアを作っていく。
    • 最終的に全てのペアの相性が良い組み合わせを数える
    • 以上の計算には O(N*(N!)) の計算量がかかり、今回の制約だと間に合わない。(N <= 9 とかならギリ間に合うかも)
  • DP を使った解法を考える。(競プロフレンズさんの解説を参考に書きます)
    • 最終的に欲しいのは組み合わせが何通りあるか?であって、誰と誰がペアになったのか?という情報は必要ない。
    • こういった問題で良くあるのが、状態を bit で持って遷移していくDP(いわゆる bit DP )
    • ある男性とペアにする女性を選ぶ時、まだペアになっていない女性から選ぶ必要がある => 既にペアになっている女性を状態として持っておけば良い
    • 相性が以下のようになるとき、遷移は下図のようになる。
    • 遷移できるかどうかは相性に依存する。

実装

def resolve():
  popcnt = lambda x: bin(x).count("1")

  # N の最大値がとても小さいのでこれを利用する。
  inf = 10**18+1
  mod = 10**9+7
  N = int(input())
  A = [[int(x) for x in input().split(" ")] for _ in range(N)]
  # MATCHES[i]: i 番目の男性と相性の良い女性の index
  MATCHES = [[j for j in range(N) if A[i][j] == 1] for i in range(N)]

  # dp[i] := i を二進数で考えた時に x 桁目が 1 の場合に x 番目の女性の相手が既に決まっている時の組み合わせの数
  # ex : i == 0b01001 の時、 [1, 4] 番目の女性は既に相手が決まっていて、[2, 3, 5] 番目の女性はまだ相手が決まっていない。
  dp = [0]*(1<<N)
  dp[0] = 1

  for s in range((1<<N)-1):
    # i: 何番目の男性を見るか?を表すインデックス
    # popcnt(s) は既に相手が決まっている女性の人数。
    # 0-index で考えて popcnt(s) 番目の男性を見るようにする。
    i = popcnt(s)
    for n in MATCHES[i]:
      # n 番目の女性のお相手が既に決まっている場合、遷移できない。
      if s&(1<<n): continue

      # n 番目の女性と i 番目の男性をマッチさせた時、状態は s|(1<<n) になるので、そこに遷移する。
      j = s|(1<<n)
      dp[j] += dp[s]
      if dp[j] >= mod: dp[j]%=mod

  print(dp[-1]%mod)

resolve()

P - Independent Set

競プロフレンズさんの解説 (EDPC解説 M~T (応用編))
自力 AC できたんですが、どういう思考で辿り着いたかの説明が難しいです・・・

考察

ダメだった考察

  • 色塗りの基本、端から塗っていってみよう。DFS or BFS で解けそう。

    • ある頂点を見た時にその頂点が白ならば、次の頂点は白 or 黒。
    • ある頂点を見た時にその頂点が黒ならば、次の頂点は白のみ。
    • 各頂点に「その頂点が白の場合数」と「その頂点が黒の場合数」を持って、次の頂点に遷移する時に白の場合数から白と黒、黒の場合数から白に遷移すれば良さそう。
  • この考え方はサンプル 1 のように分岐しないパターンであれば解が一致する

  • ただし、サンプル 2 のように分岐があるパターンで間違った答えを出す。

正しい答えを出せた考察

  • サンプル 2 を観察する。
  • 頂点 2 が白のケースが 5 パターン、黒のケースが 4 パターンある。
    • さらに見ていくと、頂点 2 が白かつ、頂点 1 が黒のケースが 1 パターン、頂点 2 が白かつ、頂点 1 が白のケースが 4 パターンある。
    • 頂点 2 が黒の場合、当然ながら頂点 1 は 4 つ全てのケースで白。
    • 頂点 2 を存在しないものとして、重複を考慮に入れると、頂点 1 が白の時、頂点 3 と 4 は自由に決めれるので、2*2 = 4 パターン
    • 頂点 1 が黒の時、頂点 3 と 4 は白固定なので 1 パターン
    • 「親のパターン数は子のパターン数に依存している」と考えると解けるかも?
  • 親のパターン数は、白の時 = 子のとりうるパターン数全て。黒の時 = 子が全て黒のパターン数
    • 葉は白 1 パターン、黒 1 パターンの合計 2 パターンを持ってると考える。

実装

def resolve():
  from collections import deque
  mod = 10**9+7
  N = int(input())

  # EDGES[n]: 頂点 n に繋がっている頂点
  EDGES = [[] for _ in range(N)]
  for _ in range(N-1):
    x, y = [int(x)-1 for x in input().split(" ")]
    EDGES[x].append(y)
    EDGES[y].append(x)

  # checked[n]: 頂点 n が既にチェックされているかどうか
  checked = [False]*N
  checked[0] = True

  # parents[n]: 頂点 n の親。根の親は -1 になる。
  parents = [-1]*N

  # dp[n][c] := 頂点 n が c 色のケースのパターン数
  dp = [[1, 1] for _ in range(N)]

  # DFS をやっていく。
  # 帰り道で子の状態から白、黒のそれぞれのパターン数を計算する。
  que = deque([~0, 0])
  while que:
    current = que.pop()
    if current < 0:
      current = ~current
      for n in EDGES[current]:
        # 子だけを見るので、親ノードだった場合はスキップする。
        if n == parents[current]: continue

        # dp[current][0]: 頂点 current が白色のパターン数。子がどの色でも良い => 子のパターンを全て掛け合わせる。
        dp[current][0] *= sum(dp[n])

        # dp[current][1]: 頂点 current が黒色のパターン数。子全て黒である必要がある。 => 子が黒のパターンを掛け合わせる。
        dp[current][1] *= dp[n][0]

        if dp[current][0] >= mod: dp[current][0]%=mod
        if dp[current][1] >= mod: dp[current][1]%=mod
      continue
    for n in EDGES[current]:
      if checked[n]: continue
      checked[n] = True
      parents[n] = current
      que.append(~n)
      que.append(n)

  print(sum(dp[0])%mod)

resolve()

Discussion

コメントにはログインが必要です。