結城浩さん (id:hyuki) 出題のチョコ問題に挑戦した.

codeiq
  • hyuki.com/codeiq/

正解してで, 5 点 & バッチをいただいた.
以下の方法で解いた.

  • 数式処理ソフトを使って N を素因数分解をする.
  • 8 つの素因子を縦・横・高さのどれに配置するかを総当たりして最小値を探索した.
    • 3^8=6561 なので総当たりでもたいしたことはない.　
  • C 言語 + GMP を利用した.

で, 工夫しないと終わらないというふうに書いてあったのでどこが難しいのかわからなかった.
twitter を眺めてみて分かったのは素因数分解が悩みどころだったらしい.
うーむ. いつもの癖で何も考えずにソフトを使ってしまった.

んで, フィードバックをみて思ったのが上記の「総当たり数」が思っているのと違った.
他にも twitter で comb_next を調べたというコメントがリツイートされていたのはこれだったのね, と.

●最小表面積探索

さて残りのポイントは「最小表面積探索」です。

(略)

素因数はすべてわかっていますから、あとはその素因数を3グループに分けるすべてのパターンを作るという問題に帰着されます。まずはざっと何パターンあるか調べるのは大事です。8個の素因数と、その素因数を3グループに分ける区切りマーク2個。合計10個のものの順列を考え、区切りマーク2個は区別しないので2で割ります。

10! ÷ 2 ÷ 2 = 907200

これは多めの見積もりです。

2013/2/20 追記

3^8 でよさげだ.