算数オリンピック
はてなのエンジニアが「算数オリンピック」に挑戦してみた、
という記事が面白そうだったので、Seaoak も挑戦してみました。
⇒ はてな若手エンジニアが「算数オリンピック」の問題を解いてみた
⇒ 算数オリンピック
とりあえず、最初の問題（問題６）は直感で解けました。
２問目（問題１）は、倍数を全部書き出して、出現する数字の数を数えて、正解。
３問目（問題３）は、高校時代に勉強した「整数問題」みたいな印象（なつかしい）。
とりあえず方程式を立てて、各変数が 1～9 の整数であるという条件で
とりうる値を絞り込み、最後は５個くらいのケースを場合分けでしらみつぶし。
かなり時間がかかりましたが、とりあえず全部の値を見つけられました。
# ５個以外の解が無いことも確認できました。
４問目（問題７）は、直感で解いたのですが、不正解。
くやしいので、Ｃ言語で解いてみました。
◎ ２問目（問題１）
#include <stdio.h>
int populate(int div, int count[])
{
int total = 0;
int i;
for (i=1; i<=9; i++) {
int j;
for (j=1; j<=9; j++) {
if (i==j) continue;
{
const int x = 10*i+j;
if (x % div) continue;
count[i]++;
count[j]++;
total++;
}
}
}
return total;
}
int main(int argc, char *argv[])
{
int table2[10] = {0};
int table4[10] = {0};
int table7[10] = {0};
const int total2 = populate(2, table2);
const int total4 = populate(4, table4);
const int total7 = populate(7, table7);
{
int i;
for (i=1; i<=9; i++) {
if (table2[i] != total2 - 21) continue;
if (table4[i] != total4 - 12) continue;
if (table7[i] != total7 - 8) continue;
printf("%d\n", i);
}
}
return 0;
}
◎ ３問目（問題３）
#include <stdio.h>
int main(int argc, char *argv[])
{
int i;
for (i=100; i<=999; i++) {
if (i % 10 == 0) continue;
{
const int x = i / 10 + i % 10;
if (i % x) continue;
}
{
const int y = i / 100 + i % 100;
if (i % y) continue;
}
printf("%d\n", i);
}
return 0;
}
◎ ４問目（問題７）
#include <stdio.h>
int populate(int x)
{
int count = 0;
while (x) {
if (x & 0x1) count++;
x >>= 1;
}
return count;
}
int main(int argc, char *argv[])
{
int count = 0;
int x;
for (x=0; x<(1<<25); x++) {
const int mask_column = ((0x1 << (5*4)) |
(0x1 << (5*3)) |
(0x1 << (5*2)) |
(0x1 << (5*1)) |
(0x1 << (5*0)));
if (populate(x) != 6) continue;
if (! ((x >> (5*4)) & 0x1f)) continue;
if (! ((x >> (5*3)) & 0x1f)) continue;
if (! ((x >> (5*2)) & 0x1f)) continue;
if (! ((x >> (5*1)) & 0x1f)) continue;
if (! ((x >> (5*0)) & 0x1f)) continue;
if (! ((x >> 4) & mask_column)) continue;
if (! ((x >> 3) & mask_column)) continue;
if (! ((x >> 2) & mask_column)) continue;
if (! ((x >> 1) & mask_column)) continue;
if (! ((x >> 0) & mask_column)) continue;
count++;
}
printf("%d\n", count);
return 0;
}
いずれもちゃんと正解が得られました。
ちゃちゃっとビット演算を使うときはＣ言語でも悪くないですねー
