【競プロ典型 90 問】032 - AtCoder Ekiden で bitDP を学ぶ

はじめに

競プロ典型 90 問 の032 - AtCoder Ekiden をトライしました. 結果的に解けたのですが, 解説には「bitDP を用いてこの問題を解くこともできます」とありました.

私自身, bitDP を使ったことがなかったので, 練習として bitDP を使った解を考えました.

bitDP で解く

参考にしたのは こちらのサイト です.

方針としては解説にある通り, $dp[S][i]$ を以下の条件での最小値になるようにしています.

• $S$ ; 既に走った人の集合を表す. 例えば全部で 4 人, そのうち (0-indexed で考えて) 選手 0 と 2 が既に走っていれば 0b0101 とします.
• $i$ ; 現時点で最後に走った選手

いわゆる 配る DP の考え方で作っています (多分).

032_AtCoderEkiden_bitDP.py

# 読み込み. 選手と区間は 0-indexed
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
M = int(input())

# 噂情報, friend[i][j] = True → 仲良し, False → 仲悪い
friend = [[True] * N for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x:int(x)-1, input().split())
    friend[x][y] = False
    friend[y][x] = False

# 大きい数
INF = 10**9

# DP
# dp[これまでに走った選手の集合][最後に走った選手] = かかる時間の最小値
# dp[0][j] は使わない
dp = [[INF] * N for _ in range(1<<N)] 

# DP の初期化. 第 0 区間の走者を設定
for i in range(N):
    dp[1<<i][i] = A[i][0]

# print(dp)

# DP の更新 (配る DP)
for cur in range(1, (1<<N)-1):
    interval = bin(cur).count("1") # 現在検討している区間 (0-indexed)

    # 選手 i を加える
    for i in range(N):
        if (cur >> i) & 1: # 既に「状態 cur」に選手 i が加わっている場合
            continue

        nxt = cur | (1<<i) # 「次の状態 nxt」 = 「状態 cur」 に選手 i を加える (ビット or)

        for j in range(N): # 「状態 cur」の末尾が選手 j の場合に対して
            if friend[i][j]: # 選手 i と選手 j が仲良しならば
                # dp[nxt][i] の値を更新する
                #   dp[cur][j] ; 状態 cur の末尾が選手 j の場合の最小値
                #   A[i][interval] ; 選手 i の interval 区間の時間
                dp[nxt][i] = min(dp[nxt][i], dp[cur][j] + A[i][interval])

# 答えを求める
ans = min(dp[(1<<N)-1])
if ans == INF:
    ans = -1

print(ans)

学んだことは次の通り.

• 初期化をきちんとやろう
• 演算子の優先順位 に注意. 例えば (1<<N)-1 のつもりで 1<<N-1 とやると間違える.

全探索で解く

032 - AtCoder Ekiden の解法をネットで調べると, $1 \le N \le 10$ なので, 組み合わせの数は最大 $10! \lt 10^7$ だから全探索でも解けるとあった.

そこで, 素直に全探索でも解いてみた.

032_AtCoderEkiden_zentan.py

import itertools

# 読み込み. 選手と区間は 0-indexed
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
M = int(input())

# 噂情報, friend[i][j] = True → 仲良し, False → 仲悪い
friend = [[True] * N for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x:int(x)-1, input().split())
    friend[x][y] = False
    friend[y][x] = False

# 大きい数
INF = 10**9

# 仮の答え
ans = INF

# 0 ～ N-1 について全ての並び方を調べる
for v in itertools.permutations(range(N)):
    if sum([friend[v[i]][v[i+1]] for i in range(N-1)]) == N-1: # 隣接する人々が全て仲良し (True は 1 と認識)
        t = sum([A[v[i]][i] for i in range(N)]) # ゴールまでにかかる時間
        ans = min(ans, t) # 小さいほうを選択

# INF だったら -1 にする
if ans == INF:
    ans = -1

print(ans)

私が最初に考えた方法

最初に私が考えた方法は,

• 検討中の順番をキューに入れておく
• キューから 1 つ取り出して, 噂情報を使って「次に走れる選手」を探して末尾に足し, キューに戻す
• 選手全員の順番が定まったら, かかる時間を計算する

というもの.

032_AtCoderEkiden_MyAns.py

# 読み込み
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

# R[i] ; 選手 i と仲良しな選手の集合
R = [set(range(N)) for _ in range(N)]
M = int(input())
for _ in range(M):
    X, Y = map(lambda x:int(x)-1, input().split())
    # 仲の悪いメンバを削除
    R[X].discard(Y)
    R[Y].discard(X)

# 大きい数
INF = 10**9

# 仮の答え
ans = INF

# 検討中の順番を格納するキュー (LIFO で運用する)
q = list()

# 第 0 区間の走者をキューに入れる
for i in range(N):
    q.append([i])

while len(q) > 0:
    # キューから取り出す
    c = q.pop()

    if len(c) == N: # 全部の走者が並んでいたら
        t = sum([A[c[i]][i] for i in range(N)]) # ゴールまでの時間を計算
        ans = min(ans, t) # ans を更新
        continue

    for nxt in (R[c[-1]] - set(c)): # 次の走者 = 現時点で最後の走者の仲良し (R[c[-1]]) からすでに走った人 (set(c)) を引く
        q.append(c + [nxt])

# ans == INF なら -1 にする
if ans == INF:
    ans = -1

print(ans)

解法の比較

解法	コード長	実行時間	メモリ	リンク
bitDP	1676 Byte	71 ms	82224 KB	リンク
全探索	901 Byte	1989 ms	83116 KB	リンク
My Answer	1129 Byte	2596 ms	84204 KB	リンク

私の解法は, 遅かったんですね…

おわりに

bitDP で初めてプログラムを作って, 何となく感触は掴めました. 今後は実践で使えるようになりたいです.

参考

• AtCoder：競技プログラミングコンテストを開催する国内最大のサイト