Skip to content

Instantly share code, notes, and snippets.

@parrot-studio
Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save parrot-studio/f7770fdfb6b12b472504 to your computer and use it in GitHub Desktop.
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
@parrot-studio
Copy link
Author

master => http://paiza.jp/poh/kirishima/result/3ed226ed924f99208e77cea595699529

一発目でCase5が0.02sは悪くない

@parrot-studio
Copy link
Author

54c84e => http://paiza.jp/poh/kirishima/result/0e208c381746c24dfe0158316ac9268e

わかっている答えより大きければ棄却・・・はあまり効果なし

@parrot-studio
Copy link
Author

1db46d => http://paiza.jp/poh/kirishima/result/20f65a864f574dec886fbbead58ada19

考える前にソースを整理

@parrot-studio
Copy link
Author

ef6fbc => http://paiza.jp/poh/kirishima/result/04030b70baad1928a36adfb7963e88cb

行き詰まったのでアプローチを変える
とりあえず複雑化した状態のを残す

@parrot-studio
Copy link
Author

7188dd => http://paiza.jp/poh/kirishima/result/b936a356256abfb83f32641f2b997c09

余計なものを全部そぎ落として結果を確認
今後のベース

@parrot-studio
Copy link
Author

95e4b6 => https://paiza.jp/poh/kirishima/result/51be0e4e4eecbfcb463bde39ed593806

最初から要件を満たしたデータを除外したが、変化なし

@parrot-studio
Copy link
Author

d5103f (type2) => https://paiza.jp/poh/kirishima/result/cd178c2e9224447aac58700e077e7e1e

試しにcombinationを使ってみたら、ごりごり書いたコードと大差なかった件

@parrot-studio
Copy link
Author

3feb7e => http://paiza.jp/poh/kirishima/result/7c3b1a804dc2b128ff4cdacd621e83cb

深さの制約をつけても変わらず
多すぎるデータを間引くか、効率の良い探索を考えるか

@parrot-studio
Copy link
Author

9b9d55 => http://paiza.jp/poh/kirishima/result/3a84341cd1c2f6d93e4d71781e857a91

「絶対含まれる会社」をあらかじめ間引いてみたけど効果なし

@parrot-studio
Copy link
Author

9bfde2 => http://paiza.jp/poh/kirishima/result/d89160ddb3129940a31a502afb5b5e75

一度は棄却した「1人あたりのコスト」から足きり条件を追加
これを利用すればまだ切れるか・・・?

@parrot-studio
Copy link
Author

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