SRM538 Div2 Hard(1050) SkewedPerspectives

SkewedPerspectives

連続した見えている黒いキューブの個数が全て偶数ならば、見えているとおりに積み上げれば良い。問題は、それが奇数個の場合。↓の左のように1個だけ隠す。奇数個の黒いキューブが地面に接している場合、黒いキューブが1個ならば無理だが、3個以上ならば↓の右のようにおける。このように配置できるだけのキューブと幅があるかどうかを調べる。

 0
 B   B
 B   B
0B   B
10  BB
21  B0

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

bool check( vector<int> cubes, int B, int w, string view )
{
    //  見えているキューブの個数を数えつつ、
    //  必要な見えないキューブの個数を調べる
    vector<int> S;

    for ( int i=0; i<(int)view.size(); )
    {
        if ( view[i]=='b' )
        {
            int b = 0;
            while ( i+b<(int)view.size() && view[i+b]=='b' )
                b++;
            B -= (b+1)/2;
            if ( b%2!=0 )
                if ( i==0 )
                    if ( b==1 )
                        return false;
                    else
                        S.push_back(1);
                else
                    S.push_back(i-1);
            i += b;
        }
        else
        {
            cubes[view[i]-'0']--;
            i++;
        }
    }

    //  見えるキューブが足りない
    if ( cubes[0]<0 || cubes[1]<0 || cubes[2]<0 || B<0 )
        return false;

    //  幅が足りない
    if ( w < (int)S.size()+1 )
        return false;
    
    //  見えないキューブが足りない
    for ( int i=0; i<(int)S.size(); i++ )
    {
        int t = min( B, S[i]/2 );
        B -= t;
        S[i] -= 2*t;
    }
    if ( accumulate(cubes.begin(),cubes.end(),0)
         < accumulate(S.begin(),S.end(),0) )
        return false;

    //  それ以外の場合は塔が作れる
    return true;
}

class SkewedPerspectives{public:
vector <string> areTheyPossible( vector <int> cubes, int B, int w, vector <string> views )
{
    vector<string> ans;
    for ( int i=0; i<(int)views.size(); i++ )
        ans.push_back( check(cubes,B,w,views[i]) ? "valid" : "invalid" );
    return ans;
}};