こん○○は！久々に今日は寒かったですね～。
さて、これまた久々にブログCheckIOに挑戦を更新させていだきます。
よろしくお願いします。
それでは、まず方針を決めます。なんとなく、数学的にまるっと解くこともできそうですね。再帰使ってゴリゴリ行く前に整理してみます。
ちなみに忘れていたので累乗の和の公式はチートしました。 チートシート： http://www.osaka-c.ed.jp/shijonawate/pdf/yuumeimondai/suuretu_17.pdf
pigeons(n) = Σk = n(n+1)/2
requiredWheat(n) = pigeons(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分の時点でそれまでにすでにいたハトによって消費された餌の量を求めます。 eatenWheatBySenior(n) = requiredTotalWheat(n) - n = n(n+1)(n+2)/6 - 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の言語やライブラリの情報を整理しました。
これを使って「x**(1.0/3)」で3乗根を求めます。べき乗演算 power ::= primary ["**" u_expr]
組み込み関数:min(iterable, *[, key]) iterable の中で最小の要素、または2つ以上の引数の中で最小のものを返します。
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ゴール！！
やっぱり再帰していないと早い！餌の数を増やしても即答です。