本履歴

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

GCJ2012(Google Code Jam 2012 Round 1)

Round 1A

GWを満喫するためにどうしてもこのラウンドで通過を決めたいところ。
A,Bの問題文を一瞥し、Aのsmall,largeが同じスコアなのでA,B,Cの順に決定

Problem A. Password Problem

問題の意味がわからず手こずった。幸先悪いなー。
各ストラテジーごとに確率を計算して、その中で最も良い確率が求めるもの、ということを理解するのに40分位かかったw
サンプルも手計算で通るので、コーディング開始。ただ、その時点で1000人以上通しているので、焦りまくり。指が震えたw
smallが通ってlargeも計算量的に問題なさげだったのでそのままsubmit。

gets.to_i.times{
	a,b=gets.split.map(&:to_i)
	prob=gets.split.map(&:to_f)
	dp=Array.new(a+1,0)
	ok=prob.inject(:*)
	ans=[1+ok*(b-a)+(1-ok)*(2*(b+1)-a),2+b].min
	pr=1
	prob.each_with_index{|_p,i|
		pr*=_p
		temp=pr*(b-i)+(1-pr)*(2*(b+1)-i-1)+(a-i-1)
		ans=temp if temp<ans
	}
	write("%.7f"%ans)
}
Problem B. Kingdom Rush

問題文がわからず5回くらい読み返す。半分くらいの人がWA食らっているなあ。
1-star ratingというのとearns 2 starsのところのstarが全く意味わからず、ちょっと絶望。図を書いてほしいな。
落ち着いて状況を整理してみた。
まず、A,Bを完答すれば1000位には入れそう。Cはsubmitしている人が少なくC Largeは解けそうにない。
ということはBに全力投球しかない←結論。
残り時間格闘したけど問題文とサンプルからなんとなくゲームについて理解できたところでタイムアップ。
Rank: 2193 Score: 20で通過ならず。今年もそんな甘くない。

Round 1B

日本時間の1時から開始。4時間くらい仮眠を取って準備万端。
A,B,C と問題文をざっと読む。Bは変なしょぼい図があったので後回しw。過去問のロードランナーを思い出した。
Cはdistinct(区別できる)をdisjoint(互いに素、共有部分がない)と読み間違え、bruteforceでも3^20かかるから無理ゲーっぽい。何かアイデアが必要と考えAから決定。

Problem A. Safety in Numbers

問題文を読んでXがinputに与えられていないことに気づく。Xが任意の場合に解くもんだと思ったまま紙上で計算してみる。
i番目がS_i+X*Yゲットした時、他の競技者のスコア平均は(ΣS_j+X*(1-Y))/(n-1)だからこれより大きくなるようにYを指定すれば良い。
しかし色々試してみるとXが任意だと解答も任意になることが判明。問題文をもう一度注意深く読んでみるとLet X be the sum of the judge-assigned point values of all contestants.なる文発見w ここまでで1時間費やす。
XをΣS_jとして計算し、サンプルが通るもの完成。いざsubmitするとWA。自分の出力を見ると、負数が混ざっているようだ。なるほど、ということで負数は0に修正するロジックを入れてsubmit。何とか通る(後からだと、なぜ通ったw)。
ついでにlargeもsubmit. この時100以上が出た場合など確率は全く考慮していなかった・・・

gets.to_i.times{
	n,*s=gets.split.map(&:to_f)
	x=s.inject(:+)
	ans=s.map{|s|((2*x-s-(n-1)*s)/(x*n*0.01))}
	if ans.any?{|a|a<0}
		dist=0.0
		c=n
		ans.each{|a|if a<0
			dist-=a
			c-=1
			end
		}
		ans=ans.map{|a|a<0 ? 0.0 : a-dist/c}
	end
	ans=ans.map{|a|"%.6f"%a}*" "
	write(ans)
}
Problem C. Equal Sums

次にみんなが通してるCへ。この時点でC small、B small取らないと通過できなさそう・・・
でも一度disjointと空目してしまったものをコンテスト中に覆すのは厳しく、終了後サンプルにそのケースがあったなら、と思うのであった。

Problem B. Tide Goes In, Tide Goes Out

残り時間40分くらいでBを通すことに全力。幅優先探索でしこしこ書いていたらタイムアップ。
問題文の洪水が起こる前だったら行けるところまで事前に行ける、というのも見逃していたのでどうしようもない。
A largeも落として、Rank: 2532 Score: 10でRound C最終戦へ。

Round 1C

明日から会社かーという大型連休最終日の日曜、憂鬱な18時サザエさんな時間帯に開始。
問題文を一通り読んでAから行こうと思ったが、サンプル最後の三角形のパターンがダイアモンド継承とされていたのがわからず、Bに変更(四角形じゃないとダイヤモンド継承と言わないと勘違いしていた・・・)

Problem B. Out of Gas

