Darumaka Number

2 secs 1024 MB

$N$ の桁数を $D$ とします。 $D$ 桁の良い数を全探索することを考えましょう。
良い数に使われている数字は $2$ 種類のみであり、 $2$ 種類のみの数字として代表的なものとして、 $2$ 進数があります。
また、 $2$ 進数の $0$ を $4$ 、 $1$ を $5$ に変換すれば良い数に変換することができます。
$D$ 桁の二進数は、bit 全探索をすることにより $O(D \times 2^D)$ の計算量で全通り列挙することができます。
よって、それぞれの良い数と $N$ を比較することによって $N$ 以下で最大の良い数を求めることができます。
$N$ 以下の良い数で $D$ 桁のものがない場合は、 $5$ を $D - 1$ 個並べたものが答えとなることに注意してください。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
    long long n;
    cin >> n;

    string s = to_string(n);
    int digit = s.size();

    if(digit == 1){
        if(n == 4){
            cout << 4 << endl;
        }else{
            cout << 5 << endl;
        }
        return 0;
    }

    long long ans = 0;
    for(int i = 0; i < digit - 1; i++){
        ans *= 10;
        ans += 5;
    }

    for(int bit = 0; bit < (1 << digit); bit++){
        long long num = 0;
        for(int i = 0; i < digit; i++){
            num *= 10;
            int mask = 1 << i;
            if(bit & mask){
                num += 4;
            }else{
                num += 5;
            }
        }
        if(num <= n){
            ans = max(ans, num);
        }
    }
    cout << ans << endl;
}