れんしゅうちょう。

■ [FaceBookHackerCup]FaceBook Hacker Cup 2012 Qual 16:35

○|-|○

840位 29:26:13

Bの難易度異常じゃね･･･

以下メモとソース的な.

ソースはテンプレ省いてある.全部見たければScorebordから.

Billboards

文字の大きさを決めると,その大きさで書けるかどうか判定するのは割と簡単.

文字の大きさを線型探索しても大丈夫そうだけど,なんか怖くて二分探索してしまった.

こんな事したらバグ埋めそうだし,しなかったほうがよかったですね.

def binary_search(l, r) #return last index returns true
  return -1 unless yield l
  return r if yield r
  while l < r - 1
    m = (l + r) >> 1
    if yield m
      l = m
    else
      r = m
    end
  end
  return l
end

def ok?(sz, str, w, h)
  maxline = h / sz
  maxchr = w / sz
  arr = Array.new(maxline, maxchr)
  arr.unshift -1
  line = 0
  for i in 0...str.size
    if arr[line] >= str[i] + 1
      arr[line] -= str[i] + 1
    else
      line += 1
      return false unless arr[line]
      return false if arr[line] < str[i]
      arr[line] -= str[i]
    end
  end
  return true
end

T = geti
T.times do|cas|
  l = gets.split
  w, h = l[0..1].map(&:to_i)
  str = l[2..-1].map(&:size)
  l = 0
  sz = binary_search(1, [w,h].min) { |size| ok?(size, str, w, h)}
  print "Case ##{cas+1}: "
  puts sz < 0 ? 0 : sz
end

Auction

むず過ぎわろえる.

思い付いた方針は,

1.Nが小さい時: 普通にシミュレーション

2.lcm(M,K)が小さい時: ループの周期が短いので,シミュレートしてループ飛ばす.

3.gcd(M,K)が1でNが大きいとき: (Pi,Wi)が全通りでるので, 自明な解になる.

4.各k<=Mについて,Pi=kを満たすWiの最大を,合同式をexgcdとか使って解いて,そうなるようなiがN以下であるか見る的な事を繰り返す

くらい.4が詰みそうな気がするけど,どうなんだろう…

Alphabet Soup

やるだけゲー.

しかし書き方が汚なさ過ぎる…

もうちょっと纏めろよ俺…

cnt = gets.split(" ").map{|w|w.split("")}.flatten.map(&:to_sym).group_by{|a|a}
cnt.each{|k, v| cnt[k]=v.size}
res = [cnt[:H],cnt[:A],cnt[:C] ? cnt[:C]/2 : 0,cnt[:K],cnt[:E],cnt[:R],cnt[:K],cnt[:U],cnt[:P]].min_by{|a|a.nil? ? 0 : a}
res.nil? ? 0 : res

ツイートする