POH! Vol.1 Ruby模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

Ruby: paiza事務局作成コード Vol.3 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.02秒
実行時間(テストケース2):0.18秒
実行時間(テストケース3):3.64秒

# coding: utf-8
tmp = gets.chomp.split(" ")
n = tmp[0].to_i
d = tmp[1].to_i
p = []
n.times do
  p.push(gets.to_i)
end
p.sort!

p_len = p.length - 1
d.times do
  m_j = gets.to_i
  ans = 0
  j = 0
  k = p_len
  while j != k do
    s = p[j] + p[k]
    if s > m_j
      k -= 1
    else
      j += 1
      if ans < s
        ans = s
      end
    end
  end
  print ans, "\n"
end

Ruby: paiza事務局作成コード Vol.2 O(DNlogN)

通過テストケース数:2
実行時間(テストケース1):0.10秒
実行時間(テストケース2):2.25秒
実行時間(テストケース3):--

# coding: utf-8
tmp = gets.chomp.split(" ")
n = tmp[0].to_i
d = tmp[1].to_i
p = []
n.times do
  p.push(gets.to_i)
end

p.sort!
d.times do
  m_j = gets.to_i
  ans = 0
  n.times do |i|
    r = m_j - p[i]
    lb = 0
    ub = n
    while ub - lb != 1 do
      mid = (ub + lb) / 2
      if p[mid] <= r
        lb = mid
      else
        ub = mid
      end
    end
    ub -= 1
    if i >= ub
      next
    end
    if p[ub] > r
      next
    end
    tmp = p[i] + p[ub]
    if tmp <= m_j and ans < tmp
      ans = tmp
    end
  end
  print ans, "\n"
end

Ruby: paiza事務局作成コード Vol.1 O(DN^2)

通過テストケース数:1
実行時間(テストケース1):6.06秒
実行時間(テストケース2):--
実行時間(テストケース3):--

# coding: utf-8
tmp = gets.chomp.split(" ")
n = tmp[0].to_i
d = tmp[1].to_i
p = []
n.times do
  p.push(gets.to_i)
end

d.times do |i|
  m_j = gets.chomp.to_i
  ans = 0
  n.times do |j|
    n.times do |k|
      s = p[j] + p[k]
      if s <= m_j and ans <= s and j != k
        ans = s
      end
    end
  end
  print ans, "\n"
end
ページの先頭へ戻る