bitDP - Githubissues

tipstar0125 commented 10 months ago

dp[s][pos]:= 集合s(bitが1がvisited)のとき、posにいるときの最小

MAX=1<<L
dp=[[INF for _ in range(L)] for _ in range(MAX)]
dp[0][0]=0

for s in range(1,MAX):
    for frm in range(L):
        if frm!=0 and s&(1<<frm)==0:continue  # 原点0に戻る場合
        # if s&(1<<frm)==0:continue  # 戻らない場合
        for to in range(L):
            if s&(1<<to)==0:continue
            bs=s^(1<<to)
            dp[s][to]=min(dp[s][to],dp[bs][frm]+dist[frm][to])

TSP（原点に戻る）
- 初期化において、dp[0][0]=0として、どこも訪れていない状態を0とする

問題：https://atcoder.jp/contests/abc274/tasks/abc274_e 解答：https://atcoder.jp/contests/abc274/submissions/49806227

TSP（原点に戻らない）
- 初期化において、dp[1][0]=0として、原点を訪れた状態を0とする
- 多始点の場合はdp[1<<i][i]として、全ての点で初期化する

問題：https://atcoder.jp/contests/abc301/tasks/abc301_e 解答：https://atcoder.jp/contests/abc301/submissions/49787905

TSP（負辺）
- 負辺がある場合は、まだ訪れていないINFからの遷移はできない(負辺だと距離が短くなる）
- 辺がINFの遷移もしてはいけない問題：https://atcoder.jp/contests/abc338/tasks/abc338_f 解答：https://atcoder.jp/contests/abc338/submissions/49787672

tipstar0125 commented 10 months ago

n進数dp
- Kビットの(P+1)進数で状態をもつ
- 速い言語ならHashMapを使ってもよい問題：https://atcoder.jp/contests/abc322/tasks/abc322_e 解答：https://atcoder.jp/contests/abc322/submissions/49802215 解答(Rust, map)：https://atcoder.jp/contests/abc322/submissions/49804245

tipstar0125 commented 10 months ago

問題リスト https://blog.hamayanhamayan.com/entry/2017/07/16/130151

ABC142E(使う、使わないの組合せ、よくあるやつ) 問題：https://atcoder.jp/contests/abc142/tasks/abc142_e 解答：https://atcoder.jp/contests/abc142/submissions/49806944
ABC180E(原点に戻るTSP) 問題：https://atcoder.jp/contests/abc180/tasks/abc180_e 解答：https://atcoder.jp/contests/abc180/submissions/49806215
ABC190E(多始点TSP、原点に戻らない) 問題：https://atcoder.jp/contests/abc190/tasks/abc190_e 解答：https://atcoder.jp/contests/abc190/submissions/49808831
ABC199E 問題：https://atcoder.jp/contests/abc199/tasks/abc199_e 解答：
yuki No.698(ペア、ペア順列全探索でも可) 問題：https://yukicoder.me/problems/no/698 解答：https://yukicoder.me/submissions/947331
yuki No.286(costを都度計算するTSP,bsの訪れた箇所から状態を復元) 問題：https://yukicoder.me/problems/no/286 解答：https://yukicoder.me/submissions/947346
yuki No.107(costを都度計算するTSP,bsの訪れた箇所から状態を復元) 問題：https://yukicoder.me/problems/no/107 解答：https://yukicoder.me/submissions/947344
yuki No.134(costを都度計算するTSP,bsの訪れた箇所から状態を復元) 問題：https://yukicoder.me/problems/no/134 解答：https://yukicoder.me/submissions/947345
yuki No.771(maxのmin) 問題：https://yukicoder.me/problems/no/771 解答：https://yukicoder.me/submissions/947347
yuki No.357(pointを都度計算するTSP,bsの訪れた箇所から状態を復元) 問題：https://yukicoder.me/problems/no/357 解答：https://yukicoder.me/submissions/947348
yuki No.719 問題：https://yukicoder.me/problems/no/719 解答：

tipstar0125 / atcoder

bitDP #51