SRM 146 DIV2 500

問題を読む為の英単語

単語	意味
rectangular	長方形の

問題概要

入力：width, height
出力：長方形の個数

以下のような四角形が与えられる。

 __ __ __
|__|__|__|
|__|__|__|
|__|__|__|

(width:3 height:3)

与えられた四角形に存在する長方形の数を出力せよ。
ただし、正方形は除外すること。

例示

width:3 height:3
return 22

回答案

すべての長方形パターンの数を合計する。

3x3の長方形では。。。
W:入力width H:入力heightとし、例示より以下のパターンが導かれる。

width	height	個数
1	2	6
1	3	3
2	1	6
2	3	2
3	1	3
3	2	2

widthとheightから個数を得る一般式
(W - width + 1) * ( H - h + 1)

回答コード(C#)

class RectangularGrid
	{
		public long countRectangles(int width, int height)
		{
			long rect_num = 0;

			for (int i = 1; i <= height; i++) {
				for (int j = 1; j <= width; j++) {
					if (i != j)
						rect_num += (width - j + 1) * (height - i + 1);
				}
			}

			return rect_num;
		}
	}