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

# はじめに
[競プロ典型 90 問](https://atcoder.jp/contests/typical90 "競プロ典型 90 問") の[032 - AtCoder Ekiden](https://atcoder.jp/contests/typical90/tasks/typical90_af "032 - AtCoder Ekiden") をトライしました. 結果的に解けたのですが, 解説には「bitDP を用いてこの問題を解くこともできます」とありました.

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

# bitDP で解く
参考にしたのは [こちらのサイト](https://scrapbox.io/kyopro-notes/%E7%AB%B6%E3%83%97%E3%83%AD%E5%85%B8%E5%9E%8B90%E5%95%8F:_032_-_AtCoder_Ekiden%EF%BC%88%E2%98%853%EF%BC%89) です.

方針としては解説にある通り, $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)
```
学んだことは次の通り.
- 初期化をきちんとやろう
- [演算子の優先順位](https://docs.python.org/ja/3.13/reference/expressions.html#operator-precedence) に注意. 例えば `(1<<N)-1` のつもりで `1<<N-1` とやると間違える.


# 全探索で解く
[032 - AtCoder Ekiden](https://atcoder.jp/contests/typical90/tasks/typical90_af "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 | [リンク](https://atcoder.jp/contests/typical90/submissions/65410388) |
|全探索| 901 Byte  | 1989 ms  |  83116 KB | [リンク](https://atcoder.jp/contests/typical90/submissions/65410559)|
| My Answer  |1129 Byte|2596 ms|84204 KB| [リンク](https://atcoder.jp/contests/typical90/submissions/65410746) |

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

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

# 参考
- [AtCoder：競技プログラミングコンテストを開催する国内最大のサイト](https://atcoder.jp/ "AtCoder：競技プログラミングコンテストを開催する国内最大のサイト")