出力時に最初に改行が入るパターン。これやめて欲しいと個人的に思う。入れるなら全部の問題で改行を標準にしてほしい。
さて、ブレーキを任意にかけられるので、前の車の位置情報の折れ線と自分の車の2次関数が交差するかどうかで判定できそうと考えた。つまり、交差しない=前の車と接触しないのでノーブレーキで加速してOK、交差する=前の車と接触してしまうのでブレーキを調整して前の車が自宅を通るときに同じく自宅を通れば良いはず。
ということで、グラフの交点の問題にして紙上で計算。二次方程式の解の公式とか懐かしいなあと思いながらしこしこ書いてみたがサンプル通すものが作れず。
よく考えてみると、時間・距離のグラフを距離・時間にしていたことが判明。無意識に変数xは横軸に取ってしまうケアレスミス、慌てて修正してみて、sample通すものができた。
また、前の車の位置情報が1つの場合(N=1)どうしたらいいのか言及されていないことも気になった。だれか質問してくれないかなーと思いながら問題文を何度も読んでみたけどどこにも書いていない。N=1だと、前の車は動いていないことになり衝突が避けられないのでは?ということで、N=1の入力は無い、という判断でsubmit、WA。N=1のケースあるじゃんw ということで問題文を目をサラにして読むもそこが不明。Aを2000人くらい通していて、この時点で詰んだっぽい。しかし、落とした入力のN=1を見るとすべて自宅より先に前の車があるパターンじゃんwなんだこれ。というわけでN=1の場合はフルスロットルで加速するコードを追加し
Accepted。とりあえずAへ。

gets.to_i.times{
	d,n,a=gets.split.map(&:to_f)
	n=n.to_i
	seg=n.times.map{gets.split.map(&:to_f)}#t,x
	a=gets.split.map(&:to_f)
	write("")
	if n==1
		a.each{|_a|
			puts"%.7f"%((2*d/_a)**0.5)
		}
		next
	end
	
	#max_time=seg.last.first
	#liner_coe=[]
	#seg.each_cons(2){|(t1,x1),(t2,x2)|
	#	m=(x2-x1)/(t2-t1)
	#	n=x1-m*t1
	#	liner_coe<<[m,n]
	#}
	#wi=when_intersect(a,liner_coe)
	t1,x1=seg.first
	t2,x2=seg.last
	m=(x2-x1)/(t2-t1)
	n=x1-m*t1
	a.each{|_a|
		t=(2*m+(4*m*m+8*_a*n)**0.5)/(2*_a)
		ans=0.0
		#p t,m,n
		#p seg
		if (t<=(d-n)/m)
			ans=(d-n)/m
		else
			ans=((2*d/_a)**0.5)
		end
		puts"%.7f"%ans
	}
	
	
	#seg.each_cons(2).map{|(t1,x1),(t2,x2)|[t1,t2]}.with_index{|(t1,t2),idx|
	#	t=wi[idx]
	#	if (t1<=t)&&(t<=t2)
	#		int=true
	#		break
	#	end
	#}
	#write(ans)
}
Problem A. Diamond Inheritance

問題文をよく読んでみると四角形でなくてもOKというものだったので、BFSで各頂点から訪れたかどうか判定するコードを書く。
配列のdupをするのを忘れて1WA。small,largeと連続高速submit。その間、52秒。

gets.to_i.times{
	n=gets.to_i
	@edge=[]
	n.times{
		m,*e=gets.split.map{|s|s.to_i-1}
		@edge<<e
	}
	def inh?(n,k)
		v=Array.new(n,nil)
		v[k]=0
		cand=@edge[k].dup
		ret=false
		until cand.empty?
			s=cand.shift
			next if s==k
			if v[s]
				ret=true
				break
			else
				v[s]=1
			end
			@edge[s].each{|v|cand<<v}
		end
		ret
	end
	ans=[*0...n].any?{|k|inh?(n,k)}
	write(ans ? "Yes" : "No")
}

このとき残り40分で、順位600位。グラフの交点判定で行けるならBのLargeが簡単そうだったが通してる人が少なすぎるので何かあると考えてCへ。多分前の車が急速に
速度を上げた時に、自分の最大加速と比較して同時にゴールできないパターンがあるのだろう。それを俺に40分でコードするのは無理なこと。

Problem C. Box Factory

問題文を読んでsmallはbruteforceで解けそうということでしこしこ書いている最中にどんどん自分のランクが下がっていく恐怖。心臓に悪すぎw。
結局、時間内に解けず終了直前で1080位。最終結果は、Rank: 1006 Score: 38。おわた、おわたよー。

結局今年もRound 1でダメでした。2年連続だなあ。参加者が増えてることもあるし、実力のブレイクスルーがないと厳しい。


後日スコアを見てみると、Rank: 999 Score: 38。あれ?チートした人がいてランクがちょっと上がったのかな?メール来るまでぬか喜びはしないけど、ちょっとワクワクドキドキ。