SRM526 Div2 Hard(1000) SumOfLuckiness

TopCoder

SumOfLuckiness

lucky(x)を0からxまでのluckinessの合計とすると、答えはlucky(B)-lucky(A-1)。まずは、iとjそれぞれについて、i桁以下で(4の個数)-(7の個数)=jとなる整数の個数T[i][j]を動的計画法で求める。例えば、x=526とすると、0-99, 100-199, 200-299, 300-399, 400-499, 500-509, 510-119, 520, 521, 522, 523, 524, 525, 526と分けることで、Tを使ってそれぞれの組のluckinessの合計が求められる。

#include <vector>
#include <map>
using namespace std;

long long lucky( int A )
{
    //  T[i][j]: i桁以下で(4の個数)-(7の個数)=jな整数の個数
    map<int,int> T[10];
    T[0][0] = 1;

    for ( int i=0; i<10-1; i++ )
        for ( int j=-i; j<=i; j++ )
            for ( int k=-1; k<=1; k++ )
                T[i+1][j+k] += (k==0?8:1)*T[i][j];

    int t = 1000000000;
    int f = 0;
    long long ans = 0;
    for ( int i=9; i>=0; i-- )
    {
        for ( int j=0; j<A/t; j++ )
        {
            int d = j==4 ? 1 : j==7 ? -1: 0;
            for ( int k=-i; k<=i; k++ )
                ans += T[i][k]*abs(f+d+k);
        }
        f += A/t==4 ? 1 : A/t==7 ? -1 : 0;
        A -= A/t*t;
        t /= 10;
    }
    ans += abs(f);

    return ans; 
}

class SumOfLuckiness{public:
long long theSum( int A, int B )
{
    return lucky(B)-lucky(A-1);
}};