本履歴

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

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))
}