Last active
August 29, 2015 14:04
-
-
Save parrot-studio/f7770fdfb6b12b472504 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 再帰的探査 | |
def search(list, i, need, nco, maxind, mincost, limit_mem) | |
c = list[i] | |
nmem = need - c[0] | |
cost = nco + c[1] | |
return mincost if cost > mincost # すでにわかっている答えより大きいので無駄 | |
return cost if nmem <= 0 # メンバーが埋まった | |
return mincost if i >= maxind # 終端までいったが、メンバーが埋まらない | |
# 自身の効率*残り人数+現在のcostがmincostを超える | |
return mincost if (cost + c.last * nmem >= mincost) | |
# 自分よりindexが大きいものから探査したcostの最小値 | |
min = mincost | |
((i+1)..maxind).each do |ind| | |
# これ以上先に満たせるだけのメンバーがいない | |
break if nmem > limit_mem[ind] | |
rsl = search(list, ind, nmem, cost, maxind, min, limit_mem) | |
min = rsl if rsl < min | |
end | |
min | |
end | |
member = gets.to_i | |
size = gets.to_i | |
companys = [] | |
ans = nil | |
tcos = 0 # total cost | |
size.times do | |
ds = gets.split(' ').map(&:to_i) | |
if ds.first >= member | |
ans = ds.last if (ans.nil? || ans > ds.last) | |
else | |
mem = ds.first | |
cos = ds.last | |
companys << [mem, cos, (cos.to_f / mem)] | |
tcos += cos | |
end | |
end | |
(puts ans; exit) if companys.empty? | |
ans ||= tcos | |
(puts ans; exit) if ans < tcos | |
companys.sort_by!{|c| c.last} | |
maxind = companys.size - 1 | |
# あるindexまでのメンバー数 | |
limit_mem = {} | |
lm = 0 | |
limitind = nil | |
maxind.downto(0) do |i| | |
lm += companys[i].first | |
limit_mem[i] = lm | |
limitind = i if (limitind.nil? && lm > member) | |
end | |
ratio = ans.to_f / member | |
(0..limitind).each do |i| | |
break if companys[i].last > ratio | |
cost = search(companys, i, member, 0, maxind, ans, limit_mem) | |
next if cost >= ans | |
ans = cost | |
ratio = ans.to_f / member | |
end | |
puts ans | |
exit |
9b9d55 => http://paiza.jp/poh/kirishima/result/3a84341cd1c2f6d93e4d71781e857a91
「絶対含まれる会社」をあらかじめ間引いてみたけど効果なし
9bfde2 => http://paiza.jp/poh/kirishima/result/d89160ddb3129940a31a502afb5b5e75
一度は棄却した「1人あたりのコスト」から足きり条件を追加
これを利用すればまだ切れるか・・・?
124936 => http://paiza.jp/poh/kirishima/result/fa999e57b33527ff7dbbaefb67620f7e
人数での足きりを追加してS獲得
効率も人数の足きりも途中で思いついたのに、使い方がまずかった・・・
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3feb7e => http://paiza.jp/poh/kirishima/result/7c3b1a804dc2b128ff4cdacd621e83cb
深さの制約をつけても変わらず
多すぎるデータを間引くか、効率の良い探索を考えるか