ABC135-B - 0 or 1 Swap を解く

ABC135-B - 0 or 1 Swap

数列 { p1, p2, ... , pn } が与えられる

一度だけ、 pi, pj を入れ替えることができる（入れ替えなくてもいい）とき

数列を昇順に並べることが可能かどうかを調べる問題

まずは昇順に並べた場合の数列を作ってみて

与えられた数列と完全に一致した場合は可能である（入れ替え不要）

また、ソートした数列が与えられた数列と 2 箇所 不一致であり

不一致であった 2 箇所を並べ換えることで一致させることができるならば

これも昇順に並べることが可能である

この条件は

昇順に並んだ数列から 2 つを選んで入れ替えたときの条件に等しい

上記 2 通りの方法について確認するコードを書けばいい

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())
l=list(map(int,input().split()))

# ソートした数列
sl=sorted(l)

# 一致するなら 'YES'
if l==sl:
  print('YES')
  exit()

# 一致しない回数をカウント
c=0

# 一致しない数字を保持するリスト
a=[]
b=[]

for i in range(N):
  # 不一致のとき
  if l[i]!=sl[i]:
    c+=1
    a.append(l[i])
    b.append(sl[i])

# 不一致の回数が2回であり、同じペアの数字であれば 'YES'
if c==2:
  if a[0]==b[1] and a[1]==b[0]:
    print('YES')
    exit()

# それ以外の場合は 'NO'
print('NO')

 

提出結果はACでした