2010年12月19日日曜日

Project Euler

■054
実装ゲー.条件に忠実に組む.
5枚のカードのマークが全て同じかどうかと,どの数字が何枚あるかを先に計算しておくと(少し)楽.

■172 4進数でビットDP
[桁数][どの数字が何回出たか]
でDP.各数字は0~3回までしか出ないので,dp[18][410]とすれば良い.
更新式は頑張る.

■173
全体の大きさをnとすると,最大の穴の大きさはn-2.
よって,使えるタイル数をmaxとすると,nが満たす条件は,
n2-(n-2)2≦max
となる.
最小の穴の大きさをkとすると,
n2-k2≦max
を満たすので,その最小値
k=ceil(√n2-max)
となる.但し,laminaeは上下左右に対称なので,n≡k mod 2を満たすようにkを補正.
n2-max<0
の場合は,k=0とすれば良い.
最後に,k,k+2,k+4,…,n-4,n-2の個数cは,
c=(n-2-k)/2+1
となる.
結構値が大きいため,intで計算したらオーバーフローした.注意注意….

■183
P=(N/k)kが最大となるkを見つける.おそらく上に凸な関数なので,三分探索でも良いが,kの値の範囲は高々Nなので,単純なループでも十分可能.また,(N/k)kを正直に計算すると,doubleでもオーバーフローするので,対数をとった値k*log(N/k)を計算.
(N/k)kが無限小数になるかどうかは,N/kが無限小数になるかどうかを確かめれば良い.そのためには,まずN/kを約分しN/k=n/dとする(各々をgcd(N,k)で割る).
d=2a5bと表す事が出来れば,有限小数,そうでなければ,無限小数.

0 件のコメント: