以下の1x1,1x2,1x3,2x2,2x3,3x3の6個の矩形がある。矩形の対角上にある頂点を順に繋ぎ合わせて3x3,4x4,5x5の正方形を作る。
3x3は単独，4x4は1x1,1x2,1x3,2x2の5つ，5x5は6個全ての組み合わせで作成する。
4x4,5x5の矩形では3x3は繋ぎ合わせの端に位置するものとする。
繋ぎ合わせは例えば以下のようになる。
対角上にある頂点を繋ぎ合わせる必要があるので，以下のような繋ぎ合わせはあり得ない。
まずは以下のように矩形に記号を振る。
Fは固定して考えることが出来るので，A,B,C,D,Eの数字の割り当て問題と見なすことが出来る。
単純に考えると以下のようになる。
YesNo used[6];
int main( int argc, cstring argv[])
{
for( int a=0; a< 5; a++) {
used[a] = YES;
for( int b=0; b< 5; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=0; c< 5; c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=0; d< 5; d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=0; e< 5; e++) {
if( used[e]) continue;
used[e] = YES;
A=矩形[a],B=矩形[b],…
if( A,B,C,D,E で4x4の矩形が作成できるか? &&
3x3とA,B,C,D,E で5x5の矩形が作成できるか?) {
Find
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
return 0;
}
矩形を以下のような座標で考える。
矩形の繋ぎ合わせを対角上の頂点で行うことを考えると，矩形の繋ぎ合わせは単なる座標値の移動になる(タートルグラフィックス?)。
最初の図形のサンプルは以下のような座標になる。
座標値は以下のように7x7(49ビット)の図形と以下のように組み合わせることで処理を行いやすくする。
そうすると題意は以下のような図形を探すことになる。
実際には左側の4x4の図形はF(3x3の矩形)と重ならなければ位置はどこにあっても良い。
Fは端にあるので，残りの図形を探し始めるのは(3,0)，(3,3)，(0,3)の位置からになる。
Bは正方形でないので(0,0)からの組み合わせは以下のように2通りある(判りやすいように1,2と番号を振った)。
これを座標軸で表現すると以下のようになる。
例えばFとBの組み合わせを考えたとき，以下のような図が考えられる。
(2007.03.12)私は上記ねじれ(mirror)の組み合わせが「あり」だと思ったけど，もしかしたら出題者の意図は「なし」かも知れない気がしてきた。
つまり，ねじれは別の組み合わせと見なすのかも知れない。もしねじれを「なし」とすると，
「ねじってから4x4の判定，5x5の判定をする」ように変更する必要がある。
今は「4x4の判定の中でねじれを考慮，5x5の判定の中でねじれを考慮」している。
ただ，ねじれを考慮しても解答が1件しか出なかったのでこれで良しとする。
C,Eの図形に関しても同様に処理しなければならない。
これを考慮すると，A,B,C,D,Eで4x4の矩形が出来るかどうかは以下のようになる。
class rect { // 矩形
public:
rect( char c, int x, int y); // 矩形に文字と大きさを割り当てる
rect( const rect& r); // コピー
void mirror(); // MIRRORする,正方形でもMIRRORする
YesNo end_of_mirror(); // MIRROR出来たか?
void rotate90(); // 左に90度回転
int64 move( int& x, int& y); // (x,y)から矩形分座標位置を移動する,戻り値は図形のビット表現
char getchr() { return m_c;} // 矩形文字を得る(ダンプ出力用)
private:
char m_c; // 矩形文字('A','B','C','D','E','F'の何れか)
int m_x; // 座標位置
int m_y; //
YesNo m_yn_square; // 正方形か?
int m_mirror_count; // 正方形でない場合MIRRORした回数(初期値:0,最大値:1)
};
YesNo check4x4_ok( int start_x, int start_y, rect A, rect B, rect C, rect D, rect E) // 4x4の矩形が出来てFと重ならないか?
{
…
}
YesNo check4x4_with_rotate( int start_x, int start_y, rect A, rect B, rect C, rect D, rect E) // 回転を考慮する
{
for( int rotateA=0; rotateA< 4; rotateA++) {
A.rotate90();
for( int rotateB=0; rotateB< 4; rotateB++) {
B.rotate90();
for( int rotateC=0; rotateC< 4; rotateC++) {
C.rotate90();
for( int rotateD=0; rotateD< 4; rotateD++) {
D.rotate90();
for( int rotateE=0; rotateE< 4; rotateE++) {
E.rotate90();
if( check4x4_ok( start_x, start_y, A,B,C,D,E)) return YES;
}
}
}
}
}
return NO;
}
YesNo check4x4( int start_x, int start_y, rect start_A, rect start_B, rect start_C, rect start_D, rect start_E) // 4x4の矩形が出来るか?
{
for( rect A(start_A); !A.end_of_mirror(); A.mirror()) {
for( rect B(start_B); !B.end_of_mirror(); B.mirror()) {
for( rect C(start_C); !C.end_of_mirror(); C.mirror()) {
for( rect D(start_D); !D.end_of_mirror(); D.mirror()) {
for( rect E(start_E); !E.end_of_mirror(); E.mirror()) {
if( check4x4_with_rotate( start_x, start_y, A,B,C,D,E)) {
return YES;
}
}
}
}
}
}
return NO;
}
int64 plane5x5 = bit14|bit15|bit16|bit17|bit18|bit21|bit22|bit23|bit24|bit25|bit31|bit32|bit38|bit39|bit45|bit46;
rect R[6] = {
rect('A',1,1),
rect('B',2,1),
rect('C',3,1),
rect('D',2,2),
rect('E',3,2),
rect('F',3,3),
};
main() {
for(a)for(b)for(c)for(d)for(e) {
if( check4x4( 3,0,R[a],R[b],R[c],R[d],R[e]) ||
check4x4( 3,3,R[a],R[b],R[c],R[d],R[e]) ||
check4x4( 0,3,R[a],R[b],R[c],R[d],R[e])) {
// 同じようなチェック関数check5x5()を作って呼び出す。違いは出来た図形がplane5x5になるかどうか。
if( check5x5( 3,0,plane5x5,R[a],R[b],R[c],R[d],R[e])) Find;
else if( check5x5( 3,3,plane5x5,R[a],R[b],R[c],R[d],R[e])) Find;
else if( check5x5( 0,3,plane5x5,R[a],R[b],R[c],R[d],R[e])) Find;
}
}
}
rectの実体は以下のようになる。
rect::rect( char c, int x, int y) // 座標位置を割り当てる
{
m_c = c;
m_x = x;
m_y = y;
m_yn_square = YES;
if( abs(m_x) != abs(m_y)) m_yn_square = NO; // x=yでないので正方形でない
m_mirror_count= 0;
}
rect::rect( const rect& r) // コピー
{
m_c = r.m_c;
m_x = r.m_x;
m_y = r.m_y;
m_yn_square = YES;
if( abs(m_x) != abs(m_y)) m_yn_square = NO;
m_mirror_count= 0;
}
void rect::mirror()
{
m_y = -m_y;
m_mirror_count++;
}
YesNo rect::end_of_mirror()
{
if( m_yn_square && m_mirror_count >= 1) return YES; // 正方形の場合mirrorは必要ない
if( m_mirror_count >= 2) return YES; // 長方形の場合は1回有効
return NO;
}
void rect::rotate90() // 90度左回転
{
int T = m_x;
m_x = -m_y;
m_y = T;
}
int64 get7x7bit( int x, int y, int dx, int dy) // (x,y)-(x+dx,y+dy)の図形を7x7のbitで取得する
{
x += dx;
y += dy;
if( x < 0) return 0;
if( y < 0) return 0;
if( x >= 7) return 0;
if( y >= 7) return 0;
y = 7-y-1;
int64 bit = 1;
bit <<= y*7;
bit <<= x;
return bit;
}
int64 rect::move( int& org_x, int& org_y)
{
int start_x = org_x;
int start_y = org_y;
if( m_x < 0) start_x += m_x;
if( m_y < 0) start_y += m_y;
org_x += m_x;
org_y += m_y;
if( org_x < 0 || org_x > 7 ||
org_y < 0 || org_y > 7) return 0; // 7x7の図形をはみ出た
int64 plane = 0;
int X = m_x;
int Y = m_y;
if( X < 0) { X = -X; }
if( Y < 0) { Y = -Y; }
for( int x=0; x< X; x++) {
for( int y=0; y< Y; y++) {
plane |= get7x7bit( start_x, start_y, x, y);
}
}
return plane;
}
答えは1件出力されました。
今考えると最初から図形のままの方が扱い易かったかも…
おかげで，途中重なりをチェックした枝刈りをしていないので処理に時間が掛かってしまった。反省。
ただ，図形のままだと頂点を繋ぎ合わせる処理が面倒だし…
短期決戦プログラムなのでやはり開発速度優先だからやむを得ないか。
今日「箱根ターンパイク」の入口の前を通ったら「TOYO TIRES ターンパイク」になっていた。
ネーミングライツ恐るべし。道の名前まで変えてしまうんだ。
私が乗る近所のバスは距離によって料金が異なり，整理券が無く前払いなのでバス停の名前を言って料金を払うことになっている。
私は「ダイクマ前」ってバス停には無い名前を言って乗っていた。ただ最近はダイクマが撤退したので「サミット前」と言うようにしている。
正式な名前は「○○2丁目」か「○○3丁目」か「○○4丁目」なんだけど，うーん，たまにしか利用しないので覚えられない。
解速度
Pentium Xeon2.4GHz で約2.4秒