Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/23

Google Code Jam 2010 Round 1B C. Your Rank is Pure

| 04:38

http://code.google.com/codejam/contest/dashboard?c=635101#s=p2&a=0

問題

正数の集合 S の中においてある数 n が pure である条件がある.n が S の中で r 番目の数であるとき n のランクは r であると言う.n のランクが r1 であり,数 r1 のランクが r2 であり,,,としていき最後に 1 にたどり着けば n は pure であると言う.

与えられた n について, S = {x|x∈[2,n]} の部分集合 S' において n が pure であるような S' の作り方の個数を求める.

結果

small は correct だったけど提出するコードを間違えた.

large は答えを出したけど,提出がギリギリで駄目だったけど,admin に問い合せろとエラーが出た.

なので問い合わせ中.

→提出は + 0.674 秒遅かったらしい.そう計測された以上 reject とのこと.正しいソースコードの再アップロードと,エラーの理由はスルーされた.

large-practice では正解を出せていた.

アプローチ

数字 n がランク r として出現するときの場合の数を求める.

DP でも解けるけど DP にせずに再帰とキャッシュ(*1)を使った.

r〜n の間に m 個(m∈[0,r-2]) の数字が入る場合(*2)の数は Combination(n-r-1,m) で(*3),1〜r の間に数字が入る場合の数は数字 r がランク r-m-1 で現れる場合の数なのでこの関数の再帰で求められる.これらを掛け合せたものが,数字 n がランク r として出現するときの場合の数である(*4).

この関数を入力 n に対して,数字 n がランク r∈[1,n] として出現するときの場合の数の合計を計算してあげれば良い(*5).

Combination を求める部分で Integer Overflow を起こしそうな気配なので,gmpxx にお世話になった.

ソースコード

提出コードから掲載コードへの変更点

  • キャッシュ部分をマクロ化.
  • include 順序の整列,改行の追加削除等,表示を見やすくするもの
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <iostream>

// using The GNU Multiple Precision Arithmetic Library
// http://gmplib.org/
// compile with -lgmpxx -lgmp
#include <gmpxx.h>

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())

#define make_cache(...) map< __VA_ARGS__ > cache;\
map< __VA_ARGS__ >::iterator cache_it;
#define cache_hit(query_) (cache_it=cache.find(query_))!=cache.end()
#define check_cache(query_) if(cache_hit(query_)) return (*cache_it).second;
#define store_cache(key_,value_) cache.insert(mp(key_,value_))

make_cache(pair<int,int>,mpz_class)

mpz_class func(int n, int r)
{
	if(r==1) return 1;
	
	// *1
	check_cache(mp(n,r));
	
	int N = n-r-1;
	int M = r-2;
	mpz_class ans = 0;
	
	// *2
	for(int m=0; m<=M; m++)
	{
		if(N<m) continue;
		mpz_class p=1;
		// Combination(N,m) *3
		for(int j=0; j<=m-1; j++)
			p *= (N-j);
		for(int j=2; j<=m; j++)
			p /= j;
		// *4
		ans += p*func(r, M-m+1);
	}
	
	// *1
	store_cache(mp(n,r),ans);
	
	return ans;
}

int solve(int n)
{
	mpz_class ans = 0;
	// *5
	for(int i=1; i<n; i++)
		ans += func(n, i);
	ans %= 100003;
	return ans.get_si();
}

int main(int argc, char* argv[])
{
	uint T;
	cin >> T;
	
	for(uint t=0;t<T;t++)
	{
		uint n;
		cin >> n;
		cout << "Case #" << t+1 << ": " << solve(n) << endl;
	}
	
	return 0;
}

AndiAndi2011/07/22 15:08Thanks alot - your answer solved all my problems after several days srtuglging

ymztwdpymztwdp2011/07/26 00:50iMKSlH , [url=http://vxqonjgohmzr.com/]vxqonjgohmzr[/url], [link=http://bdghiksyjeoz.com/]bdghiksyjeoz[/link], http://fqpjpgeffbmu.com/

EgwoloEgwolo2013/02/16 23:19Thanks for contributing. It's helepd me understand the issues.

zzokgazzokga2013/02/19 14:25gNeh7s <a href="http://jdxldqxslfbx.com/">jdxldqxslfbx</a>

ealpalshhtealpalshht2013/02/19 14:25ftpxVI <a href="http://cpdedlynamuf.com/">cpdedlynamuf</a>

2010/05/10

Google Code Jam 2010 Qual B. Fair Warning

| 11:48

http://code.google.com/codejam/contest/dashboard?c=433101#s=p1

C++ で多倍長整数演算ができなかったので,本番では泣きながら Ruby で書いた.RubyC++ を行ったり来たりすると文法ミスが多発する...error: expected `;' before ... みたいな.

TopCoder では多分使えないけど,今後のことを考えて gmpxx で練習してみた.

※掲載しているコードは手直ししたものです.

#include <iostream>
#include <vector>
#include <gmpxx.h>

using namespace std;

mpz_class gcd(mpz_class& l, mpz_class &r)
{
	mpz_class a;
	mpz_gcd(a.get_mpz_t(), l.get_mpz_t(), r.get_mpz_t());
	return a;
}

int main(int argc, char* argv[])
{
	unsigned int C;
	cin >> C;
	
	for(unsigned int i=0;i<C;i++)
	{
		unsigned int N;
		cin >> N;
		vector<mpz_class> v(N);
		vector<mpz_class> d(N-1);
		for(unsigned int j=0;j<N;j++)
		{
			cin >> v[j];
		}
		sort(v.begin(), v.end());
		for(unsigned int j=0;j<N-1;j++)
		{
			d[j] = v[j+1]-v[j];
		}
		mpz_class g = d[0];
		for(unsigned int j=1;j<N-1;j++)
		{
			g = gcd(g, d[j]);
		}
		mpz_class m = v[0] % g;
		mpz_class r = (m==0) ? mpz_class(0) : g-m;
		cout << "Case #" << i+1 << ": " << r << endl;
	}
	
	return 0;
}

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

忍者最終号忍者最終号2010/05/13 00:53cin, cout使うな.

yuyarinyuyarin2010/05/13 04:17>忍者最終号さん
それはどういった理由からでしょうか?

exsexfexsexf2011/02/28 12:15RFRU9x <a href="http://kstxagthgxsq.com/">kstxagthgxsq</a>, [url=http://hoakvztpgsoj.com/]hoakvztpgsoj[/url], [link=http://liulzkniffql.com/]liulzkniffql[/link], http://gfaelupssudw.com/