読者です 読者をやめる 読者になる 読者になる

本履歴

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

コードゴルフ

CodeIQのid:Ozyさん開催コードゴルフコンペに参加していたので、自分のコード公開。
提出期限の月曜の明け方に縮めてた。縮まりまくって、徹夜だよ・・・あるあるーw
最初にハッシュにx,yでの値を保存していたけど、結局、1次元配列の方が短くなることが判明。$*に保存。
popで取り出したかったので、巻く方向は逆になってる。
n/2*-~nをn*n/2にすることで更に2バイト短くなることに気づいたけど、後の祭り。なんでこんなの気づかないんだろう。アホだな。
トップは120台だと思ってたけど、全然短くて、アルゴリズム重要だよなーと改めて感じた。
上級入れなくてかなり残念。

問題
https://codeiq.jp/ace/ozy4dm/q335

結果発表
http://codeiq.hatenablog.com/entry/2013/06/10/165837

最終版 139バイト

n=gets.to_i
x=n/2*-~n
j=m=0
(2*n+i=1).times{|d|i,j=-j,i;(d/2).times{$*[x]="%#{(n*n).to_s.size}d"%m+=1;x-=n*i+j}}
n.times{puts$*.pop(n)*" "}

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パスした方は次も頑張ってください!

競技プログラミング

Golf関係でCodeIQのアカウントを取ったのだが、計算幾何学の問題があったのでちょっと解いてみた。
https://codeiq.jp/ace/stakemura/q296
フィードバックが返ってきてるので、ソースコード公開してもいいんだよね。
Computational Geometry: Algorithms and Applicationsを参考というかパクって実装。3点が同一直線上に乗る場合の処理を追加した。乱択アルゴリズム

127.5, 75.5,
の入力に対し、gets.split.map(&:to_f)でうまく動くのが新しい発見。

#!ruby2.0

class Point
  attr_reader :x,:y
  def initialize(x,y)
    @x,@y=x,y
  end

  #return square Euclidean distance
  def dist2(point)
    (@x-point.x)**2+(@y-point.y)**2
  end

  #return Euclidean distance
  def dist(point)
    dist2(point)**0.5
  end
end

class Circle
  EPS=1e-30
  def Circle.generate_from_2points(p1,p2)
    center=Point.new((p1.x+p2.x)/2,(p1.y+p2.y)/2)
    circle=Circle.new(center,center.dist(p1))
  end

  #we assume p1 is a boundary(edge) point,
  #i.e. circle have to pass on it whether p2,p3 does not.
  def Circle.generate_from_3points(p1,p2,p3)
    a=2*(p3.x-p2.x)
    b=2*(p3.y-p2.y)
    c=2*(p2.x-p1.x)
    d=2*(p2.y-p1.y)
    x=p3.x**2-p2.x**2+p3.y**2-p2.y**2
    y=p2.x**2-p1.x**2+p2.y**2-p1.y**2
    
    #solve the fol. linear eq.
    #(a b)(x0)=(x)
    #(c d)(y0) (y)
    
    det=a*d-b*c

    #in case 3 points lie on some line,
    #we ignore mid-point and generate circle from two edge points.
    #the mid-point must be p2 or p3
    if det.abs<EPS
      circle=Circle.generate_from_2points(p1,p2)
      circle=Circle.generate_from_2points(p1,p3) unless circle.contains?(p3)
    end

    center=Point.new((d*x-b*y)/det,(-c*x+a*y)/det)
    Circle.new(center,center.dist(p1))
  end

  def initialize(center,radius)
    @center,@radius=center,radius
  end

  def contains?(point)
    @center.dist2(point)<=@radius**2
  end

  def to_s
    "[x=%f, y=%f, r=%f]"%[@center.x,@center.y,@radius]
  end
end

