読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

yukicoder No.429 CupShuffle

yukicoder

問題

No.429 CupShuffle - yukicoder
N個のコップについて交換の仕方・最終配置が与えられる.ただし,X回目の交換の仕方の情報が抜けている.どのコップを交換したかを求める問題.

解法

解説を見るとX-1回目までswapを行い,一方K回目からX+1回目まで逆順でswapを行って,その差を求める,という解法だった.しかし逆方向からswapを行う必要はなく,X回目を飛ばして最後までswapを行って最終配置と比較する.このとき間違っているコップは2つだけのはずなので,X回目での配置を覚えておけばどこを交換すべきだったかが求められる.

ソースコード

[n,k,x] = map(int,input().split(' '))
x -= 1
s = [i for i in range(1,n+1)]
for i in range(k):
    if i == x:
        input()
        tmp = s[:]
        continue
    [a,b] = map(int,input().split(' '))
    a -= 1
    b -= 1
    s[a],s[b] = s[b],s[a]
c = list(map(int,input().split(' ')))
t = [s[i] for i in range(n) if s[i] != c[i]]
for i in range(n):
    if tmp[i] in t:
        print(i+1,end=' ')
print("")

最近pythonを使い始めたけど,c++より全然書きやすい