SRM514 Div2 Hard(1000) MagicalGirlLevelThreeDivTwo

MagicalGirlLevelThreeDivTwo

hi-lo≦1000という制約があるので、1ビットごとに0か1かを調べる。事前に各要素の長さを求めておけば、O(n²)で辿ることができる。文字列長はlong longで表現できる長さを超えうるけど、hi≦10¹⁵という制約があるので、10¹⁵以上の適当な値を入れておけば良い。

サンプルインプットの４個目のバイトを１つの文字列に固めてから１６ビットずつに区切ってShiftJISるととマミさんの必殺技の名前になる

https://twitter.com/kyuridenamida/status/101255069755916289

www　気付かなかった。

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

int getbit( vector<string> first, vector<long long> L, int s, long long p )
{
    int K = (int)first.size();

    if ( s < K )
    {
        return first[s][(int)p]-'0';
    }
    else
    {
        long long t = 0;
        for ( int i=s-1; ; i-=K )
        {
            if ( p < t+L[i] )
                return getbit(first,L,i,p-t);
            t += L[i];
        }
    }
}

class MagicalGirlLevelThreeDivTwo{public:
int theCount( vector <string> first, int n, long long lo, long long hi )
{
    long long M = 1000000000000000ll;

    int K = (int)first.size();

    vector<long long> L(n+1);
    for ( int i=0; i<=n; i++ )
        if ( i < K )
            L[i] = first[i].size();
        else
            for ( int j=i-1; j>=0; j-=K )
                L[i] += L[j],
                L[i] = min( L[i], M );
    
    int ans = 0;
    for ( long long i=lo; i<=hi; i++ )
        ans += getbit( first, L, n, i );
    return ans;
}};