読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

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 通りであるようなナイトの置き方は何通りあるか。

解法

f:id:mayokoex:20160713001113j:plain
真ん中に書いてある図が解法の肝です。

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