塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

復習 4/2,4/3

atcoder.jp

必勝法ゲー。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となる。

atcoder.jp

BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく


onlinejudge.u-aizu.ac.jp

巡回セールスマン問題。これ始点を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)

シフト演算子が結構便利であることに気づいた。