INSIGHT

インサイト

2014年327

CheckIOに挑戦⑤ Pythonを学んでいるんだか、数学やっているんだか(汗)

こん○○は!久々に今日は寒かったですね~。

さて、これまた久々にブログCheckIOに挑戦を更新させていだきます。

よろしくお願いします。

それでは、まず方針を決めます。なんとなく、数学的にまるっと解くこともできそうですね。再帰使ってゴリゴリ行く前に整理してみます。

ちなみに忘れていたので累乗の和の公式はチートしました。 チートシート: 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) 根の演算子もしくは関数

これを使って「x**(1.0/3)」で3乗根を求めます。べき乗演算 power ::= primary ["**" u_expr]

(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

ゴール!!

やっぱり再帰していないと早い!餌の数を増やしても即答です。