SRM542 Div1 Easy(250), Div2 Medium(500) PatrolRoute

TopCoder

PatrolRoute

x軸方向で最小の点と最大の点の差をwとすると、x軸方向の移動距離は2wで、各点のx座標の選び方は(w-1)*(X-w)通り。y軸方向も同様。各点のx軸方向の位置とy軸方向の位置を決めると、その組み合わせは6通り。

class PatrolRoute{public:
int countRoutes( int X, int Y, int minT, int maxT )
{
    long long ans = 0;
    long long M = 1000000007;

    for ( long long w=2; w<X; w++ )
    for ( long long h=2; h<Y; h++ )
    if ( minT<=2*w+2*h && 2*w+2*h<=maxT )
    {
        ans += (w-1)*(X-w)*(Y-h)*(h-1)*6;
        ans %= M;
    }

    return (int)ans;
}};