Hatena::Grouptopcoder

yuyarinのtopcoder記

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

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

2010/09/28

SRM 483 BestApproximationDiv1

| 00:55

http://www.topcoder.com/stat?c=problem_solution&rm=305892&rd=14236&pm=11023&cr=22851423

問題

与えられた数より小さい分母を持つ分数の中から,与えられた 1 より小さい小数点以下6桁の小数を最もよく近似する分数を見つける問題.

アプローチ

分母を小さい値から固定していき,分子を近似対象の小数と分母の掛け算で決定.誤差があるので分子は floor と ceil の両方を計算する.

本番では Failed System Test だった.理由は作った分数の小数表現を sprintf("%.8f") で作ったから.sprintf は指定桁数以下の値を四捨五入してしまうので小数点以下7桁目以降が 995 より大きいテストケースだと失敗する."%.10f" で失敗するケースは無かった模様.

Test Case: 138
Args: {1000, "0.812983"}
Expected: "313/385 has 6 exact digits"
Received: "526/647 has 7 exact digits"

こうした誤差を最初から出さないためには 10^6 倍して整数として計算するのがよい.問題はこの方法でも int の範囲内で計算できるように設計されているようだ.

*

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

#define For(i,a,b)    for(int i=(a);i<(b);++i)

string findFraction(int maxDen, string number)
{
	int ml = 0;
	int mn = 0;
	int md = 0;
	int num = toi(number.c_str()+2);
	
	For(d,1,maxDen+1) For(dd,0,2)
	{
		int n = num*d;
		n -= n%1000000;
		n += dd*1000000;
		int x = n/d;
		int y = 100000;
		int l = 1;
		For(i,0,6)
		{
			if(x/y!=num/y) break;
			l++;
			y /= 10;
		}
		if(l>ml)
		{
			mn = n/1000000;
			md = d;
			ml = l;
		}
	}
	
	char s[64];
	sprintf(s, "%d/%d has %d exact digits", mn, md, ml);
	
	return string(s);
}

