チョコの量を減らせ!
問題ページ
[チョコの量を減らせ!]
問題
- 1辺が1の立方体N個を並べて直方体を作る
- その際、表面積が最小になるパターンを見つける
N = 280671392065546467397265294532969672241810318954163887187279320454220348884327
例題は...
- N=30のとき
- 30を素因数分解すると、2*3*5なので、直方体のパターンとしては
- 1*1*30、1*2*15、1*3*10、1*5*6、2*3*5のいずれか
- 1*1*30 のとき、表面積は、1*1 * 2 + 1*30 * 2 + 1*30 * 2 = 122
- 1*2*15 のとき、表面積は、1*2 * 2 + 1*15 * 2 + 2*15 * 2 = 94
- 1*3*10 のとき、表面積は、1*3 * 2 + 1*10 * 2 + 3*10 * 2 = 86
- 1*5*6 のとき、表面積は、1*5 * 2 + 1*6 * 2 + 5*6 * 2 = 82
- 2*3*5 のとき、表面積は、2*3 * 2 + 2*5 * 2 + 3*5 * 2 = 62
- なので、2*3*5 のときが最小になる
どんなときに表面積が最小になるか
- N = m * n * o ( m <= n <= o ) とすると、表面積は ( m * n ) * 2 + ( n * o ) * 2 + ( o * m ) * 2 となるから、これが最小となる (m, n, o) を見つけてあげればよいということ。
- 整理すると、
- 2mn + 2no + 2om で、2倍するのはいつも一緒なので、要は mn + no + om が最小になるものを見つければよいということ。
- mn + no + om に n = N / o / m を代入すると、mn + no + om = N/o + N/m + om が得られる
- これを o について微分すると -N/o^2 + m で、通分すると ( -N + mo^2 ) / o^2
- N = m * n * o だから、
- ( -mno + mo^2 ) / o^2 = ( om( o - n ) ) / o^2
- ここで、 o >= n、om > 0、o^2 > 0 だから、 -N/o^2 + m >= 0
- したがって、mn + no + om は o が大きければ大きいほど大きくなる(単調増加)
- 同様に、m について微分すると、m が小さければ小さいほど大きくなる(単調減少)
- m、n、o が正の実数であれば、 m = n = o = N^(1/3) のとき、表面積が最小になる
- 今回は正の整数という条件がついているので単純にはいかないが、できるだけ o が小さく( = N の 三乗根に近く)、できるだけ m が大きい( = N の 三乗根に近い)組合せを見つけてやればよい
- 素因数の数によっては、しらみつぶしに調べても問題はないかな
- ということで、まずは問題の
280671392065546467397265294532969672241810318954163887187279320454220348884327
- を素因数分解する。
素因数分解
- ポラード・ローの素因数分解法を用いて素因数を探す
- 多倍長の計算が必要なので、Math::BigInt::GMP モジュールを利用
- また、得られた因数や因数で割った残りが素数かどうかの判定に、Math::Primality モジュールを利用
- [コード]
実行結果
n = 280671392065546467397265294532969672241810318954163887187279320454220348884327
factor (prime) 358456949
n = 782998886891564954421528858498903510563022503866046929912577369100523
factor (prime) 369941863
n = 2116545774360132241701796421182275093216531982124031553337821
factor (prime) 369941863
n = 5721292954509806968512229234198009899778582187991067
factor (prime) 162425297
n = 35224149564028853021042831980772120119802411
factor (prime) 215940091
n = 163120008891859052801097652500165521
factor (prime) 706170617
n = 230992347975105643344967513
factor (prime) 479871607
factor ((possibly) prime) 481362815814826159
280671392065546467397265294532969672241810318954163887187279320454220348884327 =
358456949x369941863x369941863x162425297x215940091x706170617x479871607x481362815814826159
- MacBook Air mid 2011 で、約34秒かかった。
- 問題の
280671392065546467397265294532969672241810318954163887187279320454220348884327
- は、
358456949x369941863x369941863x162425297x215940091x706170617x479871607x481362815814826159
- という形に因数分解できることがわかった。
- 最後に得られた「481362815814826159」については素数かどうか確定していないが、ミラー-ラビンの判定法を用いて20回の判定を行なっても合成数との結果は得られなかったため、素数と見てほぼ間違いないと思われる
表面積が最小になる直方体を探す
まずは予測してみる
- 得られた結果を見ると、9桁の数が7つ、18桁の数が1つで計8つで、先に考えたように縦、高さが N の 三乗根に近いときに表面積が小さくなることを考えると、3つの数が近くなるように選んでやればよさそう
- 上に書いたように9桁の数が7つと18桁の数が1つなので、9桁の数3つ、9桁の数3つ、9桁の数1つと18桁の数というふうに分けてあげるとよさそう
- 18 桁の数はひとつしかないから、これと 9桁の数をかけて N の三乗根に近いものを探すと、
78185498323479435878944223 ( 481362815814826159 x 162425297 ) … A
- が得られる。これは N 三乗根より大きいので、高さの候補になる
- 次に、残りの9桁の数を3つずつかけて N の三乗根に近いものを探すと、
65673779881467254576635783 ( 369941863 x 369941863 x 479871607 ) … B と
63634925160141537479761109 ( 358456949 x 369941863 x 479871607 ) … C が
- 得られる。B は N の三乗根より大きいので横の候補、C は小さいので縦の候補
- A x B x 残り と A x C x 残りのそれぞれの組合せで表面積を計算すると、
- A x B x 残りでは
25996543686708345761182905723919513810539627959729254
- A x C x 残りでは
25951584851644825093824507917780974813654548406812318
- が得られる
- たぶんこのあたりが最小になるのだろう
- 縦x横x高さの形にすると、
56412637156759097412131861x63634925160141537479761109x78185498323479435878944223
- である
しらみつぶしに探す
- 素因数の数は8つだけなので、縦、横、高さのどこかにいずれかの素因数を使うと考えれば、重複を含めても高々 3^8 = 6561 パターンしかないのですべてのパターンをしらみつぶしに探しても問題ないだろう
- ということで、探すプログラムを作成
- [コード]
実行結果
EXPECTED : 280671392065546467397265294532969672241810318954163887187279320454220348884327
CALCULATED: 280671392065546467397265294532969672241810318954163887187279320454220348884327
OK!
6561 patterns.
56412637156759097412131861x63634925160141537479761109x78185498323479435878944223
(25951584851644825093824507917780974813654548406812318)
- MacBook Air late 2011 で、約1.7秒かかった
- 予想通りの結果が得られた
答え
- ということで、答えは、
56412637156759097412131861x63634925160141537479761109x78185498323479435878944223
- かな
- 以上