本履歴

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

GCJ2013(Google Code Jam 2013 Round 1A)

今年のGCJ Round 1は、ひとつの週末に固まっていないのがうれしいなと思ってのんびりしていたら、あっという間に当日になり、GW初日の土曜日10時から開始。
8時に起き、いい天気なので部屋を掃除してたら開始5分前になっていてびっくり。急いで準備して30秒前に着席。深呼吸。
前回からの変更点はTextEditorがsublime(unregistered)になったこと。オレ、このGCJ Round 1突破したら、registerするんだ・・・
つーか、登録しないと時々保存するときにはよregisterしろ攻撃を受けるな、これ。

問題文を読むまでもなく、Aのsmall、Largeの点の差がないのでAから。

A. Bullseye

同心円で半径rから先を交互に黒と白(=塗らない)と塗っていった時に塗れる黒の個数の最大値を求めよという問題。等差数列の和を求めて与えられたtを超えない項数xが求めるもの。
問題文をちゃんと読まず、Piを入れて計算して全く数字が合わず絶望に身をよじる。ぐぬぬぬ。最大値を求めよという問いの形がちょっと気になって、順番に塗っていくのではないのかな、と勘違いする。Maria draws the first black ring around a white circle of radius r cm.のaroundの意味を考えて、外側じゃなく内側にも塗るのか等々いろいろパターンを考えたがサンプルの出力に合うものはできなかった・・・。30分以上経ち、問題文の図がだんだんぐるぐる回り始め気持ち悪くなり、これはオレには解けない問題だと考え、1000人がA smallを通しているのを尻目に、Bへ。今年も厳しい感じ。

B. Manage your Energy

時間がないので、問題文をななめ読み。順番にやらなきゃいけないアクティビティがあって、自分のエナジーをそれに注ぐと、アクティビティの価値*注いだエナジーの結果を取得できる。各アクティビティ前に定数エナジーを回復できるときに、取得できる最大の結果の総和を求める問題。smallの制限を見ると、1<=E<=5、1<=N<=10なので、毎回全パターンのエナジーを注ぐ場合(高々0から5の6パターン)を計算しても6^10で間に合いそうなので、small一点集中。波紋使いの気分だよ。10分くらいで再帰的にコードを書いて、smallが通ってホット一息。この時点で600位くらいまでjump up。

#!ruby2.0

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

def max_gain(score,c,e,r,n,a)
  c=[c+r,e].min
  if a.size-1==n
    return score+c*a.last
  else
    return (c+1).times.map{|cc|max_gain(score+cc*a[n],c-cc,e,r,n+1,a)}.max
  end 
end

gets.to_i.times{
  e,r,n=gets.split.map(&:to_i)
  a=gets.split.map(&:to_i)
  write(max_gain(0,e,e,r,0,a))
}

C. Good Luck

良く考えたら、この問題のsmallが一番点数小さいのか、なら簡単じゃんとこちらもななめ読み。
S={2, 3, 4, 5}から3個任意に取って、それを推測するゲーム。全問正解でなくてもいいというユニークな試み。さすがGoogleさん。smallは半分Guessできればいいそうだ。まあ、smallは何回でもチャレンジできるから確率とか検討する前に試しにやってみるのが吉。
方針は、Sから3個とった集合(の中から確率0.5で元を取って積を計算)が取れる値域をハッシュに求めておいて、与えられる結果の積のヒントから候補の集合を絞っていき、最後に候補の中からランダムで一つ選択。これも最初候補が空集合になったりして、デバッグ地獄に落ちる。20分くらい世界に対する呪詛を唱えていたら、Note that some numbers might be equal.の文が目に入って、即repeatedを付けてrepeated_combinationにして、なんとか通った。通すまでも、出力にスペース入れたりして3回間違ったが・・・

#!ruby2.0

$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 reg(h,a,b)
  if h[a]
    h[a] << b
  else
    h[a]=[b]
  end
end

srand(42)
gets.to_i.times{
  a=[]
  r,n,m,k=gets.split.map(&:to_i)
  #for small case
  cards=[*2..m]
  h={}
  cards.repeated_combination(n){|cc|
    reg(h,1,cc)
    1.upto(n){|nn|cc.combination(nn){|ccc|
      reg(h,ccc.inject(:*),cc)
    }}
  }

  r.times{
    prods=gets.split.map(&:to_i)
    cand=[]
    h[prods.first].each{|cc|cand << cc.dup}
    #debug cand
    prods.each{|prod|
        cand=cand&h[prod]
    }
    #debug cand
    a << cand.sample
  }
  write("")
  a.each{|_a|puts(_a*"")}
}

A. Bullseye

最後に1時間くらい残ってAへ。問題文をもう一度読み、Piを出さないでいいことに気付く。やられたー。2次方程式の係数を変更してサンプルの最後以外は合うコードができた!どうせLargeは不動点小数の精度で引っかかるパターンだなとわかりつつ一秒でも早く通したいのでそのままsmallにsubmit、パス。Largeはbigdecimal使えばいいでしょ!と2次方程式の係数をBigDecimalにしたらサンプルの最後も合ったのでそのままsubmit。残り30分弱。この時点で900位後半で、あれよあれよと1000位以下に落ちる。A Largeは精度の問題で落とす人が多いだろうと予想してムフフしていたら、なんと自分が落ちていて呵々大笑。自分のoutput見てみたら、出力0とかあってダメダメじゃん(問題文に1以上が保証されている)。後になってbigdecimalとか使うより、2次方程式の解で計算した後、検算すればいいだけだと気づいた。解の候補となる値が分かるのだから、その前後+-1で等差数列の和がt以下を満たすかどうか。

結局、smallのみの33点1552位。
パスしたみなさんおめでとうございます!
自分は今年もまだまだ続きます。

#!ruby2.0
require 'bigdecimal'

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

gets.to_i.times{
  r,t=gets.split.map(&:to_f)
  a=BigDecimal("2")
  b=BigDecimal((2*r-1).to_s)
  c=BigDecimal((-t).to_s)
  root=(-b+(b*b-4*a*c)**0.5)/(2*a)
  ans=root.floor
  write(ans)
}