🔍

[鉄則A15] Compression (座標圧縮)

に公開
Ruby
AtCoder
競プロ
二分探索
座標圧縮
tech

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_o

座標圧縮問題。

問題を要約する

  • スコアからランキングを求めるには？

例1で問題を理解する

0 1 2 3 4
A 46 80 11 77 46
B 1 3 0 2 1

A から B を作りたい。差分の配列ではない。連番になっている。連番ではあるが同じ値は同じ数字になる。元の値はどうでもいい。

これを解説では座標圧縮と紹介しているが、どうも既視感があるので思い返してみると、スコアからランキングへの変換と同じである。

解き方

元の、

0 1 2 3 4
A 46 80 11 77 46

をソート＆ユニークにした B を用意して、

0 1 2 3
B 11 46 77 80

A の 46 は B のどこにあるか調べると 1 だとわかる。これを繰り返すと、

Aの要素 B のどこにある？
46 1
80 3
11 0
77 2
46 1

になって、それを 1-based にしたのが答えになる。

自力で捻り出した実装 (TLE)

N = gets.to_i                   # => 5
A = gets.split.collect(&:to_i)  # => [46, 80, 11, 77, 46]
seq = 1
ans = []
A.sort.each do |v|
  found = false
  A.each.with_index do |e, i|
    if e == v
      unless ans[i]
        ans[i] = seq
        found = true
      end
    end
  end
  if found
    seq += 1
  end
end
ans                             # => [2, 4, 1, 3, 2]
puts ans * " "

ソート済みの配列を先頭から順に元の配列ではどこにあったかを見ていく方法は二重ループになってしまって遅い。

解説の模範解答 (AC)

139 ms
N = gets.to_i                                               # => 5
A = gets.split.collect(&:to_i)                              # => [46, 80, 11, 77, 46]
a = A.sort.uniq                                             # => [11, 46, 77, 80]
ans = A.collect { |v| a.bsearch_index { |e| v - e }.next }  # => [2, 4, 1, 3, 2]
puts ans * " "

sort + uniq + bsearch_index のシナジーが美しすぎる。

気づいたこと

ランキングを出すときに便利な Redis の ZREVRANK や ZCOUNT 命令も計算量が O(log(N)) ということは同様のアルゴリズムだと思われる。

参考

Discussion