SRM 559 div1 easy HyperKnight
問題
TopCoder Statistics - Problem Statement
チェスのナイトのようなものを考える。チェスのナイトは今いる位置から (+1, +2), (+1, -2), (-1, +2), (-1, -2), (+2, +1), (+2, -1), (-2, +1), (-2, -1) と動くことができるが, 今回のナイトは (+a, +2), (+a, -2), (-a, +b), (-a, -b), (+b, +a), (+b, -a), (-b, +a), (-b, -a) に動くことができる。
このナイトを R*C の大きさのグリッドのどこかに置く。すると, ナイトが外に出ないようにするための動かし方は何通りか考えられるが, この動かし方が k 通りであるようなナイトの置き方は何通りあるか。
解法
真ん中に書いてある図が解法の肝です。
maxi = max(a, b), mini = min(a, b) とします。すると, 各区画に分かれて, ナイトの動かし方が決まります。
class HyperKnight { public: long long countCells(int a, int b, int numRows, int numColumns, int k) { ll ans = 0; ll mini = min(a, b); ll maxi = max(a, b); ll nr = numRows, nc = numColumns; switch(k) { case 2: ans = 4*mini*mini; break; case 3: ans = 8*mini*(maxi-mini); break; case 4: ans = 2*(nr-2*maxi) * mini + 2*(nc-2*maxi) * mini; ans += 4*(maxi-mini) * (maxi-mini); break; case 6: ans = (maxi-mini) * (2*(nr-2*maxi) + 2*(nc-2*maxi)); break; case 8: ans = (nr-2*maxi) * (nc-2*maxi); break; } return ans; } };