Google Code Jam 2013 Round 1A : A. Bullseye

さてGCJのRound1。
AのLargeをミスして落としたが、幸いBのLargeを取れたのですんなりRound2進出。
Aを取れてればかなりいい順位になったのだが…まぁ1Aを抜けられたのでよしとしよう。
https://code.google.com/codejam/contest/2418487/dashboard#s=p0

問題

２つの数値R,Tが与えられる。
半径Rcmの位置から、幅1cmの黒い円を描き、その外側を1cm空け、また黒い円を描く…ということを繰り返す。
ペンキ1当たりπcm^2を塗れる場合、Tのペンキで黒い円を何個書けるか答える。

解法(small)

半径Rの円の外に幅1cmの黒い円を描くと、その面積は((R+1)^2-R^2)×πなので、必要なペンキは((R+1)^2-R^2)である。
黒い円の半径を2ずつ増やしながらペンキがなくなるまで繰り返せばよい。

void solve(int _loop) {
	ll R,T;
	
	cin >> R >> T;
	ll pr=0;
	while((R+1)*(R+1)-R*R<=T) {
		T-=(R+1)*(R+1)-R*R;
		pr++;
		R+=2;
	}
	
	_PE("Case #%d: %lld\n",_loop,pr);
}

解法(Large)

上記のとおり、半径Rのの外側に黒い円を描くのに必要なペンキは((R+1)^2-R^2)=(2R+1)。
ここで、黒い円をD個描く場合、(2R+1)+(2R+5)+...(2R+1+4(D-1) ) = (2D+2R-1)Dとなる。
この値がTを超えないDの最大値を求めればよい。

二分探索で求める方法と、二次方程式で近似解を求めてその周辺を詳細に検索する方法がある。
今回は後者を用いた。
なお、途中でRの2乗を取る都合で64bit整数には収まらないため、Pythonで対処。

下記のコードは２次方程式の解から100程度引いた値から、1つずつTを超えないことを検証している。
本来は小数分の切り捨てにせいぜい1引いておけば十分なはずだが、100位引かないとCorrectにならなかった。
多倍長整数と小数での変換に精度問題があったりする？

import sys
import math

def test(i):
	R,T=map(int,raw_input().split(" "))
	D=int(max(0, ((-(2*R-1)+math.sqrt((2*R-1)*(2*R-1)+8*T))/4)-100))
	while(1):
		L=(2*D+2*R-1)*D
		if L>T:
			print("Case #%d: %d"%(i,D-1))
			return
		D+=1

N=input()
for i in range(N):
	test(i+1);

まとめ

本番中ではミスしたとはいえ、Pythonを練習した経験が活きた。
コードもだいぶシンプルになって良いね。