[Home]Memo/Q197

Amatubu_Wiki | Memo | RecentChanges | Preferences

チョコの量を減らせ!

問題ページ

  [チョコの量を減らせ!]

問題

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
かな

以上

Amatubu_Wiki | Memo | RecentChanges | Preferences
This page is read-only | View other revisions
Last edited March 12, 2013 22:39 by Amatubu (diff)
Search:

Copyright (c) 1996-2006 naoki iimura e-mail