SRM510 Div1 Medium(500) 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; }};