以下の形状の図形がある。
ここに「コ」の字型をした以下の図形をマス目が一致するように重ねる。
元の図形の2升を適当に選べば,「コの字」をどのように乗せても,そのうち1升が必ず「コの字」に重なるように出来る。
2升を求める。
図形問題だけどプログラムを作るには比較的簡単な問題。頭で考えても簡単な所が悲しいけど…
元の図形を4x4の図形と見なし,0〜15の番号を振る。
上記番号と16ビット整数のビット位置を対応させて考える。問題図の図形から例えば以下の2点を選択すると選択した図形は数値で
0001 0000 0100 0000 = 0x1040 になる。
元の図形から全ての2升(2点)を選択するには以下のようなコードになる。
for( int i=0; i< 0x10000; i++) { if( !(i&0x0013) && // 0x0013 は元の図形の欠けている場所 bitcount(i) == 2) { // ビット数が2ということが2点に相当する // 元の図形から2点を選択した } }
「コの字」をどんな配置にしても選択した2点のどちらかと重なればそれが答えになる。
事前に「コの字」の全ての配置を求めておけば,プログラムは以下のようになる。
int main( int argc, cstring argv[]) { // まず「コの字」の配置を全て求めておく。 int N = 0; // 「コの字」の置き方の総数 const int S = 100; int z[S+1] = {0}; // 「コの字」のビット表現 N = calcAllZ( z, N, 0x0057); // 「コの字」の置き方-1 N = calcAllZ( z, N, 0x0313); // 「コの字」の置き方-2 N = calcAllZ( z, N, 0x0075); // 「コの字」の置き方-3 N = calcAllZ( z, N, 0x0323); // 「コの字」の置き方-4 // 16升の中から2点を選択して,図形の全ての可能性と比較する。 for( int i=0; i< 0x10000; i++) { if( !(i&0x0013) && // 0x0013 は元の図形の欠けている場所 bitcount(i) == 2) { // ビット数が2ということが2点に相当する // 16マスの中から2点を選択した // 全ての組み合わせと重なり合うか調べる。 YesNo yn_find = YES; for( int j=0; j< N; j++) { if( !(i & z[j])) { // 重なりが無い yn_find = NO; break; } } if( yn_find) { print_find( i); } } } return 0; }
「コの字」は以下のような置き方を基本に4x4の図形内での配置を全て考えておく。
calcAllZ()は以下のようになる。
int calcAllZ( int z[], int n, int zukei) // 「コの字」の配置方法を求める { int saveZukei = zukei; // 4x4内で基本図形をずらして配置できるものを選ぶ for( int ix=0; ix< 3; ix++) { // X方向にずらす zukei = saveZukei; for( int iy=0; iy< 3; iy++) { // Y方向にずらす if( zukei) { // ずらしても4x4内に図形が存在する if( !(zukei & 0x0013)) { // 左上の欠けている部分に重なっている場合はダメ z[n++] = zukei; // そうでなければ配置できる } } else { break; } zukei = shiftZukei( zukei, NO, YES); // Y方向にずらす } saveZukei = shiftZukei( saveZukei, YES, NO); // X方向にずらす } return n; }
答えは1件出力されました。
今年は栗がうまい。去年は買う栗がことごとく外れだった。
解速度
即