てきとーじゃない日記

2009-01-22

TopCoder部参加 15:07

本家が「てきとーにやるだけ」ばっかであまりにひどいので、この日記ではTopCoderとかの問題で面白かったやつを禁止ワード「てきとー」でてきとーに解説をします。

SRM 433 DivI 500 SettingTents 15:52

N*Mの平面上に、格子点を頂点とする菱形はいくつあるかという問題。

まず、菱形の短い方の対角線を伸ばすと、正方形になる。

菱形の頂点が格子点に載っていれば、伸ばした正方形の頂点も格子点に載る。

正方形の列挙はバウンディングボックスの大きさとずれでできるので、結局O(n^3)になる。

いつかのTopCoderで正方形の列挙の問題が出たので、それを思い出した結果こういう方針になった。

public int countSites(int N, int M) {
	int n = max(N, M);
	int res = 0;
	for (int w = 1; w <= n; w++) {
		for (int i = 0; i < w; i++) {
			res += max(0, (N - w + 1)) * max(0, (M - w + 1));
			for (int k = 1; k * 2 < w; k++) if ((w - 2 * i) * k % w == 0) {
				int x = max(max(i, w - i), w - k) - min(min(i, w - i), k);
				res += max(0, (N - x + 1)) * max(0, (M - w + 1));
				res += max(0, (N - w + 1)) * max(0, (M - x + 1));
			}
		}
	}
	return res;
}

イメージ図

f:id:wata_orz:20090122155027j:image