Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/10

Google Code Jam 2010 Qual A. Snapper Chain

| 11:48

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

問題を理解するのに時間がかかった上に1回勘違いしてミスした.気づいたら凄く簡単...

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

#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
	unsigned int T, N, K;
	cin >> T;
	for(unsigned int i=0;i<T;i++)
	{
		cin >> N >> K;
		cout << "Case #" << i+1 << ": " << (((K+1)%(1u<<N)==0)?"ON":"OFF") << endl;
	}
	
	return 0;
}

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;
}

Google Code Jam 2010 Qual C. Theme Park

| 11:48

large では答えが 32bit で収まらないことに気付かず提出してしまった.本番では int を使っていたので負の値が出力されていたのだけど,時間を急いでしまって確認しなかった.もったいない.

本番ではやらなかったループ検出機能を追加.凄く速くなった.

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

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main(int argc, char* argv[])
{
	unsigned int T;
	cin >> T;
	
	for(unsigned int t=0;t<T;t++)
	{
		unsigned int R, k, N;
		cin >> R >> k >> N;
		
		vector<unsigned int> g(N);
		for(unsigned int j=0;j<N;j++)
		{
			cin >> g[j];
		}
		
		vector<unsigned int> nv(N), cv(N);
		for(unsigned int j=0;j<N;j++)
		{
			unsigned int i = j;
			unsigned int c = g[i];
			i = (i+1)%N;
			while(c+g[i]<=k&&i!=j)
			{
				c += g[i];
				i = (i+1)%N;
			}
			nv[j] = i;
			cv[j] = c;
		}
		
		unsigned int idx = 0;
		unsigned long long euro = 0;
		map<unsigned int, pair<unsigned int, unsigned long long> > m;
		bool loop_detect = false;
		for(unsigned int r=0;r<R;r++)
		{
			if(loop_detect==false && m.insert(make_pair(idx, make_pair(r,euro))).second==false)
			{
				pair<unsigned int, unsigned long long> p = m.find(idx)->second;
				unsigned int repeat = ((R-p.first)/(r-p.first));
				euro += (euro-p.second)*(repeat-1);
				r += (repeat-1)*(r-p.first);
				if(r>=R) break;
				loop_detect = true;
			}
			euro += cv[idx];
			idx = nv[idx];
		}
		
		cout << "Case #" << t+1 << ": " << euro << 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/