Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/05/10

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/