P8680 [蓝桥杯 2019 省 B] 特別な数の和

問題説明

数値の桁に2、0、1、9が含まれる数字（先頭の0は除く）に興味があるとします。1から40までの範囲において、このような数は1、2、9、10から32、39、40であり、合計28個あります。それらの総和は574です。

n以下の範囲で、このような数の総和を求めてください。

入力形式

一行に整数nが与えられます。

出力形式

条件に合う数の総和を一行に出力してください。

例

入力例

40

出力例

574

制約

• 20%のテストケース：1 ≤ n ≤ 10
• 50%のテストケース：1 ≤ n ≤ 100
• 80%のテストケース：1 ≤ n ≤ 1000
• すべてのテストケース：1 ≤ n ≤ 10000

解法

最もシンプルな解法は全探索です。各数値について、2、0、1、9のいずれかが含まれているかどうかを判定します。

全探索による実装

#include <cstdio>
bool check(int num) {
    int digit;
    while(num) {
        digit = num % 10;
        if(digit == 2 || digit == 0 || digit == 9 || digit == 1)
            return true;
        else
            num /= 10;
    }
    return false;
}
int main() {
    int n, total = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        if(check(i))
            total += i;
    }
    printf("%d\n", total);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long sum = 0;
    for(int i = 1; i <= n; i++) {
        int temp = i;
        while(temp != 0) {
            int digit = temp % 10;
            if(digit == 2 || digit == 0 || digit == 1 || digit == 9) {
                sum += i;
                break;
            }
            temp /= 10;
        }
    }
    cout << sum << endl;
    return 0;
}

効率的な解法

数のパターンには一定の規則があります。例えば、10個の連続した数字をグループとして扱い、それぞれのグループの末尾の数字だけを確認することで、計算量を削減できます。

#include <cstdio>
bool hasSpecialDigit(int num) {
    int digit;
    while(num) {
        digit = num % 10;
        if(digit == 2 || digit == 0 || digit == 9 || digit == 1)
            return true;
        else
            num /= 10;
    }
    return false;
}
int main() {
    int n, result = 0, groupBase, remainder;
    scanf("%d", &n);
    for(int i = 1; i < n && n >= 10; i += 10) {
        if(hasSpecialDigit(i / 10))
            result += i * 10 + 35;
        else
            result += i * 4 + 8;
    }
    groupBase = (n / 10) * 10;
    if(hasSpecialDigit(n / 10)) {
        for(int i = groupBase; i <= n; ++i)
            result += i;
    } else {
        remainder = n % 10;
        if(remainder < 9) {
            if(remainder < 2) {
                if(remainder < 1)
                    result += groupBase;
                else
                    result += groupBase * 2 + 1;
            } else
                result += groupBase * 3 + 3;
        } else
            result += groupBase * 4 + 12;
    }
    printf("%d", result);
    return 0;
}