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点)。もし本番ならば間違いなく解く前にタイムアップだっただろう。問題も分かりやすくて読むのに時間をとられなかったし、完成したプログラムを見てみると構造も単純なのに。