SRM510 Div1 Easy - TheAlmostLuckyNumbersDivOne

問題

　からまでの整数の中で4と7以外の数字を多くとも1つしか使わない数字はいくつあるか求めよ。

解法

　桁DPのメモ化が無いようなもの。状態として、

• 上から何桁目を見ているか
• 4と7以外の数字が何回出てきたか
• 今まで見てきた要素でより大きいことが保証されているか
• 今まで見てきた要素でより小さいことが保証されているか
• 0以外の数字が出てきたか(一番左に並ぶ0はカウントしてはいけないため)

　を保持しながら条件に合わせて遷移していけばよい。

反省

　メモ化再帰、をやろうとしたところメモ化する必要はなかった。実質的に枝刈り全探索ということになるのか。しかし気持ちとしては完全に桁DPで、DP苦手なのでかなり苦しんだ。

　最初は問題文を誤読していて「4と7以外の数字のうち最大のものが一番左に来ているような整数の数を求めよ」かと思ってなんじゃこの問題は！ と苦しんでいた。

　誤解に気づいてからも、forループでのDPを書こうとして挫折し、結局再帰関数を書くことに。最初っからこっちで書き始めればよかったのに。

　以上以下の条件を満たす数を求める問題で、ある整数以下について条件を満たす数を求める関数を作ってとして答えを求めるのは常識なはずなのにそれができない。こういうところで無駄に難しい問題を解きに行ってしまうから実装で大変な目に遭うんだ。

　先頭の0は数えないようにするという部分でもかなり苦しんだ。最初はの桁をの桁に揃えるときに埋める数字を変えていろいろやろうとしたが、結局状態に0以外の数字が出たかどうか持たせるのが早い。こういうところでも桁DPに慣れているかどうかというのが顕著に表れるのだと思う。慣れていこう。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class TheAlmostLuckyNumbersDivOne {
public:
    long long find(long long a, long long b) {
        a_str = to_string(a);
        b_str = to_string(b);
        while (a_str.size() != b_str.size()) {
            a_str.insert(0, "0");
        }

        return solve(0, 0, false, false, false);
    }
private:
    string a_str, b_str;
    ll solve(ll d, ll num, bool bigger_than_a, bool smaller_than_b, bool appear_non0) {
        if (num >= 2) {
            return 0;
        }
        if (d == a_str.size()) {
            return 1;
        }
        ll result = 0;
        ll a_num = a_str[d] - '0';
        ll b_num = b_str[d] - '0';

        ll low  = ( bigger_than_a ? 0 : a_num);
        ll high = (smaller_than_b ? 9 : b_num);

        for (ll i = low; i <= high; i++) {
            ll add = (appear_non0 ? (i != 4 && i != 7) : (i != 0 && i != 4 && i != 7));
            result += solve(d + 1, num + add, i > a_num || bigger_than_a, i < b_num || smaller_than_b, appear_non0 || i != 0);
        }

        return result;
    }
};