TopCoderOpen 2015 Round 2D

BalancedSubstrings.cpp

#include <string>
using namespace std;

class BalancedSubstrings{public:
int countSubstrings( string s )
{
    int n = (int)s.size();
    int ans = 0;

    for (int i=0; i<n; i++)
    {
        int a = 0;
        int b = 0;
        for (int j=i; j<n; j++)
        {
            if (s[j] == '1')
            {
                a += j;
                b ++;
            }

            if (b==0 || a%b==0)
                ans++;
        }
    }

    return ans;
}};

BallsInBoxes.cpp

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

class BallsInBoxes{public:
long long maxTurns( long long N, long long K )
{
    long long ans = 0;

    N = N-K+1;
    
    //while (N>2*K)
    //{
    //  N -= K;
    //  ans++;
    //}

    if (N>2*K)
    {
        long long c = (N-2*K+K-1)/K;
        N -= K*c;
        ans += c;
    }

    while (N>1)
    {
        N = (N+1)/2;
        ans++;
    }

    return ans;
}};

//  ↓確認用にこれで小さいケースを計算した

vector<int> B;
long long N, K;

long long BT(int s)
{
    int c = 0;
    for (int i=0; i<=N-K; i++)
    {
        bool f = true;
        for (int j=0; j<N; j++)
            if ((j<i || i+K<=j) && B[j]==1 ||
                (i<=j && j<i+K) && B[j]==0)
                f = false;
        if (f)
            c++;
    }
    if (c==0)
        return -1;
    if (c==1)
        return s;

    long long ans = N;

    for (int i=0; i<N; i++)
    if (B[i] == -1)
    {
        long long t = 0;

        for (int j=0; j<2; j++)
        {
            B[i] = j;
            
            long long a = BT(s+1);
            if (a!=-1)
                t = max(t, a);

            B[i] = -1;
        }

        ans = min(ans, t);
    }

    return ans;
}

class _BallsInBoxes{public:
long long maxTurns( long long N, long long K )
{
    B = vector<int>(N, -1);
    ::N = N;
    ::K = K;

    return BT(0);
}};

/*
 0
 1 0
 2 1 0
 3 2 1 0
 4 2 2 1 0
 5 3 2 2 1 0
 6 3 3 2 2 1 0
 7 4 3 3 2 2 1 0
 8 4 3 3 3 2 2 1 0
 9 5 4 3 3 3 2 2 1 0
 10 5 4 3 3 3 3 2 2 1 0
*/