SRM559 Div2 Medium HyperKnight
問題
ハイパーナイトの動きを表す2つの整数a,bが与えられる。
ハイパーナイトは
(a,b) (b,a) (a,-b) (b,-a)
(-a,b) (-b,a) (-a,-b) (-b,-a)
の八箇所に動ける。
a=1, b=2だったら普通のナイトの動きになる。
マス目の数がR*Cのチェスボードがある。
このボード上で、ハイパーナイトがK(0<=K<=8)箇所だけ動けるような
マス目の数はいくつあるかを返せ。
制約
1 <= a,b <= 10^9
a != b
1 <= R,C <= 10^9
2 * max(a,b) < min(R,C)
ACしてるコードを見ると・・・
2 * max(a,b) < min(R,C)という制約があるので、
各マス目のハイパーナイトが移動できる箇所は下記のようになる
2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |
3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |
2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |
あとはそれぞれのKのマス目が何個出来るか計算する
例えばK=2だったら四隅の2の部分のマス目が何個できるのか
計算すればよい。
実はK=0,1,5,7のマス目なんて存在しなかったのだ・・・
よく考えたらK=5,7なんてありえないよ・・・
マス目はintで計算すると簡単にオーバーフローするので注意する。
ソースコード
typedef long long ll; class HyperKnight { public: long long countCells(int _a, int _b, int numRows, int numColumns, int k){ ll R = numRows; ll C = numColumns; ll a = _a; ll b = _b; if( a > b ) swap( a, b ); ll res[9] = {0}; res[2] = a * a * 4; res[3] = (b - a) * a * 8; res[4] = (C - 2 * b) * a * 2 + (R - 2 * b) * a * 2 + (b - a) * (b - a) * 4; res[6] = (C - 2 * b) * (b - a) * 2 + (R - 2 * b) * (b - a) * 2; res[8] = (C - 2 * b) * (R - 2 * b); return res[k]; } };