bitDP

[tipstar0125]

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]

• 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]

問題リスト
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
  解答：