690th, 0pts, +0/0 challenge
Volatility 333->345
250: MyLongCake
ある長さ\(n\)のケーキが与えられる。
\(n\)よりも小さな\(n\)の約数の人数の友達が来ることがわかっている。
何人友だちが来ても大丈夫なようにケーキを切るには、ケーキを最小で何ピースに分ければよいか。
ただしそれぞれの友達にはいくつかの連続したピースを与える。
長さ\(6\)の時\(1, 2, 3\)人が来る場合が考えられる
この場合\(2,1,1,2\)と4つに分けるのが最小
\(3\)人の時は\((2), (1, 1), (2)\)、\(2\)人の時は\((2, 1), (1, 2)\)、\(1\)人の時は全部与えればよい
連続したという部分を深く考えずに読み飛ばして時間内には解けず。
Challenge中に見たコードの解法をメモしておく。
\(n\)を割り切る素数で分割して論理和を取る方法
長さ\(n\)を\(i\)分割(\(i\)は\(n\)を割り切るそれぞれの素数)したときの、分割する場所の集合の論理和の大きさに等しい。
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class MyLongCake: def cut(self, n): result = set() num = n for i in itertools.chain([2], xrange(3, n + 1, 2)): if num % i == 0: while num % i == 0: num /= i for i in xrange(1, n, i): result.add(i) return len(result)
分割しない場所の数を求める方法(GCD)
数直線を分割する場所の数を求めるのではなく、分割しない場所の数を求めるという方法も考えられる。
これには\(n\)と互いに素な数の個数を求めればよく、pythonには最大公約数を求めるfractions.gcd関数があるので簡単に書ける。
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class MyLongCake: def cut(self, n): result = n for i in xrange(1, n): if fractions.gcd(n, i) == 1: result -= 1 return result
分割しない場所の数を求める方法(オイラーのトーシェント関数)
オイラーのトーシェント関数はある正の整数\(n\)に対して\(1\)から\(n\)までのうち\(n\)と互いに素な数の個数を返す。
\(p\)を素数とした時\(p\)と互いに素な数は\(p\)ごとに\(p - 1\)個あるのでオイラーのトーシェント関数は
$$ \varphi(p^k) = p^{k - 1}(p - 1)=p^k(1 - \frac{1}{p})$$
オイラーのトーシェント関数は互いに素な数の積に対して乗法的なので、
$$n = \prod_{k=1}^d {p_k}^{e_k}$$
のとき次のようになる
$$\varphi(n) = n \prod_{k=1}^d \left(1-\frac{1}{p_k}\right)$$
以上のことを使って問題を解いた。
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class MyLongCake: def cut(self, n): totient = 1 num = n for i in itertools.chain([2], xrange(3, n + 1, 2)): if num % i == 0: num /= i totient *= (i - 1) while num % i == 0: num /= i totient *= i return n - totient
