こん○○は!久々に今日は寒かったですね~。
さて、これまた久々にブログCheckIOに挑戦を更新させていだきます。
よろしくお願いします。
Home 第五問 ハトに餌をあげろ! Feed Pigeons
最初にハト1匹に餌をあたえます。1分後2匹のハトがやってきます。次の1分後に別の3匹、そしてさらに4匹のようにやってきます。(例:1+2+3+4+...).
餌1つでハトを1分飼うことができます。もし全てのハトにいきわたるほど十分な餌がなかった場合、最初にいたハトから順に食べます。ハトは飢えていて、いつまでも食べ続けます。もし、餌がw個あった場合、何匹のハトを飼うことができますでしょうか?
それでは、まず方針を決めます。なんとなく、数学的にまるっと解くこともできそうですね。再帰使ってゴリゴリ行く前に整理してみます。
ちなみに忘れていたので累乗の和の公式はチートしました。
チートシート: http://www.osaka-c.ed.jp/shijonawate/pdf/yuumeimondai/suuretu_17.pdf
① n分後にいるハトの数
pigeons(n) = Σk = n(n+1)/2
② n分後に必要な餌の数
requiredWheat(n) = pigeons(n)
③ 1~n分後までに必要な餌の総量
requiredTotalWheat(n)
=Σpigeons(k)
=Σn(n+1)/2
=(1/6n(n+1)(2n+1)+1/2n(n+1))/2
=n(n+1)(n+2)/6
さて注意点としては、n分経過後に、餌はすべて消費されるわけではありません。残った量が一定量を超えた場合、新しくやってきたハトの一部に餌を与えることができます。
④ n分の時点で新しいハトにまわせる餌の量を求めます
そのまえに、n分の時点でそれまでにすでにいたハトによって消費された餌の量を求めます。
eatenWheatBySenior(n)
= requiredTotalWheat(n) - n
= n(n+1)(n+2)/6 - n
⑤ もし新しいハトに餌を回せた場合にn分の時点で餌を与えられる最大のハトの数
maxFeededPigeons(n)
= pigeons(n-1) + w - eatenWheatBySenior(n)
= w + (n-1)n/2 + n - n(n+1)(n+2)/6
= w - n(n-1)(n+1)/6
さて、n(n+1)(n+2)/6 <= w となる、最大のnをN(分)とします。このN分はすべてのハトに餌を与えられる最後の時刻です。
あきらかに、n^3 < n(n+1)(n+2) < (n+2)^2 ですから、W=(f×6)^(1/3)とすると、Nは、min(W[繰り上げ]-2,1) <= N <= W[繰り下げ]となります。ここまで絞れれば、数回の繰り返しで、Nを探索することができます!
ここで工夫して、maxFeededPigeons(n)が0以上になるNを、先ほどの範囲の上限に+1した数から下方向に検索してみます。
それが見つかったら、pigeons(n-1)かmaxFeededPigeons(n)のどちらか大きいほうが答えです。
最後に、必要なpythonの言語やライブラリの情報を整理しました。
(1) 根の演算子もしくは関数
べき乗演算 power ::= primary ["**" u_expr]
これを使って「x**(1.0/3)」で3乗根を求めます。
(2) 最小値をもとめる関数
組み込み関数: min(iterable, *[, key]) iterable の中で最小の要素、または2つ以上の引数の中で最小のものを返します。
(3) 実数を整数にする
math.floor(x) x の「床」 (x 以下の最大の整数) を返します
math.ceil(x) x の「天井」 (x 以上の最小の整数) を返します。
それでは、レッツコーディング!
def checkio(wheat): W = (wheat * 6) ** (1.0/3) s = math.floor(W) + 1 e = min(math.ceil(W) - 3 + 1,1) n = s maxFeededPigeons = 0 while e <= n: maxFeededPigeons = math.floor(wheat - n*(n-1)*(n+1)/6) if 0 < maxFeededPigeons: maxFeededPigeons= max(maxFeededPigeons,math.floor(n*(n-1)/2)) break n = n -1 return maxFeededPigeons
ゴール!!
やっぱり再帰していないと早い!餌の数を増やしても即答です。