class Points
  def initialize(points=[])
    @points=points
  end

  def <<(point)
    @points << point
  end

  #return the [center_point,radius], the smallest enclosing disk of @points
  #this is randomized algorithm and done in O(n) expected time
  def smallest_enclosing_disk
    pts=@points.shuffle
    
    raise RunTimeError if pts.size==0
    return Circle.new(pts.first,0.0) if pts.size==1
    return Circle.generate_from_2points(pts.first,pts.last) if pts.size==2
    
    def min_disk_with_2points(pts,q1,q2)
      circle=Circle.generate_from_2points(q1,q2)
      pts.each{|p|
          circle=Circle.generate_from_3points(p,q1,q2) unless circle.contains?(p)
      }
      circle
    end

    def min_disk_with_point(pts,q)
      circle=Circle.generate_from_2points(pts.first,q)
      1.upto(pts.size-1){|i|
        circle=min_disk_with_2points(pts[0..i-1],pts[i],q) unless circle.contains?(pts[i])
      }
      circle
    end

    def min_disk(pts)
      circle=Circle.generate_from_2points(pts[0],pts[1])
      2.upto(pts.size-1){|i|
        circle=min_disk_with_point(pts[0..i-1],pts[i]) unless circle.contains?(pts[i])
      }
      circle
    end

    min_disk(pts)
  end

  def sed_valid?(circle)
    @points.all?{|p|circle.contains?(p)}
  end
end

#retrive data from standard input, format is
#127.5, 75.5,
#ruby2.0 smallestEnclosingDisk.rb < points.csv
csv_points=[]
while line=gets
  csv_points << line.split.map(&:to_f)
end

csv_points.uniq!

points=Points.new
csv_points.each{|p|
  points << Point.new(*p)
}

sed=points.smallest_enclosing_disk
puts sed

#puts points.sed_valid?(sed)

競技プログラミング

最近codechefサボってたんだけど、GCJ(Google Code Jam 2013)が開催中なので、腕試しに出てみたら五問解けた。あれあれ?簡単になってる??
Rubyで解くよう頑張った。

