SRM564 Div2 Hard(1050) 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; }};