bit dp
- 要素をbitのフラグとしてみなしその構成パターンのdpテーブルを作って管理する
- 巡回セールスマン問題
配るdpと貰うdpの２種類が存在し、問題によってはどちらでも行けることがある
例; 配るdpと貰うdp両方どちらでもOKなケース
問題
解説
- 貰うもの、配るものをbit maskとして管理する
- 前の状態、次の状態を決定するのもbit maskを利用する
解答(配るdp)
N,M=map(int,input().split())
dp=[0]*(1<<N)
dp[0]=1
edge = [0]*N
for _ in range(M):
x,y=map(int,input().split())
"xはyより早くにゴールしたという情報をyを起点に記録"
edge[y-1] |= 1<<(x-1)
for s in range(1<<N):
for j in range(N):
"sとjが共起してなかったら"
if s & (1<<j) == 0:
"かつ、sと配る先が共起していなかったら"
if s&edge[j] == 0:
dp[s|(1<<j)] += dp[s]; "配る"
print(dp[-1])
解答(貰うdp)
N,M=map(int,input().split())
dp=[0]*(1<<N); "ありえるパターンの大きさのリスト"
dp[0]=1
"もらうためのビットの対応を作る"
edge = [0]*N
for _ in range(M):
x,y=map(int,input().split())
edge[x-1] |= 1<<(y-1); "xはyより早くにゴールしたというbitパターンを記録"
for s in range(1<<N):
for j in range(N):
"sとjが共起したら"
if s & (1<<j) > 0:
"前に早くにゴールしたというパターンを持っていなければ"
if s&edge[j] == 0:
dp[s] += dp[s^(1<<j)]; "jがゴールしていない状態のbitパターンを貰う"
print(dp[-1])
例; トラベリングセールスマン問題の拡張
問題
解説
edgeという変数を作成- dpは圧倒的にC++が早い(PythonでもAtCoderは通せるがコードがピーキーになり非本質的)
- dpはもらうdpで一歩手前の状態を考えて実装する
解答
int main() {
ll N;
cin >> N;
vector<ll> X(N, 0), Y(N, 0), Z(N, 0);
rep(i, N) {
cin >> X[i] >> Y[i] >> Z[i];
}
vector<vector<ll>> edge(N, vector<ll>(N, INF));
rep(i, N) { rep(j, N) {
edge[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max(0ll, Z[i] - Z[j]);
edge[j][i] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max(0ll, -Z[i] + Z[j]);
}}
vector<vector<ll>> dp(1<<N, vector<ll>(N,INF));
dp[0][0] = 0ll;
rep(mask, 1<<N) {
rep(i, N) {
rep(j, N) {
if(i!=j and (mask&1<<i) > 0 and edge[j][i] != INF) {
dp[mask][i] = min(dp[mask][i], dp[mask^(1<<i)][j] + edge[j][i]);
}
}
}
}
print(dp[(1<<N) - 1][0]);
}
例; 素直に考えるとsetで処理するような内容の数え上げはbit dpで処理する
問題
解説
- 素直に考えるとバックトラック法が適応例に見えたが、数が非常に多いのでバックトラック法では間に合わなかった
- 愚直なコードにsetが必要であったので、この時点でbit dpが適応例になると気付けると良い
解答
MOD = 998244353
N = int(input())
S = input()
P = 1 << 10 # せいぜい10種類のコンテストしかないので1024の表現で間に合う
dp = [[[0]*10 for i in range(P)] for j in range(N+1)]
for i in range(1, N+1):
x = ord(S[i-1]) - ord("A")
for u in range(P):
for j in range(10):
dp[i][u][j] = dp[i-1][u][j]
if j == x:
dp[i][u][j] += dp[i-1][u][j]
dp[i][u][j] %= MOD
for v in range(P):
if v & (1<<x) > 0:
continue
for j in range(10):
dp[i][v|(1<<x)][x] += dp[i-1][v][j]
dp[i][v|(1<<x)][x] %= MOD
dp[i][(1<<x)][x] += 1
dp[i][(1<<x)][x] %= MOD
ans = 0
for u in range(P):
for j in range(10):
ans += dp[N][u][j]
ans %= MOD
print(ans)
例; スケジュール問題の数え上げ
問題
解説
- ユーザをbitとして考える
- ビットのパターンはたかだか8つなので数え上げができる
- 条件を満たすものをカウントするだけ
解答(想定解法)
N=int(input())
S=input()
MOD = 10007
map = {'J':0, 'O': 1, 'I': 2}
P = 1<<3
dp = [0]*P
dp[1] = 1
for s in S:
now = map[s]
ndp = [0]*P
for i in range(P):
if i&(1<<now) == 0:
continue
for j in range(P):
if i&j == 0:
continue
ndp[i] += dp[j]
ndp[i] %= MOD
dp = ndp
print(sum(dp)%MOD)
解答(貰うdp)
N=int(input())
S=input()
MOD=10007
dp = [[0]*(1<<3) for _ in range(N+1)]
dp[0][1] = 1; "この初期値は謎"
for day, s in enumerate(S):
must_have = dict(J=0,O=1,I=2)[s]
for i in range(1<<3):
if i&(1<<must_have) > 0:
for j in range(1<<3):
if i&j > 0:
"貰うdp"
dp[day+1][i] += dp[day][j]
dp[day+1][i] %= MOD
print(sum(dp[-1])%MOD)