🔍
[鉄則A15] Compression (座標圧縮)
座標圧縮問題。
問題を要約する
- スコアからランキングを求めるには？
例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