はてな若手エンジニアが「算数オリンピック」の問題を解いてみた - はてなブックマークニュース
これの問題７に挑戦！
小学生でも2%の人が解いた問題ですね。
むむ、小学生に負けるわけには行きませんな！
さて、紙と鉛筆を用意・・・しないでVisualStudioを起動…っと！
変な見え張って解けないほうがよっぽど恥ずかしい！
聞くは一時の恥聞かぬは一生の恥！！
私は文明の利器で戦う！！
ということで、できました。
「25bitだな！」と言っているとおり、ビット操作を使うことにします。
#include <iostream>
int numofbits5(unsigned int bits) {
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
bool Check(unsigned int board){
if (numofbits5(board) != 6) return false;
for(int i = 0; i < 5; i++){
// 0x1b = 11111
// 0x108421 = 1 0000 1000 0100 0010 0001
if ((board & (0x1f << i * 5)) == 0) return false;
if ((board & (0x108421 << i)) == 0) return false;
}
return true;
}
int main(){
int count = 0;
for(unsigned int i = 0; i < (1 << 25); i++){
if (Check(i)) count++;
}
std::cout << "count = " << count << std::endl;
return 0;
}
まずはコマが６個なので、立っているビットを数えます。
ぐぐる様に聞いたら、このサイトを教えてくれたのでコピペ…。
ええい、文明の利器で戦うと言ったではないか！！
そのかわり、縦横のいずれかのマスにコマがある部分は考えました。
論理積（AND）を使えば、関係ないビットをすべてオフにできるので、
一列(or 一行)だけのビットを取り出します。
もし、取り出した結果が0ならば、その列(or 行)にはコマがないことになります。
あとはこれを2^25回forでぶん回すだけ！
Releaseなら1秒以内で答えが出たよ！！
小学生でも解ける問題なだけに楽勝でしたね！