Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2013-01-29Facebook Hacker Cup Qual

でした.

とりあえず全部Rubyで書いた.

A - Beautiful Strings

アルファベットに1〜26のユニークなスコアを自由に割り当てて,出現1回ごとにその点数が加算されるようにする.

文字列が与えられた時,得られる最高得点を求めよ.

アルファベットごとに出現頻度を数えて,多いものから順に高得点を振っていくだけ.

#!/usr/bin/ruby

def solve
  gets.to_i.times do |i|
    res = yield
    puts "Case ##{i+1}: #{res}"
  end
end

solve do
  str = gets.chomp.downcase
  arr = str.each_char.select{|c| ("a".."z").include?(c)}.to_a.sort.chunk{|c| c}.map{|ch,lst| [ch,lst.size]}
  score = 0
  arr.sort_by!{|e| e[1]}.reverse.each_with_index do |e, idx|
    score += (26-idx) * e[1]
  end
  score
end

B - Balanced Smileyes

文字列が与えられるので,カッコ()がバランスしているか確かめる.

ただし,顔文字smily :)とflowny :(が出現することもあり,これらはカッコに含めない.

顔文字をバラしてもよく,1通りでもバランスしている読み方があればOKなので(:)みたいなのも通る.

文字列長が最大100なので,先頭から文字列を見ていってi文字目でありうるネストレベルについてDP

カッコが出てきたらネストレベルを変動させる.

また,その前に:が付いていたら変動しないパターンも考慮に入れる.

これで最後まで見ていって,文末でネストレベル0が可能ならバランスしてる.

#!/usr/bin/ruby

require 'set'

def solve
  gets.to_i.times do |i|
    res = yield
    puts "Case ##{i+1}: #{res}"
  end
end

solve do
  str = gets.chomp
  dict = Set[0]
  str.each_char.each_with_index do |c, idx|
    case c
    when "("
      # Treat as open
      next_dict = Set.new(dict){|key| key+1}
      if idx > 0 && str[idx-1] == ":"
        # Treat as smily
        next_dict.merge(dict)
      end
      dict = next_dict
    when ")"
      # Treat as close
      next_dict = Set.new(dict){|key| key-1}
      next_dict.reject!{|key| key < 0}
      if idx > 0 && str[idx-1] == ":"
        # Treat as frowny
        next_dict.merge(dict)
      end
      dict = next_dict
    end
  end
  dict.include?(0) ? "YES" : "NO"
end

C - Find the Min

長さKの乱数列が与えられて,K+1番目以降を「直前K要素に含まれない非負整数のうち最小のもの」として数列を拡張する.

このときN番目の数を求めよ(ただしN ≧ K+1は保証されている).

鳩ノ巣原理より,拡張部分の要素は必ず[0,K]に含まれる.

これを繰り返していくと,K+1番目から2K+1番目までのK+1個は[0,K]の数値がちょうど1回ずつ出現することがわかる.

さらに2K+2番目はK+1番目と等しくなり,以降このK+1個の列が繰り返し出現することになる.

あとは「直前K要素に含まれない最小の非負整数」を高速に求められれば良い.

これはPriority Queueを使うとできる.

最初は初期乱数列に出現しない数を全部Priority Queueに突っ込んでおき,初期乱数列を消化していきながら,出現カウントが0になった数は新しくPriority Queueに突っ込んでいく.

(乱数列内の数はuniquenessが保証されていないので,ここで出現カウントを考えないと間違えるが,サンプルが優しいのでひっかかる)

RubyではPriority Queueがない(PriorityQueueというgemがあるけど,Cコードなので負けた気がする)ので,せっかくだし自前でHeapを書いた.

priority_queueというgemもあるけど,これは罠なので使ってはいけない.

#!/usr/bin/ruby

def solve
  gets.to_i.times do |i|
    res = yield
    puts "Case ##{i+1}: #{res}"
  end
end

class Heap
  def initialize
    @buf = [nil]
  end

  def push(val)
    @buf << val
    pos = @buf.size - 1
    while pos != 1 && @buf[pos/2] > @buf[pos]
      @buf[pos/2], @buf[pos] = @buf[pos], @buf[pos/2]
      pos /= 2
    end
  end
  alias :<< :push

  def pop
    res = @buf[1]
    @buf[1] = @buf.pop
    pos = 1
    loop do
      left = pos*2
      right = left+1
      min_one = right
      min_one = left if @buf[min_one].nil? || @buf[left] < @buf[min_one]
      if @buf[min_one] && @buf[pos] > @buf[min_one]
        @buf[pos],@buf[min_one] = @buf[min_one],@buf[pos]
        pos = min_one
      else
        break
      end
    end
    res
  end
end

solve do
  n, k = gets.split.map(&:to_i)
  a, b, c, r = gets.split.map(&:to_i)
  arr = [a]
  (k-1).times do |i|
    arr << (b*arr[i]+c) % r
  end

  in_arr = {}
  arr.each do |val|
    in_arr[val] ||= 0
    in_arr[val] += 1
  end
  
  heap = Heap.new
  (0..k).each do |i|
      heap << i if not in_arr.has_key?(i)
  end

  head = []
  arr.each do |val|
    min = heap.pop
    head << min
    in_arr[min] ||= 0
    in_arr[min] += 1
    in_arr[val] -= 1
    if (0..k).include?(val) && in_arr[val] == 0
      heap << val
    end
  end
  head << heap.pop
  #p arr
  #p head
  head[(n-k-1) % (k+1)]
end
 |