ttvijfyomttvijfyom2011/02/27 18:44XXnJye <a href="http://idnbvnetymog.com/">idnbvnetymog</a>, [url=http://ftuabcqbiduw.com/]ftuabcqbiduw[/url], [link=http://gwxepxsaficy.com/]gwxepxsaficy[/link], http://judtzquinqwh.com/

2010/05/28

TopCoder Open 2010 Algorithm Qualification Round 3 WhatsThisChord

| 16:31

http://www.topcoder.com/stat?c=problem_statement&pm=10927&rd=14278

問題

ギターの弦を押さえる時にどのコードになるのかを求める問題.6つの弦のどのフレットを押さえるのかが数値で与えられる.特に 0 なら開放弦,-1 なら弾かない,である.どの音の Major か Minor なのかを判定する.

アプローチ

全探索でも全く問題ないが,コードが汚くなる.

とりあえず押さえる弦を配列に突っ込んで 12 の剰余を取って unique をかけて正規化する(*1).ここで要素が 3 つでなければ終了.3 つの場合,その後ろにそれぞれ 12 を足した値を追加しておくと(*2)後のコード判定がすっきりして楽になる(*3).

ソースコード

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

typedef vector<int> VI;

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

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

#define Unique(v) \
	sort((v).begin(),(v).end());\
	v.resize(unique((v).begin(),(v).end())-(v).begin());
	
int s[6] = {4,9,2,7,11,4};
string name[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};

string classify(vector<int> chord)
{
	VI c;
	Rep(i,6) if(chord[i]>=0)
		c.pb((chord[i]+s[i])%12);
	// (*1)
	Unique(c);
	
	if(sz(c)!=3)
		return "";
	
	// (*2)
	Rep(i,3)
		c.pb(c[i]+12);
	
	// (*3)
	Rep(i,3)
	{
		if(c[i+1]-c[i]==4 && c[i+2]-c[i+1]==3)
			return name[c[i]]+" Major";
		if(c[i+1]-c[i]==3 && c[i+2]-c[i+1]==4)
			return name[c[i]]+" Minor";
	}
	
	return "";
}

DiegoDiego2012/07/10 00:56The pucrahses I make are entirely based on these articles.

rcomsiercomsie2012/07/10 15:55WkGRgf <a href="http://ndjqpxpaabuy.com/">ndjqpxpaabuy</a>

lurhlpgihxdlurhlpgihxd2012/07/10 21:512sAKJD , [url=http://wyqyxabtrpox.com/]wyqyxabtrpox[/url], [link=http://fetlavsdhbsq.com/]fetlavsdhbsq[/link], http://frjyegfwmtje.com/

sxyqsmsxyqsm2012/07/12 12:11UCCj2u <a href="http://srlypizeryby.com/">srlypizeryby</a>

2010/05/23

Google Code Jam 2010 Round 1B A. File Fix-it

| 07:16

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

問題

既に存在する UNIX 形式のディレクトリパスの集合がある時に,与えられたディレクトリパスのディレクトリを作る際に,いくつのディレクトリを作らなければならないかを求める問題.

結果

small, large 共に correct.

アプローチ

本番では問題の細かい条件までちゃんと読む時間がなかったので,要点だけ押さえて,思い付くまま多分木を作ってディレクトリ構造とディレクトリの作成をシミュレートした.

large でも特に問題が大きくないので set を使ってすべてのディレクトリパスを保存しても問題なさそう.

問題の条件を読み直したら

1 1
/home/yuyarin/test
/home/yuyarin

みたいなケースも無い,つまり既存のディレクトリパスについてはその上位のディレクトリのパス(/home/yuyarin,/home)も,既存ディレクトリパスの集合に含まれているので,作るかどうかは既存ディレクトリパスの集合にパスの文字列が有るか無いかだけで判定できる.

作るべきディレクトリに対しては上位ディレクトリを求めていって,それが集合に無ければ追加してカウントを増やせばいい.

ソースコード

初めから書き直したので,提出時とアルゴリズムが違う

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

typedef vector<string> VS;

#define Forall(i,v)   for(int i=0;i<(int)v.size();++i)
#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)
#define sz(a) int((a).size())

// using boost C++ library Version 1.41>=
// http://www.boost.org/
#include <boost/algorithm/string.hpp>

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int N, M;
		cin >> N >> M;
		VS ve(N);
		VS vc(M);
		set<string> sp;
		Rep(n,N)
		{
			cin >> ve[n];
			sp.insert(ve[n]);
		}
		int r = 0;
		Rep(m,M)
		{
			cin >> vc[m];
			VS vs;
			boost::algorithm::split(vs, vc[m], boost::is_any_of("/"));
			string s = "";
			For(i,1,sz(vs))
			{
				s = s + "/" + vs[i];
				if(sp.insert(s).second)
					r++;
			}
		}
		cout << "Case #" << t+1 << ": " << r << 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;
}

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/

2010/03/20

SRM 464 ColorfulStrings

| 21:19

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

Sample Case: passed

System Test: passed

問題の条件から

  • 2桁以上の数字では0と1が入ってはいけない
  • 同じ数字は2回現れない

ということがわかるので 2<=n<=8 で考えればいいことがわかるので,ひとまず枝刈りをせずに 2,3,4,5,6,7,8,9 を辞書順で生成していき colorful かチェックする.結果的に枝刈りをしなくても実行速度は十分であった.

数字は整数の配列 num[] で各桁を表現する.

辞書順の生成は再帰を使う (rec()).ある数字が使われたかを ap[] で記録しておき,使われていない数字を小さい方から num[pos] に入れていく.pos を 1 増やして再帰する.長さが桁数に達したら colorful かチェックを行う (colorful()).

colorful のチェックではそれまでの数字の積を記録 (mr[]) しておけば,ループを1重減らすことができる.

積のデータベースには set を利用している.insert() は既に要素があったときに .second で false が返されるので,既に積が出現している=colorful ではない場合を挿入と同時に判定できる.

あんまりスマートなコードだとは思わないけど,理解はしやすいと思う.

上位のコードはもっとシンプルだけどまだ解読出来ていない...

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>

using namespace std;
inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

class ColorfulStrings
{
public:

bool colorful(int n, int* num)
{
	// the results of mul
	int mr[] = {1,1,1,1,1,1,1,1,1,1,};
	
	set<int> m;
	
	for(int len=1; len<=n; ++len)
	{
		for(int idx=0; idx<=n-len; ++idx)
		{
			mr[idx] *= num[idx+len-1];
			if(!m.insert(mr[idx]).second)
				return false;
		}
	}
	
	return true;
}

bool rec(int n, int k, int* num, int* ap, int pos, int &cnt)
{
	if(pos==n)
	{
		if(colorful(n, num)) cnt++;
		if(cnt==k) return true;
		return false;
	}
	
	for(int i=2; i<10; ++i)
	{
		if(ap[i]) continue;
		num[pos] = i;
		ap[i] = 1;
		if(rec(n, k, num, ap, pos+1, cnt)) return true;
		ap[i] = 0;
	}
	return false;
}

string getKth(int n, int k)
{
	if(n>8) return "";
	if(n==1) return (k>10) ? "" : tos(k-1);
	
	string s = "";
	int num[8];
	int ap[] = {0,0,0,0,0,0,0,0,0,0};
	int cnt = 0;
	
	if(rec(n, k, num, ap, 0, cnt))
	{
		for(int i=0; i<n; ++i) s += num[i]+'0';
	}
	return s;
}
	
	
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/