SRM564 Div2 Hard "KnightCircuit"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10966
訳
(a, b)-ナイトとは普通のチェスのナイトのようにジャンプして動く
チェスの駒であるが、ジャンプ力は一方向へa、もう一方向へbとなっている。
正式には、(a, b)-ナイトがマス(x, y)にあるとすると、次の8個のマスへ移動できる。
(x+a, y+b), (x+a, y-b), (x-a, y+b), (x-a, y-b),
(x+b, y+a), (x+b, y-a), (x-b, y+a), (x-b, y-a)
当然(a, b)-ナイトがボードの角にあったときなど、
上記のうちいくつかのマスはボードからはみ出している可能性がある。
そのようなマスへはジャンプする事はできない。
knight-circuit(ナイトの回路) とはスタートとゴールが同じマスの
チェスボードのマスの配列である。
knight-circuitの隣り合うマスは(a, b)-ナイトが一回のジャンプで
移動できるものでなくてはならない。
knight-circuitは各セルを好きな回数、訪れてもよい。
knight-circuitのサイズとは、そこに含まれる異なるセルの数である。
あなたは長方形のチェスボードの幅wと高さhが与えられる。
また、(a, b)-ナイトのa, bも与えられる。
与えられたボードから得られる、knight-circuitのサイズの最大値を返せ。
knight-circuitのスタートのマスは自由に選べるものとする。
制約
1 <= w, h <= 10^5
1 <= a, b <= 10
a != b
Editorialsを見て・・・
やっと解けた・・ああ無隋
SRM564 Editorial
a, bが両方とも奇数だといける所が制限される!!
(x, y) -> (x+a, y+b)と移動したとします。
もしx + yが偶数ならば、x+a + y+bもまた偶数となります。
もしx + yが奇数ならば、x+a + y+bもまた奇数となります。
なので、x + yが偶数のマスからx + yが奇数のセルへ移動する事は不可能です。
これはちょうど、普通のチェスボードの白黒マスのように
移動が制限されるということです。
ソースコード
bool chk[105][100005]; class KnightCircuit { public: int gcd( int a, int b ){ if( a < b ) swap( a, b ); if( a % b == 0 ) return b; return gcd( b, a % b ); } long long solve( int x, int y, int w, int h, int a, int b ){ int dx[] = { a, a, -a, -a, b, b, -b, -b }; int dy[] = { b, -b, b, -b, a, -a, a, -a }; int res = 0; queue< pair<int, int> > que; que.push( make_pair( x, y ) ); chk[y][x] = true; while( !que.empty() ){ res++; int x = que.front().first; int y = que.front().second; que.pop(); for( int d = 0; d < 8; d++ ){ int nx = x + dx[d]; int ny = y + dy[d]; if( nx < 0 || w <= nx || ny < 0 || h <= ny || chk[ny][nx] ) continue; chk[ny][nx] = true; que.push( make_pair( nx, ny ) ); } } return res; } long long maxSize(int w, int h, int a, int b){ if( w < h ) swap( w, h ); // hをちっちゃく long long res = 0; if( w < 100 || h < 100 ){ // 範囲が小さいので、BFSで求める memset( chk, false, sizeof(chk) ); for( int sx = 0; sx < w; sx++ ){ for( int sy = 0; sy < h; sy++ ){ if( chk[sy][sx] ) continue; long long t = solve( sx, sy, w, h, a, b ); if( t > res ) res = max( res, t ); } } }else{ // 範囲は大きいが、自由に移動可能 int e = gcd( a, b ); w = w / e + (w % e ? 1 : 0); h = h / e + (h % e ? 1 : 0); a /= e; b /= e; if( (a % 2 == 1) && (b % 2 == 1) ){ int rem = h / 2 + (h % 2 ? 1 : 0); rem = (w % 2 ? rem : 0); res = (long long)h * (w / 2) + rem; }else{ res = (long long)w * h; } } return res; } };