C – Adjacent Swaps
方針
実際の入れ替え操作を行うリスト①に加えて、位置を記録するためのリスト②を作成する。
リスト①(A)の各要素は入れ替え操作が実際に行われる数字が格納されている。
リスト②(index)のn番目の要素はリスト①(A)における数字nの位置が格納されている。
先にリスト①(A)の要素を入れ替え、その後にリスト②(index)の要素を入れ替えている。
リスト①とリスト②が各ループの中で並びが一致することに違和感があるが、これは初めにリスト①(A)が1~nまで順番に並んでいることが理由。
標準入力によって1~nまでがバラバラの順番で与えられていた方がわかりやすかったかもしれない？
もし、Aがバラバラで与えられていたら・・・↓
入れ替え対象の数字を保存したリスト→A=[2,4,1,5,3]
入れ替え対象の数字の位置を保存したリスト→index=[3,1,5,2,4]
indexのi番目はAの各数字、indexのi番目の要素はAの各数字の位置を示す。
※indexの1番目はAの3番目、indexの2番目はAの1番目、indexの3番目はAの5番目
解答
コード＋コメント
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
n,q = map(int, input().split()) #0~nまでの数列を作る A = list(range(n+1)) #[0,1,2,3,4,5] #0~nまでの各数字の位置を記すリストを作る index = list(range(n+1)) #[0,1,2,3,4,5] #x,yは入れ替えを行う数字、i,jはx,yのリストAにおける位置(インデックス) for _ in range(q): #入れ替え対象の数字を入力 x = int(input()) #入れ替え対象の数字の位置を記録 i = index[x] #iが末尾以外の数字なら if i!=n: #iの右隣にある、位置を示す数字をjに記録 j=i+1 #iが末尾の数字なら else: #iの左隣にある、位置を示す数字をjに記録 j=i-1 #右、もしくは左隣りの数字をyに記録 y=A[j] #リストA内のi番目の数字xと、j番目の数字yを入れ替える A[i],A[j] = A[j],A[i] #print("A",A,"index",index,"Aの入れ替え後") #xの位置を更新 index[x]=j #yの位置を更新 index[y]=i #print("A",A,"index",index,"1ループの終わり＋indexの入れ替え後") print(*A[1:]) |
コードのみ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
n,q = map(int, input().split()) A = list(range(n+1)) index = list(range(n+1)) for _ in range(q): x = int(input()) i = index[x] if i!=n: j=i+1 else: j=i-1 y=A[j] A[i],A[j] = A[j],A[i] index[x]=j index[y]=i print(*A[1:]) |
その他
コメント