以下のように3x3の正方形がある。この中には1x1の大きさの正方形が9個，2x2の大きさの正方形が4個，3x3の大きさの正方形が1個あると見なすことが出来る。
このとき正方形を構成する24本の辺の何本かを取り除き異なる大きさの正方形が2個になるようにしたい。最小何本取り除けば良いか?
その時，正方形以外の図形はいくつあっても構わない。
2x2の4個の正方形と3x3の1個の正方形は以下のようになる。
最初14個の正方形から2個を選択して組み合わせれば良いと思ったけど，それではダメ。
プログラムを作ってから間違いに気づいた。
結局，24枚の辺のあるなしを全て虱潰すことにする。24ビットのループを考え，ビットがONの所が辺があり，ビットがOFFの所が辺が無いものとする。
虱潰す方法は大体以下の通り。
for( int i=0; i<= 0xFFFFFF; i++) { // 全ての辺の組み合わせを調べる
if( 異なる大きさの正方形が2個) {
if( 今までより辺の数(ビット数)が多い) {
iを記録
}
}
}
24ビットの数字から正方形を取り出すために，以下のように24本の辺に番号を振る。
そして14個の正方形を以下のように定義する。
// ＋−０−＋−１−＋−２−＋
// ｜ ｜ ｜ ｜
// 12 Ａ 13 Ｂ 14 Ｃ 15
// ｜ ｜ ｜ ｜
// ＋−３−＋−４−＋−５−＋
// ｜ ｜ ｜ ｜
// 16 Ｄ 17 Ｅ 18 Ｆ 19
// ｜ ｜ ｜ ｜
// ＋−６−＋−７−＋−８−＋
// ｜ ｜ ｜ ｜
// 20 Ｇ 21 Ｈ 22 Ｉ 23
// ｜ ｜ ｜ ｜
// ＋−９−＋−10−＋−11−＋
ulong rect[14] = { // 正方形の定義
/*A*/ bit0|bit3|bit12|bit13,
/*B*/ bit1|bit4|bit13|bit14,
/*C*/ bit2|bit5|bit14|bit15,
/*D*/ bit3|bit6|bit16|bit17,
/*E*/ bit4|bit7|bit17|bit18,
/*F*/ bit5|bit8|bit18|bit19,
/*G*/ bit6|bit9|bit20|bit21,
/*H*/ bit7|bit10|bit21|bit22,
/*I*/ bit8|bit11|bit22|bit23,
/*ABDE*/ bit0|bit1|bit6|bit7|bit12|bit16|bit14|bit18,
/*BCEF*/ bit1|bit2|bit7|bit8|bit13|bit17|bit15|bit19,
/*DEGH*/ bit3|bit4|bit9|bit10|bit16|bit20|bit18|bit22,
/*EFHI*/ bit4|bit5|bit10|bit11|bit17|bit21|bit19|bit23,
/*ABCDEFGHI*/ bit0|bit1|bit2|bit9|bit10|bit11|bit12|bit16|bit20|bit15|bit19|bit23,
};
int rect_size[14] = { // 1辺を1としたときの正方形の大きさ
1,1,1,1,1,1,1,1,1,4,4,4,4,9
};
こうすると，以下のように正方形を検出できるので，残った正方形の数が判る。
for( int i=0; i<= 0xFFFFFF; i++) { // 全ての辺の組み合わせを調べる
for( int j=0; j< 14; j++) { // 14個の正方形を全て調べる
if( (rect[j]&i) == rect[j]) { // 正方形が見つかった
………
}
}
if( 見つかった正方形が2個で大きさが異なれば) {
if( bitcount(i) が今までより多い) {
iを記録。
}
}
}
異なる大きさの正方形が2個残る場合を全て記録して最後に出力する。
答えは2件出力されました。但し，切り方の問題だけなので実質1件。
椅子がボロボロ。安い椅子はダメだなーと思うけど，座り心地が良いからなかなかリプレースできない。
解速度
Pentium Xeon2.4GHz で約1.2秒