本履歴

購入した古本の履歴と時々プログラミング

GCJ2013(Google Code Jam 2013 Round 2)

さあて、Google Code Jam 2013 Round2。目標は1000位に入ってTシャツをゲットすること。
夕方から仮眠を取り、1時間前に起きて、幅優先探索深さ優先探索ダイクストラアルゴリズムを復習し、
日本時間土曜日23時からいざスタート。

問題Aを読んだ瞬間、解き方が分かったのでまずAから。

A. Ticket Swapping

乗客が電車内で入場券をシェアして、支払う電車賃の総額を最小にする問題。
ぱっと思い立ったアルゴリズムは、まず電車内に架空の代理人を設置し、乗車時に乗車券をその人に渡し、降車時はその人からもっとも距離が短くなる(=払う電車賃が小さくなる)乗車券をもらって支払えば最小化しそう。紙の上ではこれでうまくいくことが分かったので即実装。
費用の差を最終的に出力するのでNは消えるんだけど、余計なことを考えずにcost(n,k)を定義。うまく動くな。
次に代理人から最も距離が短くなる乗車券をもらうロジックだけど、ヒープで管理すればいいでしょうと、rubygemsのalgorithmsのMinheapを使ってみることにする。このheapにはどこから何人乗ったかという配列[o,p]を保存するようにすると、デフォルトのMinHeapでは対処できないので、Heapにブロックを渡して自分で定義することにした、といっても配列の最初の値を比較するだけ。最後に、_o, _eというハッシュに駅での乗降人数を保存して、乗降のイベントが発生する駅をeventに保存し、ソートしたeventの頭から逐次処理を行う。乗車イベントの場合はHeapに入れるだけで、降車イベントの場合は、Heapからデータを取り出して、降車人数が全員降りられるまで費用を計算する。人数が余ったらまたHeapに元に戻す処理も入れて完成、これまで30分かかってなく奇跡、早速実行。しかし、サンプルが通らず、なぜか全てのケースで0が出力される結果に。普段使ってないライブラリだからなにか見落としかなとか、M=1000だからHeapにこだわんなくても配列に入れておいて毎回配列の頭から検索し最大値求めれば通るよな等考えていたら、ん?最大値?、改めてソースコードを見直すとMinheapじゃん!ということでMaxheapにしてサンプルは通った!。しかし、smallにsubmitしても通らない。あれあれきな臭いですよ?ここから悪魔のデバッグタイムがスタートとは、誰が予想したであろうか・・・。smallの出力を改めて見てみるとマイナスがあり、通るわけないじゃん。どういうパターンの時このアルゴリズムでマイナスになるかを考えてみた。例えば例外パターンがあって、普通に支払ったままのほうがいいとか。30分ほどして閃いた! eventをuniqしないとだめじゃん。道理で降車時何回も余分に支払いマイナスになるはずだ。その処理を追加してマイナスが出なくなったので再submitするも、あれーまだsmall通らず。問題文を改めて見返すと、mod 1000002013の記述がサラッとあって、その処理も追加するけど、smallでは関係無いじゃん。ここから更にテストケースなどを作って分析し、ちょっとは直してsubmitを繰り返して悪戯に時は流れ、途中でCに懸想をするものの、結局スタートから2時間くらいして、num=0;maxheap.push([o,p-num]);となっていた箇所を逆にしないとダメなことが分かったw
早速submitしてsmallようやく通った!Largeもしゅんころ。
あと一問で、1000位はいけそうだが残り20分を切っている状況で、Bは入力が変な感じだし、問題文を理解しているC smallにすべてをかける・・・

#!ruby2.0

require "algorithms"
include Containers
include Algorithms

$n=0
def write(s)
  $n+=1
  s="Case \#%d: "%($n)+s.to_s
  puts s
  #$stderr.puts(s) 
end

def debug(s)
  $stderr.puts(s)
end

def cost(n,k)
  n*k-k*(k-1)/2
end

gets.to_i.times{
  n,m=gets.split.map(&:to_i)
  passengers=m.times.map{gets.split.map(&:to_i)}
  normal=passengers.map{|o,e,p|cost(n,e-o)*p}.inject(:+)
  cheat=0
  maxheap=Heap.new{|x,y|(x.first<=>y.first)==1}
  _o={}
  _e={}
  event=[]
  passengers.each{|o,e,p|
    if _o[o]
      _o[o]+=p
    else
      _o[o]=p
    end
    if _e[e]
      _e[e]+=p
    else
      _e[e]=p
    end
    event << o << e
  }
  event.uniq!
  event.sort!
  #p event

  event.each{|ev|
    maxheap.push([ev,_o[ev]]) if _o[ev]
    if _e[ev]
      num=_e[ev]
      while num>0
        o,p=maxheap.pop
        if num>p
          cheat+=cost(n,ev-o)*p
          num-=p
        elsif num<p
          cheat+=cost(n,ev-o)*num
          maxheap.push([o,p-num])
          num=0
        else
          cheat+=cost(n,ev-o)*num
          num=0
        end
      end
    end
  }
  write((normal-cheat)%1000002013)
}

C. Erdős–Szekeres

CはAができなくて涙目の時に問題文を読んでいて、エルデシュだから解きたいなと考えていた。んで、実はこの定理はアルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)の一番最初に載っていて知ってたのだが、逆に構成するとなるとどういう風に考えたらいいか難しい。残り時間も少ないので、smallだけでも解ければいいんだけど、Bruteforceで20!を調べるのは不可能。求める数列の最初を1.0にし、Aを参考にAが増加していればそれまでの最大値の倍を配列に追加、増加していなければBの情報から適切な小数を追加、みたいにして、浮動小数点の列を最後に1..nにすればいいのでは?と考えてコーディングしていたらタイムアップ。小数の精度があるからlargeは通らないかな。

B, Dは問題文すら読めなかったなー。
最終的な結果は、Rank: 1297 Score: 19
Tシャツゲットできず。もうちょっと途中で何とかしたかったかな。また来年頑張りましょう。
R2パスした方は次も頑張ってください!