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見ちゃったのはしまったな…。