Home > Tags > codejam

codejam

Google Code Jam 2008 Qualification Round

2008-07-19 (Sat)
default
codejam | google

Google Code Jam 2008 に参加してます。

Qualification Round は A,B を解いて Score:50、Rank:2246 でした。Cむずいよ。 Rubyで書いてます。irbがつかえるこの幸せ。 irbでインタラクティブにデバッグしつつ、本番の入出力をケアするためのコードを最終行にいれてます。

A. Saving the Universe

さいしょ、レポートの出力形式を間違っていて (#0から出力してた)、なんでこれで違うんだろうと首をかしげてた。1回ぶんのmiss submit。

戦略は以下:

入力を先頭から順になめて、エンジンを set に追加
すべてのエンジンが set にはいったら、カウンタをあげて、setをリセット

電車の中で、この単純な解法に気づいたときはうれしかった。

#!/usr/bin/env ruby
# Saving the Universe
#   at Google Code Jam 2008, QR A
#
# use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]
#
# author:mootoh
#
require 'logger'
 
$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''
 
def test(engines, queries)
  state = []
  count = 0
 
  queries.each do |query|
    state.push query
    state.uniq!
    if state.size == engines.size
      $log.debug("change !")
      count += 1
      state = [query]
    end
 
    $log.debug(state)
  end
 
  count.to_s
end
 
def main(file)
  n = file.gets.chomp.to_i
  n.times do |i|
    s = file.gets.chomp.to_i
    engines = []
    s.times {|j| engines.push file.gets.chomp}
 
    q = file.gets.chomp.to_i
    queries = []
    q.times {|k| queries.push file.gets.chomp}
 
    puts "Case ##{i+1}: " + test(engines, queries)
  end
end
 
main(ARGF) unless $PROGRAM_NAME == 'irb'

Train Timetable

これも電車で解いた。オブジェクト指向っぽく考えてたら、できそうな気がして。遅いけど、実行時間は今回問われてないのでおk。

#!/usr/bin/env ruby
# Train Timetable
#   at Google Code Jam 2008, QR B
#
# use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]
#
# author:mootoh
#
require 'logger'
 
$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''
 
class Arrow
  attr_accessor :from, :to
  def initialize(from, to)
    @from = from; @to = to
  end
 
  def start_at?(at)
    @from == at
  end
  def to_s; "#{from} -> #{to}"; end
  def inspect; to_s; end
end # Arrow
 
class Train
  attr_accessor :available_at
 
  def Train.tt=(x); @@tt = x; end
  def Train.tt; @@tt; end
 
  def initialize(at)
    @available_at = at
  end
 
  def departure(to)
    @available_at = to + @@tt
  end
 
  def to_s; "Train@:#{@available_at}"; end
  def inspect; to_s; end
end # Train
 
class Station
  attr_accessor :trains, :arrows, :count
 
  def initialize(arrows)
    @trains = []
    @arrows = arrows
    @count = 0
  end
 
  def train_available_at(at)
    t = @trains.find { |train| train.available_at <= at }
    if t
      @trains.delete(t)
      t
    else
      @count += 1
      Train.new(at)
    end
  end
 
  def to_s
    'Station: ' + [
      @trains.map {|x| x.to_s},
      @arrows.map {|x| x.to_s},
      @count.to_s
    ].join(' : ')
  end
  def inspect; to_s; end
end # Station
 
 
def parse(n, file)
  ret = []
  n.times do |i|
    x = file.gets.chomp.split(/\s+/).map do |x|
      h, m = x.split(/:/).map {|y| y.to_i}
      h * 60 + m
    end
    ret.push Arrow.new(x[0], x[1])
  end
  ret
end
 
def main(file)
  n = file.gets.chomp.to_i
  n.times do |j|
    tt = file.gets.chomp.to_i
    Train.tt = tt
    na, nb = file.gets.chomp.split(/\s+/).map {|x| x.to_i}
 
    arrows = [na,nb].map {|x| parse(x, file)}
    starts = (arrows[0] + arrows[1]).map {|x| x.from}.sort.uniq
    stations = arrows.map {|x| Station.new(x)}
 
    starts.each do |start|
      $log.debug("start at #{start} --------------------")
      2.times do |i|
        st_i = stations[i]
        st_o = stations[(i+1)%2]
 
        departures = st_i.arrows.find_all {|x| x.start_at?(start)}
        $log.debug("departures=#{departures.size}")
        departures.each do |d|
          train = st_i.train_available_at(start)
          train.departure(d.to)
          st_o.trains.push train
          $log.debug(train)
        end
        st_i.arrows -= departures
 
        $log.debug("#{i == 0 ? 'A' : 'B'}: #{st_i}")
        $log.debug("#{i == 0 ? 'B' : 'A'}: #{st_o}")
      end
      $log.debug('------------------------------------')
    end
    puts "Case ##{j+1}: #{stations[0].count} #{stations[1].count}"
  end
end
 
main(ARGF) unless $PROGRAM_NAME == 'irb'