paizaラーニング解答: ソートメニュー応用編[Ruby]

ソートメニュー応用編

STEP: 1 ソートの基本

n = gets.to_i
a = gets.split.map(&:to_i)
puts a == a.sort ? "Yes" : "No"

STEP: 2 最大最小

n = gets.to_i
a = gets.split.map(&:to_i)
a.sort!
puts "#{a[-1]} #{a[0]}"

maxとminメソッドでも解答できますが、せっかくなのでソートを使って答えてます。

STEP: 3 Top - k (easy)

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a.sort!
puts a[-k]

STEP: 4 重複削除

n = gets.to_i
a = gets.split.map(&:to_i)
a.uniq!
puts a.sort.join(' ')

FINAL問題 区間のソート

n, l, r = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a[l - 1...r - 1] = a[l - 1...r - 1].sort
puts a.join(' ')

配列の指定区間をソートして、元の配列に代入しています。

STEP: 1 Top - k (hard)

n, q = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
k = gets.split.map(&:to_i)
a.sort!
k.each do |i|
    puts a[-i]
end

STEP: 2 プログラミングレベル

n = gets.to_i
a = gets.split.map(&:to_i)
a.sort!
ans = true
if a[0] != 1
    ans = false
else
    (0...n - 1).each do |i|
        if a[i + 1] > a[i] + 1
            ans = false
            break
        end
    end
end
puts ans ? "Yes" : "No"

STEP: 3 辞書順

k = gets.to_i

words = []
('a'..'z').each do |c1|
    ('a'..'z').each do |c2|
        ('a'..'z').each do |c3|
            word = c1 + c2 + c3
            words << word
        end
    end
end

puts words[k - 1]

STEP: 4 部分列

n, x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
a.sort!.reverse!
ans = -1
sum = 0
(0...n).each do |i|
    sum += a[i]
    if sum >= x
        ans = i + 1
        break
    end
end
puts ans

STEP: 5 ペアソート

n = gets.to_i
a = n.times.map { gets.split.map(&:to_i) }
a.sort!
n.times do |i|
    puts a[i].join(' ')
end

単にsortメソッドを使うだけでソートできます。
Rubyで順序を指定してソートするのはどういう方法がスマートなんでしょうか・・・？

STEP: 6 タプルソート

n, m, k = gets.split.map(&:to_i)
a = n.times.map { gets.split.map(&:to_i) }

sorted_a = a.sort_by { |row| [row[k - 1]] + row[0..k - 2] + row[k...m] }
sorted_a.each do |sa|
    puts sa.join(' ')
end

STEP: 7 スケジューリング

n = gets.to_i
campagins = n.times.map { gets.split.map(&:to_i) }
campagins.sort_by! { |l, r| r }
count = 0
last_day = 0
campagins.each do |campagin|
    if campagin[0] > last_day
        count += 1
        last_day = campagin[1]
    end
end
puts count

難しかった。
paiza側で詳しく解説されています。

STEP: 8 文字列のソート

n = gets.to_i
s = n.times.map { gets.chomp }
puts s.sort_by { |s_i| [s_i.length, s_i] }

sort_byで文字列の長さと文字列の昇順でソート。

STEP: 9 マンハッタン距離

n = gets.to_i
a = n.times.map { gets.split.map(&:to_i) }
a.sort_by! { |y, x| y.abs + x.abs }
a.each do |yx|
    puts yx.join(' ')
end

sort_byメソッドは神では・・・？

STEP: 10 座標圧縮

n, q = gets.split.map(&:to_i)
a = gets.split.map(&:to_i).sort
x = gets.split.map(&:to_i)
complessed = {}
(0...n).each do |i|
    complessed[a[i]] = i + 1
end
(0...q).each do |i|
    puts complessed[x[i]]
end

indexメソッドでそのまま取り出すより座標圧縮をすると明らかに実行時間が短いです。

FINAL問題 ソートによる高速化まとめ

n, q = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
query = q.times.map { gets.chomp.split }

q.times do |i|
    que, k, x = query[i]
    k = k.to_i
    x = x.to_i
    if que == "update"
        a[k - 1] = x
    else
        puts a.sort[-k]
    end
end