Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-12-21SRM491 Div1

SRM491 Div1 250 FoxMakingDice

| 22:46 | SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となく対向面の合計値でイテレートすれば解けそうな気がする

・・・と思いつつ今日は眠い・・考えがまとまらない・・・

とにかく書いてみる

うん、合計値をsumとすると、可能な組み合わせは、

(1,sum-1)、(2,sum-2)、・・・、(sum-1,1)となる

(1,sum-1)と(sum-1,1)など重複するものを除くと、可能な組み合わせは(sum-1)/2個である

(sum-1)/2個から3個選ぶ組み合わせについて、並べ方が2通りある(サンプル0から分かる)ので、

C((sum-1)/2, 3)*2が答えか

→書いた

→サンプル2以降が合わない

全然違った

そもそも(1,sum-1)から始まらないパターンがある

たとえばN=8、sum=10とかだと、(1,9)というパターンはなく、(2,8)から(8,2)までになる

つまり、Nがsum-1より小さい場合は、組み合わせ数は重複を含めてN-((sum-1)-N)になる

→書きなおす

→サンプル合わない

あれ?

なぜだ・・

・・・

あ、2箇所書きなおさないといけないのに1箇所だけ直してた。あほか・・

→直す

→サンプル合う

→提出

随分時間かかっちゃったな・・何とか600を解かねば・・・

→600へ


システムテスト

Passed


ソースコード

ll cmb(ll n, ll k) {
	ll result=1;
	ll i, k_=min(k, n-k);

	if(n<0 || n<k || k<0) return 0;
	for(i=1; i<=k_; i++) {
		result*=n-i+1;
		result/=i;
	}

	return result;
}
class FoxMakingDice {
public:
	long long theCount(int N, int K) {
		long long res=0;

		if(N<6) return 0;
		for(int sum=K; sum<=N+N-5; sum++) {
			int m=sum-1;
			if(N<sum-1) m=N-((sum-1)-N);
			if(m/2<3) continue;
			res+=cmb(m/2, 3)*2;
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101221