SRM510 Div1 Medium(500) TheLuckyGameDivOne

TheLuckyGameDivOne

選択する範囲を左から右に移動させていったときに、Johnの場合は個数が増える、Brusの場合は個数が減る場所だけ調べる。そのような場所は、BrusはLucky numberの右隣からの範囲、Johnはx+bLen-1がLucky numberとなるようなxからの範囲。

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

vector<long long>   L;  //  Lucky number
int                 n;  //  Lucky numberの個数
long long           jLen, bLen;
map<long long,int>  memoj, memob;

//  Brusが[p,p+bLen)を選択したときの個数
int brus( long long p )
{
    if ( memob.count(p) > 0 )
        return memob[p];

    int ans = 0;
    for ( int i=0; i<n; i++ )
        if ( p<=L[i] && L[i]<p+bLen )
            ans++;
    
    return memob[p] = ans;
}

//  Johnが[p,p+jLen)を選択したときの個数
int john( long long p )
{
    if ( memoj.count(p) > 0 )
        return memoj[p];

    int ans = brus(p);
    for ( int i=0; i<n; i++ )
        if ( p<=L[i]+1 && L[i]+1+bLen<=p+jLen )
            ans = min( ans, brus(L[i]+1) );

    return memoj[p] = ans;
}

class TheLuckyGameDivOne{public:
int find( long long a, long long b, long long jLen, long long bLen )
{
    L.clear();
    for ( int i=1; i<=10; i++ )
    for ( int j=0; j<1<<i; j++ )
    {
        long long l = 0;
        for ( int k=0; k<i; k++ )
            l = l*10 + (j>>(i-k-1)&1)*3+4;
        L.push_back( l );
    }
    n = (int)L.size();
    ::jLen = jLen;
    ::bLen = bLen;
    memoj.clear();
    memob.clear();

    int ans = john(a);
    for ( int i=0; i<n; i++ )
    {
        long long t = L[i]-bLen+1;
        if ( a<=t && t+jLen<=b+1 )
            ans = max( ans, john(t) );
    }
    
    return ans;
}};