Edited at

サイコロの配置に関する問題を乱数を使って解く(AOJ ITP1_11_B/C)

More than 3 years have passed since last update.

承前 : サイコロの回転をシミュレート(AOJ ITP1_11_A)


問題の概要


ITP1_11_B

前提:サイコロの各面の数字として、6つの数が与えられる。

問題:上の数からなるサイコロを適当に回転したときの上面と前面の数字が与えられる。右面の数字を出力せよ。


ITP1_11_C

前提:2つのサイコロの各面の数字として、それぞれ6つの数が与えられる。

問題:2つのサイコロが同一(適当に回転させたとき面の配置が一致する)か調べよ。


乱数を用いる動機

この問題には決定的な解法はもちろんある(はず)。

しかし、私は昔から空間認識系の問題(小学校でやった、展開図とかのあれ)が大の苦手で、どうにも解法が浮かばない。

じゃあ実際に転がして確かめればいいじゃん、という発想。


やり方


ITP1_11_B

上面と前面が一致するまでひたすら回転。

一致したところでその時の右面の数字d[2]を返す。

(停止しない可能性があることに注意)

d[0]dの現在の上面の数字を、d[1]は前面の数字を返す

int p_r(dice d,int up,int front){

auto rgen = std::bind(
std::uniform_int_distribution<>(0,3),std::mt19937(time(nullptr))
);
char dir[]={'N','E','W','S'};
while(up!=d[0]||front!=d[1]){
d.mov(dir[rgen()]);
}
return d[2];
}

(この関数名当時の私はどう考えて付けたんだろう…意味が分からん)


ITP1_11_C

適当な回数だけ転がして配置が一致すれば同じものとする。

(どれだけ回数を増やしても誤答を返す可能性があることに注意)

bool issame(dice d1,dice d2){

auto rgen = std::bind(
std::uniform_int_distribution<>(0,3),std::mt19937(time(nullptr))
);
int i=0;
while(i<100){
d1.mov(dir[rgen()]);
if(d1==d2)return true;
i++;
}
return false;
}

このためにdiceに次の演算子オーバーロードを追加した。

bool dice::operator==(dice d){

for(int i=0;i<6;i++){
if(v[i]!=d[i])return false;
}
return true;
}


感想

高速演算さまさま。

暇な人がいたら決定的な解き方教えてください。