AtCoderで公開されている、E869120さんの『競プロ典型90問』を解いていきます。
前回に引き続き、難易度★2を解いていきます。
問題
直方体のケーキを、最小で何回切れば同じ大きさの立方体に分割できるかを求める。
考えたこと
2次元版「長方形を同じ大きさの正方形に分割する」の派生。
⇒ユークリッドの互除法で最大公約数を求めればよさそう：
$A \times B \times C$の直方体に対して、$N$が$A,\ B,\ C$の最大公約数であるとき、辺$A,\ B,\ C$を切るべき回数はそれぞれ$(A / N - 1),\ (B / N - 1),\ (C / N - 1)$回。
互除法の計算量はどう見積もれる？
⇒ラメの定理により、2数$a, b$に対する互除法の計算量は高々
$$ 5 \times [\text{min}(\log_{10}a,\ \log_{10}b) + 1] $$
となるようで、$A,\ B \leq 10^{18}$なる制約の元でも十分に少ない計算量で済む。
今後ユークリッドの互除法については、計算量を気にする必要はなさそう。
アイデア
$A,\ B$の最大公約数$AB$をまず求め、次いで$AB$と$C$の最大公約数を求めていく。
⇒第一案
def euclid2(a, b):
u = max(a, b) # 大きい方を割られる数
v = min(a, b) # 小さいほうを割る数とする
r = u % v # [u = ? * v + r]
if r == 0:
return v
else:
return euclid2(v, r)
def euclid3(a, b, c):
ab = euclid2(a, b)
return euclid2(ab, c)
もっとうまく書けそう。
- 再帰ループの中で$v > r$は当たり前 ⇒ いちいちmaxとminしなくていい
- returnは1行で書ける
⇒改良版
def euclid2(a, b): # 常にa > bであるとする
r = a % b
return b if r == 0 else euclid2(b, r)
def euclid3(a, b, c):
a, b = max(a, b), min(a, b) # 初めに一度だけ大小関係と整える
ab = euclid2(a, b)
ab, c = max(ab, c), min(ab, c) # 初めに一度だけ大小関係と整える
ab = euclid2(a, b)
return euclid2(ab, c)
最終的な実装例
A, B, C = map(int, input().split())
def euclid2(a, b):
r = a % b
return b if r == 0 else euclid2(b, r)
def euclid3(a, b, c):
a, b = max(a, b), min(a, b)
ab = euclid2(a, b)
ab, c = max(ab, c), min(ab, c)
return euclid2(ab, c)
n = euclid3(A, B, C)
print(A // n + B // n + C // n - 3)
アルゴリズムについては苦労する点はありませんでした。コードの簡略化は常に意識していきます！
お読みいただきありがとうございました。
参考記事