ABC180E
https://gyazo.com/f3e649bb12de0bbd15495e3c67a3523e
Thoughts.
17 factorial is large enough.
Problems solving TSP (TSP) with [bitDP Is the "may pass through the same city twice" in Sample 2 a little different?
But I don't see a pattern where it would be beneficial to go through another city instead of moving directly.
I'll refer you to an article on solving the traveling salesman problem with bitDP by googling the appropriate article.
Needs a slight correction because it is "until you return to city 1", not "until you visit all cities from city 1".
Fixed and small sample passes, but large sample does not, contest ended without finding the cause.
after the contest
Bring in an implementation of someone doing AC and make a small sample of the random input that causes discrepancies.
5, [[1, 1, 0], [1, 2, 1], [1, 1, 1], [1, 2, 0], [2, 0, 1]] returns 8 when it is really 7
I looked at anthology and found the code for TSP in the case of a loop, so I referred to it and easily AC'd it in 26 minutes. 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
memo = [INF * N for _i in range(SIZE)] 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
)
consideration
The Qiita one has the final vertex for each subset as an array last value.
I have the ant book with the subscripts.
The Qiita one doesn't include the path back to vertex 0 because the problem condition is "the shortest path that starts at vertex 0 and follows all vertices".
Even if this algorithm finds the shortest path, the way back from it may be expensive
This issue and the ant book example are the shortest closed path
So the problem conditions are fundamentally different from Qiita's explanation.
Commentary on the side of the ant book
Start at vertex 0, but do not initially include vertex 0 when considering the visited vertex set
In this way, when the "visited vertex set becomes the whole set", it means "returned to vertex 0", so it can be applied to the problem condition including the return path
Is there any deeper meaning in having DPs in reverse order?
It works fine in the correct order, so there doesn't seem to be a deep meaning.
code:python
for subset in range(1, SIZE):
for v in range(N):
for u in range(N):
mask = 1 << u
if subset & mask:
---
This page is auto-translated from /nishio/ABC180E. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.