TopCoder SRM 559 Div1 Easy HyperKnight

続いてDiv1 Easy。これはDiv2 Mediumと同じ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12201

チェスのナイトの移動距離が通常より大きい場合、ナイトがN箇所に動けるマス目の数を求める。
最初DPとか場合分けで数を絞ろうかと思ったけど、しばらく考えていて結局以下のような配置になることがわかった。
http://apps.topcoder.com/wiki/display/tc/SRM+559:Editorialの図の方が見やすいかな。

<-b->
<a>
222334433222
222334433222
222334433222
333446644333
333446644333
444668866444
333446644333
333446644333
222334433222
222334433222
222334433222

よって、行数Rと列数Cを用いて以下のように書ける。

• N=2となるマスは(4a^2)個
• N=3となるマスは(8a(b-a) )個
• N=4となるマスは(4(b-a)^2 + 2a*( (R-2b)+(C-2b) )個
• N=6となるマスは(2(b-a)*((R-2b)+(C-2b) ) )個
• N=8となるマスは(R-2b)*(C-2b)個
• それ以外は0個

class HyperKnight {
	public:
	long long res[9];
	long long countCells(int a, int b, int numRows, int numColumns, int k) {
		ll NR=min(numRows,numColumns);
		ll NC=max(numRows,numColumns);
		ll ma=min(a,b);
		ll mb=max(a,b);
		ll x,y;
		ZERO(res);
		
		res[8]=(NR-(2*mb))*(NC-(2*mb));
		res[6]=(NR-(2*mb))*2*(mb-ma) + (NC-(2*mb))*2*(mb-ma);
		res[4]=(NR-(2*mb))*2*ma + (NC-(2*mb))*2*ma;
		res[4]+=(mb-ma)*(mb-ma)*4;
		res[3]=ma*(mb-ma)*8;
		res[2]=ma*ma*4;
		
		return res[k];
	}
};

まとめ

頭で考えるより、さっさと図を描いた方がわかりやすい問題。