POH! Lite Ruby模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。

Ruby: paiza事務局作成コード Vol.3 解説ブログ版

解説ブログ: もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら

得点:100点
通過テストケース:7/7

#coding: utf-8

M = gets.to_i #必要人数
N = gets.to_i #入力社数

min_cost = 0
q = Array.new(N)
r = Array.new(N)
# q 各下請け会社の人員数
# r 各下請け会社への発注費用
N.times do |i|
  q_t, r_t = gets.split(" ").map {|s| s.to_i}
  q[i] = q_t
  r[i] = r_t
  min_cost += r_t
end

dp = Hash.new
dp[0] = 0
# dp[人数] = 最低価格

# 入力社数分のループ
N.times do |i|
  dp_tmp = dp.clone
  # 人数ループ
  dp.each do |key, value|
    total_q = key + q[i]
    total_r = value + r[i]
    if dp_tmp.has_key?(total_q) == false
      dp_tmp[total_q] = total_r
    else
      if dp_tmp[total_q] > total_r
        dp_tmp[total_q] = total_r
      end
    end

    if total_q >= M && min_cost > total_r
      min_cost = total_r
    end

  end
  dp = dp_tmp

end

p min_cost

Ruby: paiza事務局作成コード Vol.2 動的計画法

得点:100点
通過テストケース:7/7

# coding: utf-8
m = gets.to_i
n = gets.to_i
qr = []
sum_q = 0
sum_r = 0
n.times do |i|
  q, r = gets.split(" ").map {|s| s.to_i}
  qr.push([q, r])
  sum_q += q
  sum_r += r
end

dp_m = sum_q - m
dp = Array.new(dp_m + 1, 0)

qr.each do |q, r|
  (q..dp_m).reverse_each do |j|
    dp[j] = [dp[j], dp[j-q] + r].max
  end
end

print sum_r - dp[dp_m], "\n"

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

得点:71点
通過テストケース:5/7

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

#m社のうちi番目の会社を使うか使わないかの表を作る
#3社とかなら
# A, B, C
# 1, 1, 1
# 1, 1, 0
# 1, 0, 1
#.....続く...
#みたいな1を使う0は使わないの表を作る

use_list = []

#2進数で考えると
(2**n).times do |i|
  use_list.push((("%0" + n.to_s + "d") % i.to_s(2)).chars.map {|c| c.to_i})
end

#使う使わないリストから、人月を満たせる組み合わせで最安を探す
ans = qr.map { |i| i[1] }.inject(:+)
use_list.each do |i|
  cost = 0;
  ningetsu = 0;
  i.each_with_index do |v, j|
    if v == 1
      ningetsu += qr[j][0]
      cost += qr[j][1]
    end
    if ningetsu >= m and ans > cost
      ans = cost
    end
  end
end

print ans, "\n"
ページの先頭へ戻る