Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-13[過去問]Member SRM458(DIV2)

SRM458 div2 第三問(950点)

| SRM458 div2 第三問(950点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM458 div2 第三問(950点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10698

ある範囲を動く整数x、y、zが与えられるとき、

x × y = z を満たす場合の数を求める問題。

問題はシンプルだが、x、y、zがそれぞれ 1 ~ 1,000,000,000 で動くため、高速化が鍵となる。


思いつく限りの高速化を施したのがこちら。

import java.util.HashSet;

public class ProductTriplet {
	public long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz) {
		long answers = 0;
		HashSet set = new HashSet();
		int finished = 1;

		for (int i = minz ; i <= maxz ; i++) {
			for (int j = finished ; j <= i ; j++) {
				if (set.contains(j)) {
					continue;
				}
				if (i % j == 0) {
					int k = i / j;
					if (minx <= i && miny <= k && k <= maxy ) {
						answers += (maxz - i) / j + 1;
					}
					set.add(j);
				}
			}
			finished++;
		}
		return answers;
	}
}

ある数 i について割り切れる数 x を見つけたら、

それ以降の数 (i + nx) についてもカウントしてしまおうという作戦。

だが i が大きくなってしまうと割れる数を探すのに時間がかかってしまう、

という問題があり、最後のテストケースには通らず。

別のアプローチを思いついたので後日試します。