SRM564 Div2 Hard(1050) KnightCircuit

KnightCircuit

本番中には誰も解けなかった問題。

要は、あるマスから到達可能な最大のマス数を返せば良い。盤面が小さいときと大きいときに分けて考える。

盤面が小さいときは、実際に探索する。(0,0)から到達可能なマスに0を書き込み、0が書かれなかったマスから1個を選んでそのマスから到達可能なマスに1を書き込み、……として、最も多い数字を数えればO(wh)で計算できる。

盤面が大きい場合、d=gcd(a,b)として、座標がdの整数倍でないところには移動できない。縦横に2aと2b動くことができるから、縦横に2d動くことは常に可能。dが最大公約数だから、x,yを整数として、(a,b)=(2xd,2yd)と表せることはない。(a,b)=((2x+1)d,(2y+1)d)ならば、((2x+1)d,2yd)や(2xd,(2y+1)d)には移動できない。(a,b)=((2x+1)d,2yd)もしくは(a,b)=(2xd,(2y+1)d)ならば、縦横にd移動することが可能なので、dの整数倍の任意の位置に移動できる。

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

int gcd(int a,int b){int t;if(a>b)t=a,a=b,b=t;while(a)t=a,a=b%a,b=t;return b;}

class KnightCircuit{public:
long long maxSize( int w, int h, int a, int b )
{
    long long ans = 0;

    if ( w<128 || h<128 )
    {
        int dx[] = { -a, -a, a, a, -b, -b, b, b };
        int dy[] = { b, -b, b, -b, a, -a, a, -a };

        vector<vector<int> > B(h,vector<int>(w,-1));
        
        int f = 0;

        for ( int oy=0; oy<h; oy++ )
        for ( int ox=0; ox<w; ox++ )
        if ( B[oy][ox]==-1 )
        {
            vector<int> vx, vy;
            B[oy][ox] = f;
            vx.push_back(ox);
            vy.push_back(oy);
            for ( int p=0; p<(int)vx.size(); p++ )
            {
                for ( int d=0; d<8; d++ )
                {
                    int x = vx[p]+dx[d];
                    int y = vy[p]+dy[d];
                    if ( 0<=x && x<w &&
                         0<=y && y<h &&
                         B[y][x]==-1 )
                    {
                        B[y][x] = f;
                        vx.push_back(x);
                        vy.push_back(y);
                    }
                }
            }
            f++;
        }

        vector<int> C(f);
        for ( int y=0; y<h; y++ )
        for ( int x=0; x<w; x++ )
            C[B[y][x]]++;

        return *max_element(C.begin(),C.end());
    }
    else
    {
        int d = gcd(a,b);
        long long t = (long long)((w+d-1)/d)*((h+d-1)/d);
        if ( (a/d+b/d)%2==1 )
            return t;
        else
            return (t+1)/2;
    }

    return ans;
}};