必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか?」をdp[j]で管理する。
取れる枚数がn種類(a_1...a_n)あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose
逆にdp[j-a_i]がLoseになるものが一つでもあれば、相手に「負け」の状況を押し付けることができるのでdp[j] = winとなる。
BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく
巡回セールスマン問題。これ始点を0に固定しているけど、どの頂点から出発したとしても、必ず0は通るわけで、そのあとの道のりは全く同じになるので、別に頂点0にスタートを固定しても問題はなさそう。
すなわち、頂点i~頂点0(経路A)→頂点0~頂点i(経路B)は、B→Aとしても最小コストが変わらない。
v,e = map(int,input().split()) #v:頂点, e:辺 graph = [[] for i in range(v)] cost = [[float('inf')]*v for i in range(v)] for i in range(e): x,y,z = map(int,input().split()) cost[x][y] = z dp = [[float('inf')]*v for i in range(1<<v)] #(1<<v)-1 == 2**v-1 dp[(1<<v)-1][0] = 0 #全ての頂点を訪れて帰ってきた時(ここがゴール) for i in range(2**v-2, -1, -1): #まだ見ていない頂点集合に対して for j in range(v): #現在いる頂点から for k in range(v): #次に行く頂点について if i>>k & 1 != 1: #まだ訪れていないならば dp[i][j] = min(dp[i][j], dp[i|1<<k][k]+cost[j][k]) #dp[i|1<<k]は「kを訪れた状態」を指す。 #視点を変える。「今kにいる状態からゴールに至るのに必要なコスト」+「j→kに必要なコスト」は、 #「今jにいる状態からゴールに至るのに必要なコスト」になる(遡る) #これを「今0にいる状態からゴールに至るのに必要なコスト」まで遡って計算する。 if dp[0][0] != float('inf'): print(dp[0][0]) #まだどこも訪れていない状態から、ゴールである0を目指して進む else: print(-1)
シフト演算子が結構便利であることに気づいた。