AtCoder Beginner Contest 186: C – Unlucky 7の初心者解説

問題

公式の問題はこちらです．

問題文

高橋君は7が嫌いです．1以上N以下の整数のうち，10進法で表しても8進法で表しても7を含まないような数はいくつありますか？

制約

  • 1 <= N <= 10^5
  • Nは整数である．

解説

けんちょんさんの解説がめちゃくちゃスッキリしていて感動しました．以下一部抜粋です．たとえば，ある数nが10進数表記で7を含んでいるか確かめる場合はok(n, 10)，8進数表記で7を含んでいるか確かめる場合はok(n, 8)とし，戻り値がfalseであれば7を含むこととなります．

bool ok(int v, int b) {
    while (v) {
        if (v % b == 7) return false;
        v /= b;
    }
    return true;
}

私の愚直な解法を載せておきます．

judge_include_seven() という関数を作り，10進数表記の場合は上記と同じようなアルゴリズムで，7が含まれているかを調べました．さらに，convert_to_octal_num() という関数を用いて8進数表記に直した後，再度 judge_include_seven() により7が含まれているかどうかを判定しました．

#include <stdio.h>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// true if number include seven.
bool judge_include_seven(int num) {
    while (num!=0) {
        if (num%10 == 7) { return true; }
        num /= 10;
    }
    return false;
}

// return octal number
int convert_to_octal_num(int dec_num) {
    int oct_num = 0;
    int nxt_num = dec_num;
    int tmp_num = 0;
    int i = 0;
    while (1) {
        tmp_num = nxt_num % 8;
        oct_num += tmp_num * pow(10, i);
        i++;
        nxt_num /= 8;
        if (nxt_num == 0) {
            break;
        }
    }
    return oct_num;
}

int main(void) {
    int N;
    scanf("%d", &N);

    bool ret_dec, ret_oct;
    int count = 0;
    for (int i=1; i<=N; i++) {
        ret_dec = judge_include_seven(i);
        ret_oct = judge_include_seven(convert_to_octal_num(i));
        if (ret_dec==false && ret_oct==false) { count++; }
    }

    cout << count << endl;

    return 0;
}

まとめ・感想

私の書き方はかなり長くなってしまい，見本となる書き方ではないです．上記で紹介したけんちょんさんの解法のように簡潔に書けるようにしていきたいです．

コメント