各面を白か黒かに色分けした立方体を振って見た目が3通りになるように色付けする。
3通りは1/3の確率にならなければならない。
2通りの大きな勘違いをする人がいそうな問題。
(勘違いその1)
1面だけに黒を塗る。すると以下のような見え方になる。
Aは上面が黒，Bは側面が黒，Cは底面が黒。
パターンとしては3通りだけど確率は1/3にならない。
(勘違いその2)
こちらの勘違いは新聞の紙面に書かれた図形の見え方で判断してしまう。
この3パターンの見え方が出来るように3面に色を付ける。
上方からはサイコロの5つの面が見えるので，5つの面を判断材料にしなければならない。
サイコロをぐるっと回転してみて同じパターンが出現する場合は同じに見なすってこと。
サイコロを展開すると以下のように向かい合う面の数字の和が7になる。
1が上面に来たとき見えるのは以下のような5つの数字(下の6は見えない)。
これを以下のような9ビットの数に割り当てて考える。
9ビットの数にして考えるのは，回転した場合の見た目が同じ場合を判断したいため。
サイコロの6面全てに色を付けて見た目どうなるか調べるプログラムの大まかな感じは以下の通り。
6面をビットで考え1が黒，0が白とする。
for( int i=0; i<= 0x3F; i++) {
iを6面のサイコロと考えそれを振る。ビットがONが黒，OFFが白と見なす。
1が上面に来た場合，2が上面に来た場合，3が上面に来た場合，…を考える。
それぞれを平面図に展開し，展開した平面図を正規化しその数字を記憶する。
平面図の値が3通りで同じ回数だけ出現したら，その時のiが塗り分けの答えになる。
}
これが基本的な考え方。この考え方でプログラムすると以下のようになる。
int getbit( int val, int bitpos) // 1オリジンでビットを取り出す
{
int b = 1 << (bitpos-1); // 1オリジンなので-1してからシフトする
if( val & b) return 1; // ビットがONか調べる
return 0;
}
int rotate3x3( int val) // 3x3の矩形を左に90度回転する
{
// ０１２ ２５８
// ３４５ ⇒ １４７
// ６７８ ０３６
…
}
int min4( int v1, int v2, int v3, int v4) // 4つの数字の最小値を取得する
{
…
}
cstring bitstr( int val) // 黒く塗った部分の数値,白い部分は.を出力する
{
static char bits[10];
if( val & bit0) bits[0] = '1'; else bits[0] = '.';
if( val & bit1) bits[1] = '2'; else bits[1] = '.';
if( val & bit2) bits[2] = '3'; else bits[2] = '.';
if( val & bit3) bits[3] = '4'; else bits[3] = '.';
if( val & bit4) bits[4] = '5'; else bits[4] = '.';
if( val & bit5) bits[5] = '6'; else bits[5] = '.';
bits[6] = NIL;
return bits;
}
void expand( int val, int face1, int face2, int face3, int face4, int face5) // 上から見た展開図で考える
{
// face1が上面,それ以外は側面
// それぞれの面の黒/白を取得する
int b1 = getbit( val, face1); // 上面の黒白
int b2 = getbit( val, face2); // 側面の黒白
int b3 = getbit( val, face3); // 側面の黒白
int b4 = getbit( val, face4); // 側面の黒白
int b5 = getbit( val, face5); // 側面の黒白
int pattern1 = (b1<<4) | (b2<<1) | (b3<<3) | (b4<<7) | (b5<<5); // これを3x3の矩形内に配置し9ビットの数と見なす
int pattern2 = rotate3x3(pattern1); // 「正規化」のために回転して考える(90度)
int pattern3 = rotate3x3(pattern2); // 「正規化」のために回転して考える(180度)
int pattern4 = rotate3x3(pattern3); // 「正規化」のために回転して考える(270度)
int pattern = min4( pattern1, pattern2, pattern3, pattern4); // 回転して一番小さな数をこの展開図の値とする
num[pattern]++; // 展開図の値を記憶する
}
int main( int argc, cstring argv[])
{
for( int i=0; i<= 0x3F; i++) { // 6面全てに色を付けてみる
for( int k=0; k<= 0x3F; k++) num[k] = 0; // 色付けし直す毎に前の記録を削除する
// この色付けでサイコロを振る。1から6の出る確率は1/6で同じ。
expand( i, 1,2,3,5,4); // 1が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
expand( i, 2,3,1,4,6); // 2が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
expand( i, 3,1,2,6,5); // 3が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
expand( i, 4,1,5,6,2); // 4が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
expand( i, 5,1,3,6,4); // 5が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
expand( i, 6,2,4,5,3); // 6が上面に来た場合,それを上からの平面図に展開し正規化した値を記憶する
// 正規化した値が3通り出現し同じ回数の場合，iが答えになる
int num_value = 0; // 出現した数
int num_cnt = 0; // 出現した回数
YesNo ynFind = YES; // 解が見つかった?
for( k=0; k<= 0x3F; k++) { // 正規化した数字を調べる
if( num[k] != 0) { // 正規化した数がある
num_value++; // 出現回数を勘定する
if( num_cnt == 0) num_cnt = num[k]; // 出現した数
else if( num_cnt != num[k]) { // 違う数が出現した,出現する確率が違うってこと
ynFind = NO;
}
}
}
if( num_value != 3) { // 出現した数字は3種類?
ynFind = NO; // 3種類でない場合ジャンケンには使えない
}
if( ynFind) {
ps( "Find %d %2x %s\n", bitcount(i), i, bitstr(i));
}
else {
ps( " %d %2x %s\n", bitcount(i), i, bitstr(i));
}
}
return 0;
}
答えは20件出力されました。しかし実質2件。2件は白黒を反転させたもの。
(2007.1.5)「Find」と出力されるのは24件でした。上記ソースの部分のうち赤い部分が間違っていて，「1,4」と「3,6」のパターンを見逃していた。
この答えを2件表示にさせるためには結構な労力が掛かるので，今回はこれでお仕舞い。
例えば以下の2つの図形は2色で色付けされたパターンとしては同じだが，これを同じと認識するのは結構大変。
頭で考えると結構簡単だと思うけど，解答を書くときに「○○」とだけ書くとダメで，しっかりと「△△う○○」と書かなければならないので星２つ問題なのかな。
来週29日の金曜日は夕刊が休みなので今年はこれが最終問題。
ノロウィルスが流行っているようなので体には気をつけたい。皆様良いお年を。
解速度
即