SRM507 Div2 Hard(1000) CubeRoll

CubeRoll

スタートとゴールの間に穴があったら到達不可能。

スタート・ゴールの両側に穴があったら、立方体の移動範囲は狭いので、動的計画法。

それ以外の場合はスタートとゴールの距離に着目する。距離が平方数なら１手。距離が平方数の和なら２手。距離が平方数の差なら２手。平方数の差は、2x+1, 4x+4, ……, 2kx+k²の形で表される。ただしxは任意の正数。任意の奇数は平方数の差（2x+1）で表せる。2x+1で移動して1移動すれば任意の偶数の距離を移動できるので、３手あれば充分。

#include <vector>
using namespace std;

class CubeRoll{public:
int getMinimumSteps( int initPos, int goalPos, vector <int> holePos )
{
    //  スタートとゴールの間に穴があったら無理
    for ( int i=0; i<(int)holePos.size(); i++ )
        if ( initPos<holePos[i] && holePos[i]<goalPos  ||
             goalPos<holePos[i] && holePos[i]<initPos )
            return -1;

    //  スタート・ゴールの両側に穴があったら動的計画法
    int HL = 0;
    int HR = 100001;
    for ( int i=0; i<(int)holePos.size(); i++ )
    {
        if ( holePos[i]<initPos && holePos[i]<goalPos )
            HL = max( HL, holePos[i] );
        if ( initPos<holePos[i] && goalPos<holePos[i] )
            HR = min( HR, holePos[i] );
    }

    if ( 0<HL && HR<100001 )
    {
        vector<int> T(HR,-1);
        T[initPos] = 0;
        bool up = true;
        for ( int t=0; up; t++ )
        {
            up = false;
            for ( int i=HL+1; i<=HR-1; i++ )
            if ( T[i] == t )
            {
                for ( int p=1; i+p*p<HR; p++ )
                    if ( T[i+p*p] == -1 )
                        T[i+p*p] = t+1,  up = true;
                for ( int p=1; HL<i-p*p; p++ )
                    if ( T[i-p*p] == -1 )
                        T[i-p*p] = t+1,  up = true;
            }
        }
        return T[goalPos];
    }

    int D = abs(initPos-goalPos);

    //  スタートとゴールの距離が平方数なら1
    for ( int i=1; i*i<=D; i++ )
        if ( i*i == D )
            return 1;

    //  平方数の和で表せるなら2
    for ( int i=1; i*i<=D; i++ )
        for ( int j=i; i*i+j*j<=D; j++ )
            if ( i*i+j*j == D )
                return 2;

    //  平方数の差で表せるなら2
    for ( int i=1; i*i<=D; i++ )
        if ( (D-i*i)%(2*i) == 0 )
            return 2;

    //  それ以外は3
    return 3; 
}};