ARC110C
from ARC110
C - Exoswap ARC110Fに関連問題
https://gyazo.com/f71976b9a1f12a846b3cf359703b0135
ARC110C
貪欲にやる
「1を先頭に持ってくるには」を考える
今いる位置から先頭まで持ってくる置換が必要不可欠
順番に先頭に持ってくる過程をやって、過不足が有ればNG
関連: 貪欲法の証明パターン
code:python
def solve(N, PS):
ret = []
used = False * (N - 1)
def swap(x):
PSx - 1, PSx = PSx, PSx - 1
usedx - 1 = True
ret.append(x)
for target in range(1, N):
x = PS.index(target, target - 1)
for i in range(x, target - 1, -1):
if usedi - 1:
return -1
swap(i)
if False in used:
return -1
return ret