TopCoder SRM146 DIV2 500点問題

　TopCoderの上位陣の人たちの成績を見ていると「継続は力なり」という言葉が頭をよぎる。
　SRMを重ねるごとに成績が上がっているからだ。

　俺も今以上に勉強を重ねなければならないと、あらためて感じさせられた。
　ということでこの前から悩んでいたTopCoderの問題が解けたので貼ってみる。
　DIV2の500点問題が解けたのはこれが始めてになる。

#include <iostream>
using namespace std;

class RectangularGrid {
public:
	long long count(int width, int height, int i, int j) {
		long long sum = 0;
	
		int cnt = width - i;
		int mul = height - j;
		
		sum = (cnt+1) * (mul+1);
		
		cnt = width - j;
		mul = height - i;
		
		if(cnt < 0 || mul < 0) return sum;
		sum += (cnt+1) * (mul+1);
		return sum;
	}
	
	long long countRectangles(int width, int height) {
		long long ans = 0;
		bool b = (width > height);
		
		for(int i = 1; i <= width; i++) {
			for(int j = 1; j <= height; j++) {
				if(i == j) continue;
				if(b && i < j) continue;
				else if(!b && j < i) continue;
				
				ans += count(width, height, i, j);
				
			}
		}
		
		return ans;
	}
};

　解くのに時間かかりすぎのためもらえた点数は150.02点（おそらく最低点が150点）。もし本番ならば間違いなく解く前にタイムアップだっただろう。問題も分かりやすくて読むのに時間をとられなかったし、完成したプログラムを見てみると構造も単純なのに。

　こんな感じで１日１問TopCoderの問題を解いていこう。それとアルゴリズムの勉強もあらためてちゃんとしよう。