Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-11-15SRM523 Div1(Practice)

SRM523 Div1 250 CountingSeries

| 02:29 | SRM523 Div1 250 CountingSeries - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM523 Div1 250 CountingSeries - SRM diary(Sigmar) SRM523 Div1 250 CountingSeries - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

等差数列については割り算で個数を求める

等比数列についてはイテレーションで個数を求める

等比数列をイテレーションする際に、等差数列に含まれるものを除いていけばOK

意外と等差数列を数えるときに、upperBound<aのときの処理を忘れている人が多かったようで、非常に正答率が低かった。

サンプルを信じすぎないことが大事だと思う。


ソースコード

class CountingSeries {
public:
	long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
		long long res;

		if(upperBound<a) res=0;
		else res=(upperBound-a+b)/b;
		while(c<=upperBound) {
			if(c<a || (c-a)%b!=0) res++;
			c*=d;
			if(d==1) break;
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111115