Matchsticks(http://www.codechef.com/MAY13/problems/MSTICK)

今月の中ではMatchsticksが一番面白かった。10^5個要素の配列Aがあって、A[x..y]の最大値(最小値)は?という問い(10^5個)に答えられればOK。
RMQ(wikipedia:en:Range_Minimum_Query)というのを使えたのだが、なんと自分自身これが初めての実装。蟻本を参考にコーディング。再帰的に処理するんだけど、これがうまく動くことが分かって、しばし感動した。
46.03secの解答。危なすぎるなあ。

MIN=0
MAX=1<<30

_n=gets.to_i
n=1
n*=2 until n>=_n
lb=n-1
#construct segment tree
$min_seg_tree=Array.new(4*n,MAX)
$max_seg_tree=Array.new(4*n,MIN)

gets.split.map(&:to_i).each_with_index{|b,i|
  $min_seg_tree[i+lb]=b
	$max_seg_tree[i+lb]=b
}

(lb-1).step(0,-1){|k|
	$min_seg_tree[k]=
    $min_seg_tree[k*2+1]<$min_seg_tree[k*2+2] ? $min_seg_tree[k*2+1] : $min_seg_tree[k*2+2]
	$max_seg_tree[k]=
    $max_seg_tree[k*2+1]<$max_seg_tree[k*2+2] ? $max_seg_tree[k*2+2] : $max_seg_tree[k*2+1]
}

#p $min_seg_tree
def find_min(a,b,k,l,r)
  return MAX if r<=a||b<=l
  if a<=l&&r<=b
    return $min_seg_tree[k]
  else
    vl=find_min(a,b,k*2+1,l,(l+r)/2)
    vr=find_min(a,b,k*2+2,(l+r)/2,r)
    return vl<vr ? vl : vr
  end
end

def find_max(a,b,k,l,r)
  return MIN if r<=a||b<=l
  if a<=l&&r<=b
    return $max_seg_tree[k]
  else
    vl=find_max(a,b,k*2+1,l,(l+r)/2)
    vr=find_max(a,b,k*2+2,(l+r)/2,r)
    return vl<vr ? vr : vl
  end
end

q=gets.to_i
q.times{
  l,r=gets.split.map(&:to_i)
  to_rear_min_time=find_min(l,r+1,0,0,n)
  to_rear_max_time=find_max(l,r+1,0,0,n)

  from_rear_max_time=0
  if 0<l
    from_rear_max_time=[from_rear_max_time,find_max(0,l,0,0,n)].max
  end
  if r<n-1
    from_rear_max_time=[from_rear_max_time,find_max(r+1,n+1,0,0,n)].max
  end

  burn_down_time=to_rear_min_time+[(to_rear_max_time-to_rear_min_time)/2.0,from_rear_max_time].max
  puts "%.1f"%burn_down_time
}

Witua and Math(http://www.codechef.com/MAY13/problems/WITMATH)

nが与えられた時、2..nの中でphi(i)/iを最大にするiを出力する問題。
オイラーのファイ関数へのwikipediaがあるので、結局n以下の最大の素数を見つけることと同値であることが分かる。nが10^18とでかいので、正確に求めると時間がかかりすぎるはずで、確率的に求めればよさげ。ということでwikipedia:ミラー-ラビン素数判定法を使って通った。4^-50の確率で間違ってしまうけど、宝くじに当たるより難しいはず、うむ。nが素数である確率は1/ln(n)なので10^18だと50個に1個くらいの確率で素数になるはずだから、余裕で間に合うのかな。計算量とかは全く考えなかったけど、出題者が合成数が長く続く区間を選択してきたらどうなるんだろう、とは思った。2..10^18までで合成数が続く区間で最長のものや如何?

def modpow(base, power, mod)
  result = 1
  while power > 0
    result = (result * base) % mod if power & 1 == 1
    base = (base * base) % mod
    power >>= 1
  end
  result
end

def prime?(n)
  return true if n==2
  return false if n%2==0
  return true if n==3
  return false if n%3==0
  return true if n==5
  return false if n%5==0
  return true if n==7
  return false if n%7==0

  n1 = d = n-1
  d >>= 1 while d & 1 == 0
  50.times{
    a = rand(n-2) + 1
    t = d
    y = modpow(a,t,n)
    while t != n1 && y != 1 && y != n1
      y = (y * y) % n
      t <<= 1
    end
    return false if y != n1 && t & 1 == 0
  }
  return true
end

gets.to_i.times{
  n=gets.to_i
  n.step(2,-1){|m|
    if prime?(m)
      puts m
      break
    end
  }
}

GCJ2013(Google Code Jam 2013 Round 1C)

Round 1Cは練習でponanza戦を観戦しつつ参加してみた。ラウンド中はinputを落とせないので、紙と頭のなかで解いて、後日コーディングしてみた。
Aは問題文を読み間違いして全然見当違いのコードになってた・・・ので後で解く。
([1,0,1,1,1,0,1,0]なる1,0からなる数列aと正数n:givenのとき、sum(a[i..j])>=nとなる(i,j)の個数をカウントせよと勘違い)
Cは問題文めんどくさかったので読んでない。smallは多分簡単なんだろうなあ。

B. Pogo

1,2,3,4,5,...Nと平面上原点から東西南北に自機を動かして(X,Y)に移動できるか、という問題。X,Yを原点に移動すると考えても良いね、N,N-1,...,3,2,1と(X,Y)を移動して原点に行けるか?。Largeは移動回数Nを最小にしなくてはいけない。
まず、smallはX,Yの絶対値が100以下と、最大500回動かしてもいいことからすぐ解ける。というのも、N回目とN+1回目を組み合わせることで必ず一歩前進できるから(365歩のマーチ戦略)、高々400回の移動で目的地へ移動可。ただし、この戦略はLargeでは通用しない。そこで、色々紙の上で考えてみた。問題文を、集合{1,...,N}を2つのグループに分割し、それぞれのグループ内で加減をうまくしてX,Yを生成できるか?と翻訳してみたり。だけどどうもうまくいかない。悩んだ末、Nが十分大ならば365歩のマーチ戦略で任意の点に行けることから、逆にNが与えられた時(X,Y)に到達できるか?という問いにオレはどう答えるのかと考えてみた。すると、X,Yのうち絶対値が大きい方にNを加減し新しいX,Yとし、次にN-1をX,Yのうち絶対値が大きい・・・というようにGreedyに計算し、最終的に原点にいるかどうかで答えられることが直感的に分かった。でも、1から順次調べていくとTLEだよなあということで次に、n回で原点に到達可能ならばn+4でも可能であるっぽいことがわかった。これも365歩のマーチ2回分だから、パリティが合うからかな。すると、ここで、アハ体験。バイナリサーチが使えることに気がついた。ステキすぎる。つまり、(1,2,3,4),(5,6,7,8),(9,10,11,12),...というようにグルーピングして、その中に原点にいける回数が一つでも存在する最小グループを見つければOK。適当に0番目と10^5番目のグループ間でバイナリサーチしたら、Large正解になりました。

#!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 solve(n,x,y)
  n.step(1,-1){|i|
    if x.abs>y.abs
      if x>0
        x-=i
      else
        x+=i
      end
    else
      if y>0
        y-=i
      else
        y+=i
      end
    end
	}
  x==0&&y==0
end

def solve4(n,x,y)
  (4*n+1).upto(4*n+4){|i|return i if solve(i,x,y)}
  false
end

def ans(n,x,y)
  ret=""
  n.step(1,-1){|i|
    if x.abs>y.abs
      if x>0
        x-=i
        ret<<?E
      else
        x+=i
        ret<<?W
      end
    else
      if y>0
        y-=i
        ret<<?N
      else
        y+=i
        ret<<?S
      end
    end
  }
  ret.reverse
end

#find the smallest group in [4*l+1,4*l+2,4*l+3,4*l+4],...,[4*r+1,4*r+2,4*r+3,4*r+4]
#s.t. at least one of them satisfies solve(n,x,y) 
def b_search(l,r,x,y)
  if l<=r
    m=(l+r)/2
    ret=solve4(m,x,y)
    if ret
      _ret=b_search(l,m-1,x,y)
      ret=_ret if _ret
    else
      ret=b_search(m+1,r,x,y)
    end
    return ret
  else
    false
  end
end

gets.to_i.times{
  x,y=gets.split.map(&:to_i)
  n=b_search(0,10**5,x,y)
  write(ans(n,x,y))
}

製本



この前のPDFを製本してみた。
どうだろうか、やはり紙で読むのは電子データにはない温かみがある、素晴らしいね。
紙の準備:30分
印刷:30分
折丁作成:30分
表紙づくり:45分
糸綴じ:2時間
仕上げ:1時間

久しぶりなので時間がかかった。
テキストは、NHK趣味悠々のお気に入りをとじるを使った。

GCJ2013(Google Code Jam 2013 Round 1B)

Round 1Bは毎回深夜回。土曜夕方、なぜか成分献血して、その後20時から仮眠を4時間取ってAM1時スタート。
前回からの変更点はTextEditorがsublime(registered!!)になったこと。買っちゃいました。てへぺろ

問題Aが吸収ゲーでSとLで点数に差がない、Bは落ちゲーで説明を漏れなく読むのは面倒そう。Cは辞書を別途ダウンロードせよとかあるので、Aから。

A. Osmos

まず、与えられたmotesを小さい順にソートしてごにょごにょするのは分かった。Greedyっぽい。吸収できるなら吸収するのが最適なんだけど、吸収できない(自分のサイズ以上)場合に自分のsize-1を生成して吸収のプロセスをある程度踏んで自分のサイズをでかくしてから該当moteを吸収するのか(その分手数がかかる)、それとも最初からeliminateしてしまうのか(手数は1)、その先どういうサイズのmoteが待ち構えているかを読まないと判断つかないっぽい。SとLで点数差がないので同じコードで通るはずだから、Lも通すことを考えると全パターンは2^100の場合を考えることになって、Bruteforceでは通りそうもないなあ、もっとうまい方法があるのかしら、と苦吟していたらあれよと30分経って、この子は解けない子だ(いつものパターンw)と判断し、泣く泣くBへ。この時点でAのSとLを通している人が結構いて血の気が失せた。

B. Falling Diamonds

方眼紙にシチュエーションを書いてみたら、だいたい把握できた。パスカルの三角形っぽいなあ。ニコ動にPhunで上からボールを二項分布するパチンコ釘に落とした時、パスカルの三角形を描くか実験した動画があったんだけど、それを思い出した。
ある程度落とすと凸の山完成形ができるので、その時内部のポジションの確率は1のはず。
凸山は1, 1+2+3, 1+2+3+4+5, ...個ごとにできるよね。
凸山完成形から2つ外のポジションも強制的に確率0でることもわかる。
それ以外の時に確率を正確に計算すればOKっぽい。つまり、1+2+3+...+2k+1の凸山完成形に更にr個のダイアモンドを降らした時に(X,Y)にダイアが行く確率。kは(X+Y)/2で分かるね。
対称性から、x座標は正としても一般性を失わないのが分かる。(X,Y)の座標が高さh番目とすると(Y座標から判別可能)、凸山ができた上で、更にr個降った時にh個以上右に行く確率が求めるもの。
r個のダイアをランダムに左右2つに分けた時、右がh個以上になる確率が求めるものかな。
ただ注意しなくちゃいけないのは、左がMAXまで埋まると、次以降のダイアは自動的に右に行ってしまう点。

\sum_{l=h}^{r}\left(\large\begin{array}{GC+23}r\\l\end{array}\right)/2^r

を計算することにしたら、なんとかサンプルにあったのでそのまま提出。ホット一息。この時点で1500位くらい。Aが解けてないのが痛すぎるね。
Largeを考えたんだけど、二項係数の和を考えているのでO(N^2)だから、N=10^6だと全然だめじゃんと判断し、別解を考えてみた(後で考えると、凸山完成形できたあとの残りのダイヤなので10^3程度?!)。28点と点数が高いのもオレには解けないというバイアスかかってるなあ。
二項分布は正規分布で近似じゃなかったっけ、そうだ、上の式の計算は、正規分布の右側積分してるのと同じじゃね?とか離散の世界から連続へ宗旨替えしてwikipediaめぐりをしたが、どうもよくわかんない。Largeのサンプル簡単に作れるんだから試せばいいものを・・・
このままだと死亡すると判断しCへ

#!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

#return combination (n,r) :the number of way choose r from n 
def combination(n,r)
  r=n-r if r>n/2
  return 1 if r==0
  result=1
  n.downto(n-r+1){|i|result*=i}
  r.downto(2){|i|result/=i}
  return result
end

def distribute(a,n,k)
  #debug "%d %d %d"%[a,n,k]
  return 1.0 if n-a/2>=k
  return 0.0 if k>n
  return 0.0 if (a/2==k-1)&&(n<a)
  ret=0
  k.upto(n){|r|ret+=combination(n,r)}
  n.times{ret/=2.0}
  ret
end

gets.to_i.times{
  n,x,y=gets.split.map(&:to_i)
  x=x.abs
  r=1+(x+y)/2
  fixed_num=r*(2*r-1)
  pre_fixed_num=(r-1)*(2*(r-1)-1)
  ans=0.0
  if fixed_num<=n
    ans=1.0
  elsif pre_fixed_num>n
    ans=0.0
  else
    h=y+1
    diff_num=n-pre_fixed_num
    ans=distribute(fixed_num-pre_fixed_num,diff_num,h)
  end

  write("%.9f"%ans)
}

C. Garbled Email

辞書をダウンロードし、長さを見てみたら、最大の長さは10だった。DPで解けそうなのでその方針で考える。まず、与えられた辞書をハッシュに登録。
DP(X,Y)でS[X..Y]を辞書を使って表示する場合の最小変更数として(表現できない場合は∞)、DP(1,Length(S))を求めたい。
DP(X,Y)はmin{DP(X,i)+DP(i+1,Y)}のはず。問題はそれぞれ文字が4つ前後できるという点だけど、全パターンでも4^10で間に合うんじゃないかとこの時は考えた(今だと8^10だからダメっぽい)。ごちゃごちゃ書いたらうんこになったので多分だめだなと諦めてAへ。この時点でAが速攻解ければ、みんなBが解けてなくて何とかなるようなのだ・・・。

A. Osmos

もう一度問題文を初めて読む気持ちで読んで、紙上でチェックしていたら、moteを生成して取り込むと大体2倍になることが判明。セルが栽培マンを蒔いて、吸収してるのをイメージ(古!)。Largeでも10^6だから、100回生成&吸収なんてありえないじゃん!つまり全パターン調べても時間内でいけることに気づいて、再帰的にコードを書いて、Smallは通った! Largeは、テストケースを作ってみたら時間内に終わることが確かめられたので、そのままsubmit。この時点で800位くらい。B Largeのことは忘れて、Cのコードを書いていたらタイムアップ。

結果、ドラムロールオン♪

Rank: 862 Score: 36でパスしたようです!!

終了後、B LargeをSmallのコードでsubmitしたらそのまま通ってびっくり。ダメ元でsubmitするべきだよなーと反省点(収穫)が多いラウンドでした。
自分は1Cも当然解きますよー。実力を試す良い機会ということで、ダメだった方も前向きに頑張りましょう。今年のGCJは毎回趣向があって面白いなー。

#!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 min(a,motes)
	return motes.size if a==1
	return 0 if motes.empty?
	if a>motes.first
		return min(a+motes.first,motes[1..-1])
	else
		gain=0
		b=a
		while b<=motes.first
			b+=b-1
			gain+=1
		end
		return [min(a,motes[1..-1])+1,min(b+motes.first,motes[1..-1])+gain].min
	end
end

gets.to_i.times{
  a,n=gets.split.map(&:to_i)
  motes=gets.split.map(&:to_i).sort
  write(min(a,motes))
}