本履歴

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

GCJ2012(Google Code Jam 2012 Round 2)

結局、Round 1は999位でぎりぎりパスできたのだが、Round2で撃沈。Rank: 1863 Score: 6

Round 2

土曜の23時スタート。ドデカミンストロングを飲んで頭をすっきりさせ挑んだ。
まず、点数と問題文を眺めてDは迷路っぽので後回し。Aが点数的に簡単そう。Cは図から奥の山のピークが手前の山頂から見えるかどうかで俺ごのみの問題だが点数高いので難しそう。
ということで、A,B,C,Dの順決定。

A. Swinging Wild

問題文に知らない単語がたくさんあってAlcで調べながら読む。要するに、ターザンだな。
蔦=Range[d_i-l_i,d_i+l_i]と考えて、蔦をうまく選んでRange[0,D]をカバーできるかという方向で考え始めた。サンプルを手計算で解いていってみるが、サンプル2がどうも合わない。蔦の長さが十分なので3番目の蔦に1番目から行けるはずだが・・・、他にも2番目経由でも行けるじゃん(蔦をピンと張らなくちゃいけない&降りちゃいけないが読み抜けていた)、と勘違いする。
そのうち、サンプルの絵からピンと蔦を張る必要性が見えてきたが、混乱してしまって何を変数として管理するかよく分からなくなる。紙上でいろいろ書き散らす。30分くらい経過。後で考え直すのが良さそうとハヤる気持ちを抑えてBへ。

B. Aerobics

問題文をナナメ読みし与えられた長方形に円をパッキングする問題と理解した。SPOJにあった球面上に点を配置して最小距離を最大にする問題を思い出した。
smallは乱択でいけるじゃんN=10だし、間違ってもtestcaseが手に入ったと思えば・・・ということで即コーディング開始。4分内に終わるかだけが心配だったがあっさり終わる。しかし、submitするとWA食らう。計2回。目をサラにしてチェックしていたらintersectionのチェックで半径の和を自乗するのを忘れていること判明w,ひどいな。すぐ直しsubmit、AC。さてLargeが通るかだけど、1000個円があるので最後の円とか難しそう、確率もよくわからないしーということでCへ(マットが5倍広いも読み抜けていた、いやわかっていてもsubmitはできなかったがw)

gets.to_i.times{
	n,w,l=gets.split.map(&:to_i)
	r=gets.split.map(&:to_i)
	$circles=[[0,0,r[0]]]
	#$circles<<[w,l,r[1]] if n>1
	
	def intersect?(x,y,rr)
		$circles.any?{|a,b,ss|(x-a)**2+(y-b)**2<(rr+ss)**2}
	end
	
	while $circles.size<n
		x,y,rr=rand*w,rand*l,r[$circles.size]
		$circles<<[x,y,rr] unless intersect?(x,y,rr)
	end
	write($circles.map{|x,y,rr|"%.9f %.9f"%[x,y]}*" ")
}
C. Mountain View

問題文を読んで、登山の時によくあるシチュエーションで思わずニヤリとした。
目の前にあるピークが目指す山頂だと思って頑張ってそこまで登るけど、やっとのことでピークに着いたらまだ先にピークがあった時の疲労度は異常、だから地形図は読めるようにしましょうということが次の本に書いてある。まじおすすめ。続編もあるね。
入門講座 2万5000分の1地図の読み方 (Be‐pal books)

さて、これは俺得な問題、山の神様が必ず解かねばと言っている・・・!ということで各山の高さと高さが決定できない場合の上限を管理することにする。最初の山は適当に2**10で高さ1024にし、最初の山から見えるピークは高さ1024*idxとする。
その間にある低い山の上限はピーク同士を結んだ線分未満という具合、高さは未確定。最初の山から順に見ていって、高さが決まってない山は、上限未満の高さを乱択して決定。新たに見えた山は今いる山との間にある山の上限の傾きより大きい高さにセット。
これでサンプルは通るかと思ったが、Impossibleのケースを考えていなかったwので、1から4が見える、2から7が見えるのようにintersectする組み合わせが無いか最初にチェックするロジックを入れてサンプルOK。
これでsmall通るかと思ったんだけど通らないね。なぜ通らないかがわからない。絶望感が漂ってくる。山の高さの列が与えられた時に各山頂からピークのindexを返す逆のプログラムを作ってチェックしてみたがよくわからない。どこかが間違っているのだが・・・太陽の絵がムカツクぜw。結局1時間格闘したけどダメでDへ。後から奥の方にある山のピークの上限を管理することを忘れていることに気づく・・・(それだけで通るのかは??)

D. Descending in the Dark

迷路じゃないじゃん。これも山かー。要は、各caveに右、左、下だけで辿り着けるスタート地点にすべて対して、うまくcaveにたどり着くplanがあるかという問題と把握。よくゲームで2画面別々の迷路上の主人公を一つのコントローラーで操作して両方の迷路ともにゴールできるか?みたいなのがあるけど、そんな感じと認識した。あるいは、迷路の板に幾つか玉が入っていて板を傾けることで玉を誘導するおもちゃ。さて、すべてのスタート地点は調べられるけど、planをどう作るのかがわからなかった。bruteforceでも3^20とかになるので、ダメっぽい。時間もないので、問題文読んだだけで、Aへ。

A. Swinging Wild

残り20分くらい。Tシャツはぎりぎりいけるかどうか、かな。というわけで全力で考える。ゴールから考えようということで神速でシコシコ書いてみるがサンプル通らない。くっそー。dp[L]を距離Lの位置に蔦を使っていけるかどうかにして、dp[L]はLより前の蔦を考えればdp[M](M