Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 再帰的探査
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
@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

考える前にソースを整理

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Jul 30, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Aug 1, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Aug 7, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Aug 7, 2014

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

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

@parrot-studio

This comment has been minimized.

Copy link
Owner Author

@parrot-studio parrot-studio commented Aug 8, 2014

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
You can’t perform that action at this time.