ABC180E

https://gyazo.com/f3e649bb12de0bbd15495e3c67a3523e

考えたこと

17の階乗は十分大きい

サンプル2に出てくる「同じ都市を2回通っても良い」が少し違うか？

でも直接移動しないで他の都市を経由した方が得になるパターンがない気がする

bitDPで巡回セールスマン問題を解いてる記事を適当にググって参考にする

「都市1からすべての都市を訪問するまで」ではなく「都市1に戻るまで」なので少し修正が必要

修正して小さいサンプルは通るけど、大きいサンプルが通らない、原因を見つけられないままコンテスト終了

コンテスト後

ACしてる人の実装を持ってきて、ランダム入力で食い違いが発生する小さいサンプルを作る

code:python

def solve(N, XYZS):

import sys

INF = sys.maxsize # float("inf")

dist = []

for i in range(N):

ds = []

dist.append(ds)

for j in range(N):

ds.append(abs(p - a) + abs(q - b) + max(0, r - c))

SIZE = 2 ** N

for subset in range(SIZE - 2, -1, -1):

for v in range(N):

for u in range(N):

if (subset >> u) & 1 == 0:

mask = 1 << u

)

考察

Qiitaの方はsubsetごとに最終頂点を配列lastの値で持ってる

蟻本の方は添え字で持ってる

Qiitaの方は問題条件が「頂点0から始めて、全部の頂点を辿る最短のパス」なので、頂点0に戻る道が含まれてない

このアルゴリズムで最短のパスを見つけたとしても、そこからの帰り道が高コストかもしれない

今回の問題と蟻本の例は最短の閉路

だからQiitaの解説とは根本的に問題条件が違う

蟻本の側の解説

頂点0からスタートするが、訪問済み頂点集合を考える上で頂点0は最初は含めない

こうすることで「訪問済み頂点集合が全集合になった」時「頂点0に戻ってきた」ことを意味するので、戻り道も含めた問題条件に適用できる

逆順でDPしていることには何か深い意味があるのだろうか？

正順でも問題なく動くから深い意味はなさそう

code:python

for subset in range(1, SIZE):

for v in range(N):

for u in range(N):

mask = 1 << u

if subset & mask: