WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};