-
-
Save parrot-studio/f7770fdfb6b12b472504 to your computer and use it in GitHub Desktop.
# 再帰的探査 | |
def search(list, i, nmem, nco, maxind, maxmem, mincost, table) | |
c = list[i] | |
mems = nmem + c.first | |
cost = nco + c.last | |
return mincost if cost > mincost # すでにわかっている答えより大きいので無駄 | |
return cost if mems >= maxmem # メンバーが埋まった | |
return mincost if i >= maxind # 終端までいったが、メンバーが埋まらない | |
# 自分よりindexが大きいものから探査したcostの最小値 | |
min = mincost | |
((i+1)..maxind).each do |ind| | |
break if (mems + table[ind]) < maxmem # ここから先は絶対にメンバーを満たせない | |
rsl = search(list, ind, mems, cost, maxind, maxmem, mincost, table) | |
min = rsl if rsl < min | |
end | |
min | |
end | |
# main | |
need = gets.to_i | |
companys = [] | |
gets.to_i.times do | |
ds = gets.split(' ').map(&:to_i) | |
next if ds.first > need | |
companys << ds | |
end | |
companys.sort_by!{|c| -c.first} | |
# あるindexにおけるメンバーの最大値 | |
csize = companys.size | |
members = {} | |
(csize-1).downto(0) do |i| | |
members[i] = companys[i].first + members[i+1].to_i | |
end | |
# 探索 | |
ans = 5000000 * csize | |
csize.times do |i| | |
break if members[i] < need # ここから先は絶対にメンバーを満たせない | |
cost = search(companys, i, 0, 0, (csize - 1), need, ans, members) | |
next unless cost | |
ans = cost if cost < ans | |
end | |
puts ans | |
exit |
54c84e => http://paiza.jp/poh/kirishima/result/0e208c381746c24dfe0158316ac9268e
わかっている答えより大きければ棄却・・・はあまり効果なし
1db46d => http://paiza.jp/poh/kirishima/result/20f65a864f574dec886fbbead58ada19
考える前にソースを整理
ef6fbc => http://paiza.jp/poh/kirishima/result/04030b70baad1928a36adfb7963e88cb
行き詰まったのでアプローチを変える
とりあえず複雑化した状態のを残す
7188dd => http://paiza.jp/poh/kirishima/result/b936a356256abfb83f32641f2b997c09
余計なものを全部そぎ落として結果を確認
今後のベース
95e4b6 => https://paiza.jp/poh/kirishima/result/51be0e4e4eecbfcb463bde39ed593806
最初から要件を満たしたデータを除外したが、変化なし
d5103f (type2) => https://paiza.jp/poh/kirishima/result/cd178c2e9224447aac58700e077e7e1e
試しにcombinationを使ってみたら、ごりごり書いたコードと大差なかった件
3feb7e => http://paiza.jp/poh/kirishima/result/7c3b1a804dc2b128ff4cdacd621e83cb
深さの制約をつけても変わらず
多すぎるデータを間引くか、効率の良い探索を考えるか
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獲得
効率も人数の足きりも途中で思いついたのに、使い方がまずかった・・・
master => http://paiza.jp/poh/kirishima/result/3ed226ed924f99208e77cea595699529
一発目でCase5が0.02sは悪くない