Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-12-09SRM490 Div1

SRM490 Div1 250 Starport

| 01:48 | SRM490 Div1 250 Starport - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM490 Div1 250 Starport - SRM diary(Sigmar) SRM490 Div1 250 Starport - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

任意のkに対してk*M%NはGCD(N,M)の倍数にしかならないことを経験則で知っていたので見た瞬間解法が分かった

つまり、g=GCD(N,M)とすると、0,g,2*g,3*g,...,N-gの平均が答えだ。

等差数列の和を要素数で割れば良い。

→書く

→サンプル合わない

計算ミスしてた

→直す

ふむ。。。そうか、等差数列の平均値だから、(最小値+最大値)/2でいいんだ。

→サンプル合う

→提出

あれ・・ほとんど誰も出してない

大丈夫だよな・・

N<Mのパターンとか色々試す

やっぱり問題なさそう

→500へ


チャレンジフェーズ

ややこしい数式書いている人が多いなあ

怪しいが合ってるかよく分からない。

突込みどころなし・・・


システムテスト

Passed


ソースコード

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

class Starport {
public:
	double getExpectedTime(int N, int M) {
		double res;

		double g=gcd(N, M);
		double sum=N-g;
		res=sum/2;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101209