Problem 275
問題の概要.
ある条件を満たす,polyominoを探す.
その条件の1つは,横方向にバランスがとれていること(重心のx座標が0).
詳細な条件は上のリンクで.
絵でみると分かりやすい.
下図はproject eulerからの引用.
求めるのはサイズ18.しかし,形が想像できないので,ナイーブな検証用のコードをC++で書いた.
実行したら,サイズ15で4 秒ぐらいだった.これなら,サイズ18でも大丈夫か,と思い,サイズ18で実行したら,
見事に1分以上かかった(3分ぐらい).
ナイーブな方法でもうまく,枝刈りをすれば,1分切れるかもしれないが,もっと賢い方法がありそう.
ひさびさに,難問か?