れんしゅうちょう。

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

ツイートする