Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-05-02

RectangularGrid

| 18:11

問題文

436.45->498.51 / 500

widht×height のグリッドに含まれる長方形(ただし正方形は除外)の数を求めよ、という問題。解法はすぐに思いついた。

class RectangularGrid {
public:
    long long countRectangles(int width, int height) {
        long long rectangles = 0;
        for (int w = 1; w <= width; w++) {
            for (int h = 1; h <= height; h++) {
                if (w == h) continue;
                rectangles += (width-w+1) * (height-h+1);
            }
        }
        return rectangles;
    }
};