れんしゅうちょう。

■ [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

ツイートする

■ [FaceBookHackerCup]FaceBook Hacker Cup 2012 R1 17:01

○|○|○

148位 7:31:22

QualよりR1の方が簡単てどういう事なの…

そして結果出るの遅すぎじゃないの…

試合中に採点してればこんな遅くなる事ないんじゃないの…

以下ソースとか.例によってテンプレ省いてあるので,全部見たければScorebordから.

Checkpoint

これが一番難しかったように感じた.

前計算でnCrとかn=max(S)まで全部求めていたら割としぬる気がするので,なるべくはしょった.

n=O(sqrt(max(S)))まで求める感じにしたけど,別にO(qbrt(max(S)))とかにも出来るなぁ.

問題読んだ時,Checkpointは複数作れるのかと思って,無理ゲーとか思っていたけれど,そんなことなかった.

nCr=Kになるような各Kに対して最小のnを返すような感じのアレ.

@memo = {}
def init(max)
  dp = [1]
  1.upto(max) do |i|
    nex = [0] * (i+1)
    nex[0] = nex[i] = 1
    for j in 1...i
      tmp = dp[j-1] + dp[j]
      if tmp <= max && dp[j] != 0 && dp[j-1] != 0
        nex[j] = tmp
        @memo[tmp] = i if @memo[tmp].nil? || @memo[tmp] > i
      else
        break
      end
    end

    break if nex[2] && nex[2].zero?
    dp = nex
  end
end
def get_min_N_from_Comb(c)
  return @memo[c] unless @memo[c].nil? # nCk k>=2
  return c #cC1 = c
end

SIZE = 10000000
init(SIZE)

each_case do
  s = geti
  res = Infinity
  s.divisor.each do |d|
    break if d  * d > s
    res = [res, get_min_N_from_Comb(d) + get_min_N_from_Comb(s/d)].min
  end
  res
end

Recover the Sequence

なんか,最初の配列のk番目がどこに行くかを,入力にそって分岐してやる事によって求めて,その置換によってソート済になるような配列を求めてやるみたいな事をした.

置換の逆元求めるだけというか.

def mergeX(arr1, arr2)
  res = []
  until arr1.empty? || arr2.empty?
    #puts "#{arr1[0]},#{arr2[0]}"
    if @str[0] == '1'
      res << arr1.shift
    else
      res << arr2.shift
    end
    @str = @str[1..-1]
  end
  return res + arr1 + arr2
end
def merge_sortX(arr)
  n = arr.length
  return arr if n <= 1
  mid = n / 2
  first_half = merge_sortX(arr[0...mid])
  second_half = merge_sortX(arr[mid..-1])
  #p "#{first_half} #{second_half}"
  return mergeX(first_half, second_half)
end
def decode(size, str)
  @str = str
  merge_sortX((1..size).to_a).zip(1..size).sort.map{|a|a[1]}
end

each_case do
  n = geti
  s = gets
  checksum(decode(n, s))
end

Squished Status

通ったから言える,DPやるだけゲー.

やるだけといいつつ,割とミスが怖い.

入力がスペースで区切られてたりして怖いが,最初に入力ファイル開いて置換した僕に隙はなかった!

この問題,0xfaceb00cが言いたかっただけじゃないの…

@M = 0xfaceb00c

def solve(m, str)
  return 0 if str[0] == '0'
  return 0 if str[0].to_i > m
  dp = [0]*(str.length+10)#k文字目までの組み合わせ
  dp[-1] = 1
  for i in 0...str.length #考えてるうちの最後の文字
    i.downto(0) do |j| #最初の文字
      next if str[j] == '0'
      break if str[j..i].to_i > m
      #p "dp[#{i}] += dp[#{j-1}]"
      dp[i] += dp[j-1]
      dp[i] %= @M
    end
  end
  #p dp
  dp[str.size-1]
end
each_case do
  m = geti
  str = gets.chomp
  solve(m,str)
end

ツイートする