公式

B - 整列の部分修正 / Partial Correction of a Sorted Sequence 解説 by sounansya


まず、\(P=Q\) である場合の答えは Yes です。以降は \(P\neq Q\) である場合を考えます。

区間を反転すると両端の値は必ず変わります。したがって、\(P_i\neq Q_i\) である \(i\) の最小値を \(l\) 、最大値を \(r\) とすると反転する区間として \([l,r]\) のみを考えれば良いです。

実装例(Python3)

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
if p == q:
    print("Yes")
    exit()
left = -1
for i in range(n):
    if p[i] != q[i]:
        left = i
        break
right = -1
for i in range(n - 1, -1, -1):
    if p[i] != q[i]:
        right = i
        break
if p == q[:left] + q[right:left-1:-1] + q[right + 1 :]:
    print("Yes")
else:
    print("No")

投稿日時:
最終更新: