kmjp's blog

競技プログラミング参加記です

TopCoder SRM 564 Div2 Hard KnightCircuit

SRM564、Div2 Hardが1050ptということで見てみた。
http://community.topcoder.com/stat?c=problem_statement&pm=10966

Div2 HardがDiv1 Easyのアレンジという珍しいパターン。
残念なことにまともに解く前にEditorialを見てしまったのだけどね…。

Div1 Easyはチェスのナイトの動きをした場合、最大で動けるマス数を答える問題だったけど、こちらは以前のSRM559 HyperKnightのように動ける範囲が一般化されている。

まず、aとbの最大公約数が1より大きいなら、今いるマスからその公約数以内のマスには止まれないので、フィールドサイズおよび移動マス数を公約数で割ってaとbが互いに素にしておく。

ここで、フィールドの幅も高さもaまたはbの倍+1以上あるなら、Editorialにある通り、今いるマスから横または縦に2aまたは2bだけ動くということができる。

まず、フィールドの幅・高さが2a+1または2b+1より多い場合を考える。
拡張ユークリッドの互除法より、aとbが素ならap+bq=1となるpとqがあるので、何回か動くと縦または横に1マスだけ動くことができる。
ただ、aとbの和が偶数の場合はpとqの偶奇がいっしょとなり、最終的に止まれるマスはX座標+Y座標が偶奇一致する点、つまりフィールドの半分になる。
aとbの和が奇数ならフィールドの全マスに止まれる。

フィールドが2a+1または2b+1より小さい場合、フィールドサイズはせいぜい20*100000なので愚直に探索しても間に合う。

ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}
int vis[21][100001];

class KnightCircuit {
	public:
	
	long dfs(int W,int H,int a,int b) {
		int dx[8]={a,-a,a,-a,b,-b,b,-b};
		int dy[8]={b,b,-b,-b,a,a,-a,-a};
		int x,y,i;
		long res=0;
		ZERO(vis);
		FOR(y,H) FOR(x,W) if(vis[x][y]==0) {
			long num=1;
			queue<int> dfs;
			dfs.push(y*100+x);
			vis[x][y]=1;
			while(!dfs.empty()) {
				int key=dfs.front();
				dfs.pop();
				int sx=key%100,sy=key/100;
				FOR(i,8) {
					int tx=sx+dx[i];
					int ty=sy+dy[i];
					if(tx>=0 && tx<W && ty>=0 && ty<H && vis[tx][ty]==0) {
						vis[tx][ty]=1;
						num++;
						dfs.push(ty*100+tx);
					}
				}
				
			}
			res = max(res,num);
		}
		return res;
	}
	
	long long maxSize(int w, int h, int a, int b) {
		int g=gcd(a,b);
		if(g>1){ w=(w+(g-1))/g; h=(h+(g-1))/g; a/=g; b/=g;}
		if(w>h) swap(w,h), swap(a,b);
		
		if(w<=max(a,b)*2) return dfs(w,h,a,b);
		if((a+b)%2) return w*(ll)h;
		else return (1+w*(ll)h)/2;
	}

};

まとめ

アルゴリズムやコード自体は単純だけど、気づくまでが面白い問題。
それだけに先にEditorial見ちゃったのはしまったな…。