ABC296 F問題 Simultaneous Swap

atcoder.jp

条件の整理

並び替えで と が一致するためには、少なくとも と で値の出現回数が一致する必要があります。
一致しない場合は、「No」です。

操作前に、 の各組が同じ位置のとき、操作後には の組み合わせになります。
並び順は問題にしていないので、 の方を元の位置に戻すと、 となり、これはの方に の巡回置換を行ったことに相当します。

以上から、 に長さ3の巡回置換を繰り返すことで と一致させることができるか、という問題に言い換えることができます。

長さ3の巡回置換は、2回の互換(2要素の入れ替え)に分解することができるので、 を に一致させるための互換の回数が奇数のときは、長さ3の巡回置換だけでは一致させることができません。
逆に偶数回の互換で一致させることができる場合、長さ3の巡回置換を繰り返しで一致させることができます。

また、 の中に同じ値がある () 場合、互換は偶数回にも奇数回にもなるので、一致させることができます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()
  A = readInts()
  B = readInts()

  # A と B の中身が一致しているか調べる

  n1 = zeros(Int,N)
  n2 = zeros(Int,N)

  for i = 1:N
    n1[A[i]] += 1
    n2[B[i]] += 1
  end

  for i = 1:N
    if n1[i] != n2[i]
      # i の登場回数が A と B で異なる
      #   --> 並び替えても一致しない
      println("No")
      return
    end
  end

  for i = 1:N
    if n1[i] >= 2
      # 同じ数字が2回以上現れる
      #   --> 一致させることができる
      println("Yes")
      return
    end
  end

  # A を小さい順に並び替えたときの B の並び
  C = zeros(Int,N)
  for i = 1:N
    C[A[i]] = B[i]
  end

  n_swap = 0

  i = 1
  while i <= N
    p = C[i]
    if p == i
      i += 1
    else
      n_swap += 1
      C[i] = C[p]
      C[p] = p
    end
  end

  if n_swap % 2 == 0
    println("Yes")
  else
    println("No")
  end

end  # function solve

# main
solve()