SRM 510 div1 easy:TheAlmostLuckyNumbersDivOne

SRM510の練習会に参加しました。1問も解けなくて国内予選の前日なのにお通夜状態でした。

問題

TopCoder Statistics - Problem Statement

解法

桁DPでも解けるんですが今回は状態量がに抑えられるので全探索します。下のコードでは500msくらいかかってるので危ないですが,もっと枝刈りできるのでそれほど問題はないです(下の書き方だとすべてのケースで500msほどで通せることが保証されているので大丈夫)。

本番書いたコード

ll ans;

void dfs(int cur, ll a, ll b, string& s, int num, int flag) {
    if (cur == 16) {
        ll x = stoll(s);
        if (a <= x && x <= b) ans++;
        return;
    }
    if (flag == 0) {
        s[cur] = '0';
        dfs(cur+1, a, b, s, num, 0);
    }
    for (int i = 0; i < 10; i++) {
        if (flag == 0 && i == 0) continue;
        if (i == 4 || i == 7) {
            s[cur] = (char)('0'+i);
            dfs(cur+1, a, b, s, num, 1);
        } else {
            if (num > 0) continue;
            s[cur] = (char)('0'+i);
            dfs(cur+1, a, b, s, num+1, 1);
        }
    }
}

class TheAlmostLuckyNumbersDivOne {
public:
    long long find(long long a, long long b) {
        ans = 0;
        string s;
        s.resize(16);
        dfs(0, a, b, s, 0, 0);
        return ans;
    }
};