2x2, 3x3, 6x6 の3つの大きさのチョコがある。これを切り込みに沿って四角形に5分割し7x7のチョコを作成する。
(2007.2.18)また問題の読み間違いをやってしまいました。「5分割」だけでなく，「四角形」がポイント。
1月5日に次ぎプログラマとして恥ずかしいミスを連発してしまいました。
最初に書いた回答は全てが四角形では無いので回答自体が間違いでした(メールで間違いを指摘してくれた人がいました，この場を借りて感謝します)。
回答の中に正解があればもう少し救いもあったのだが，正解が無かったため作成したプログラムは全て間違いでした。
結局最初に考えた分割が正しかったことになるが，アプローチを間違えていたため答えに辿り着くことが出来なかったのだ。
頭で答えを考えたらアプローチのミスに気づいた。
と言うことで改めてプログラムを作成した。最初に作成したプログラムはファイル自体を削除していたので，もう一度最初から作り直し。
結局この問題のために3回プログラムを作ったことになる。
まず図形に以下のように記号を振る。2x2がBで，3x3がAなのはご愛敬。
3つの矩形を5片にするには，以下のような分割数の組み合わせになる。
| B | A | C | |
| 1 | 1 | 3 | この分割で探す |
| 1 | 2 | 2 | これは結局四角形でない組み合わせしか見つからない |
| 2 | 1 | 2 | 見た目直ぐにダメなのが判る |
| 2 | 2 | 1 | あり得ない |
| 3 | 1 | 1 | あり得ない |
| 1 | 3 | 1 | あり得ない |
最初にプログラムして見つからなかった原因はアプローチを完全にミスしていたため。
以下のような考え方で探していた。
foreach A { // Aを7x7の矩形に配置
foreach B { // Bを7x7の矩形に配置
AとBが隣り合う場合だけを対象とする。
D = (A | B) & C ( DはAとBを会わせた部分とCの重なり)
foreach D,D'',D''',D'''' { // 'は回転を示す
E = D & C (DとCの重なる部分)
foreach E,E',E'',E''' {
A, B, C, D, Eで7x7の矩形を埋めることが出来れば解
}
}
}
}
Dの求め方に間違いがあった。必ずしもDは上記のようになるわけではないので，その場合の探索がされていないために解が見つからなかった。
今回は全くアプローチを変えて全探索を行う。最初からこの方法を取っていれば問題なかった。結局プログラムはこちらの法が楽になる。
基本的な考え方は以下の通り。
CをC1,C2,C3の3つに分割する。 A,B,C1,C2,C3の5つを7x7の矩形にレイアウトして全て埋めることが出来れば解
この考え方でプログラムすると以下のようになる。実際はorgC1,orgC2,orgC3が上記分割になり，C1,C2,C3は大きい順に並べ替えている。
void cut66( int row, int col, int64& c1, int64& c2, int64& c3, int64& orgC1, int64& orgC2, int64& orgC3) // 6x6の図形Cを3分割する
{
c1 = c2 = c3 = 0;
for( int i=0; i< row; i++) { // 横に入れる切り込み線の上がc1
for( int j=0; j< 6; j++) {
c1 |= getbit(i*7+j);
}
}
for( ; i< 6; i++) { // 横の切り込み線の下にc2,c3がある。
for( int j=0; j< col; j++) { // 縦の切り込み線の左がc2
c2 |= getbit(i*7+j);
}
for( ; j< 6; j++) { // 縦の切り込み線の右がc3
c3 |= getbit(i*7+j);
}
}
int64 c[3] = {c1,c2,c3};
qsort( c, 3, sizeof(int64), bitcountcmp); // ビット数順にソートして返す,一番大きな図形を7x7の左上に配置するため
c1 = normalize(c[0]);
c2 = normalize(c[1]);
c3 = normalize(c[2]);
orgC1 = c[0]; // 元の図形のレイアウトを表示するために使用する
orgC2 = c[1];
orgC3 = c[2];
}
void check( int64 orgC1, int64 orgC2, int64 orgC3, int64 C1, int64 C2, int64 C3, int64 A, int64 B) // 組み合わせて7x7の矩形になるか調べる
{
// C1,C2,C3はC1が最大。C1を左上に置くことを前提にする。
char s[] = {'.','C','x','A','B'}; // 出力用
char S[] = {'C','C','C','A','B'}; // 重複チェック用
int64 z[] = {C1,C2,C3,A,B};
for( int a=0; a< 1; a++) { // C1
used[a] = YES;
for( int b=1; b< 5; b++) { // C2
if( used[b]) continue;
used[b] = YES;
for( int c=1; c< 5; c++) { // C3
if( used[c]) continue;
used[c] = YES;
for( int d=1; d< 5; d++) { // A
if( used[d]) continue;
used[d] = YES;
for( int e=1; e< 5; e++) { // B
if( used[e]) continue;
used[e] = YES;
int64 mat = 0; // 7x7の矩形
int64 layoutA, layoutB, layoutC, layoutD, layoutE; // 実際のレイアウト
if( layout(mat,z[a],layoutA) && // 順番に空いている場所に配置していく
layout(mat,z[b],layoutB) &&
layout(mat,z[c],layoutC) &&
layout(mat,z[d],layoutD) &&
layout(mat,z[e],layoutE) &&
bitcount(mat) == 49) {// 全て配置できたら7x7の矩形を隙間が無いか調べる
見つけた,重複チェックして出力する
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
}
int main( int argc, cstring argv[])
{
ProcTime pt;
pt.start();
int64 A = bit0|bit1|bit2|bit7|bit8|bit9|bit14|bit15|bit16; // 3x3の矩形
int64 B = bit0|bit1|bit7|bit8; // 2x2の矩形
int64 orgC1, orgC2, orgC3; // 6x6を3分割した図形(6x6の分割を解と一緒に表示するために使用する)
int64 C1, C2, C3; // 6x6を3分割した図形,正規化したもの
for( int row=1; row<= 5; row++) { // 横に切り込みを入れる位置
for( int col=1; col<= 5; col++) { // 縦に切り込みを入れる位置
cut66( row, col, C1, C2, C3, orgC1, orgC2, orgC3); // 6x6の矩形を3分割する。最大図形をC1に返す
// A,Bは正方形なので回転を考慮する必要は無いが，C1,C2,C3は回転を考慮する
for( int r1=0; r1< 4; r1++) {
for( int r2=0; r2< 4; r2++) {
for( int r3=0; r3< 4; r3++) {
check( orgC1, orgC2, orgC3, normalize(C1), normalize(C2), normalize(C3), A, B); // A,B,C1,C2,C3の5つの矩形で7x7になるか調べる
C3 = rotate90(C3);
}
C2 = rotate90(C2);
}
C1 = rotate90(C1);
}
}
}
pt.end();
ps( "%g秒\n", pt.sec());
return 0;
}
答えは1件出力されました。
いやー，1月5日に続きまたまた問題の読み間違い。ちょっと注意力が落ちているのかな。
お恥ずかしい限りです。
解速度
即