[ABC350 C] Sort

https://atcoder.jp/contests/abc350/tasks/abc350_c

連番を並び替える問題。

問題を要約する

• 2 0 1 を 0 1 2 に並び換えるには？
• 交換していいのは 2 回まで

まちがった考え方

コンテスト中は一般的なソートアルゴリズムを実装する問題だと勘違いしていた。交換回数を答えることから、実装能力が試されているのかと。しかし、最も効率的だと思われるクイックソートでも、交換回数をN未満にすることができずに行き詰まってしまった。

本筋

先頭から順番に他から探し出した値を置いて(交換して)いく。

要点

値が連番の場合に限り、N 回未満の交換回数でソートできる。

解説を元にした単純な実装 (TLE)

N = gets.to_i                               # => 3
A = gets.split.collect { |e| e.to_i.pred }  # => [2, 0, 1]

swap = []
N.times do |e|
  if A[e] != e
    index = A.index(e)
    A[e], A[index] = A[index], A[e]
    swap << [e, index]
  end
end
p swap.size                                 # => 2
swap                                        # => [[0, 1], [1, 2]]
puts swap.collect { |e| e.collect(&:next) * " " }

せめてここまでは進めたかった。ここから A.index が遅いのに気づく流れになる。

解説を元にした速い実装 (AC)

384 ms

N = gets.to_i                                  # => 3
A = gets.split.collect { |e| e.to_i.pred }     # => [2, 0, 1]

if true
  # A.index(2) がすぐにわかるようにする
  indexes = {}                                # 最速を目指すなら配列の方がいい
  A.each.with_index { |e, i| indexes[e] = i }  # => [2, 0, 1]
  indexes                                      # => {2=>0, 0=>1, 1=>2}
end

swap = []
N.times do |e|
  if A[e] != e
    if true
      index = indexes[e]                       # => 1, 2
      # e=0 で A[e] の 2 は、0 のある位置 index=1 に移動する予定なので
      # A[e](=2) の位置は index(=1) にしておく
      indexes[A[e]] = index                    # => 1, 2
    else
      index = A.index(e)
    end
    A[e], A[index] = A[index], A[e]
    swap << [e, index]
  end
end
p swap.size                                    # => 2
swap                                           # => [[0, 1], [1, 2]]
puts swap.collect { |e| e.collect(&:next) * " " }

あまりのややこしさでこれを書くのに3時間かかった。A の要素を交換するのに合わせて indexes も同じ添字で交換しようとしていたのが失敗だった。正確には、

indexes[A[e]], indexes[e] = indexes[e], indexes[A[e]]

としなければいけなかった。

また左側の(所定の位置に収まった)値のインデックスはもう見ないので「所定の位置にいなかった値のインデックスを更新する」だけでもよかった。

indexes[A[e]] = index