Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-04-01TCO2012 Round1A

  • 250:225.46(+100), 500:423.12(+50), 1000:598.70, score:1397.28, rank:4, rating:2224(+160)
  • なぜか高順位+TCOご祝儀相場でボロ儲けw

TCO2012 Round1A 250 EllysJuice

| 16:30 | TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

予選にしては問題めんどくさああ

制約が小さいのでnext_permutationでナイーブにシミュレーションした

シミュレーションを省略するとよく間違えるので、本当にナイーブにシミュレーションした

提出

書くの遅っ と思ったら誰も出してなかった

みんな同様に律儀にシミュレーション書いていたみたい


チャレンジフェーズ

sortせずにnext_permutationしてる人を2人落とした

実は最後の返り値をsortしてない人も2人いたらしい。気づかなかった・・・


後で

シミュレーションしなくても、2回以上名前が出てくる人は必ず勝てる

オレンジとリンゴを50%ずつ取れば必ず勝てるので。後の人はどんなに頑張っても残りを全部取れるわけではないので、負ける

ただし一人しかいない場合に注意


ソースコード

ナイーブなシミュレーション

しかし後で見たらint ok=falseって・・・

warningにならないのね・・

class EllysJuice {
public:
	vector <string> getWinners(vector <string> pl) {
		vector <string> res;
		int n=pl.size();
		
		set <string> ress;
		sort(pl.begin(), pl.end());
		do {
			int o=32, a=32;
			map <string, int> cnt;
			for(int i=0; i<n; i++) {
				if(i&1) {cnt[pl[i]]+=a/2; a/=2; }
				else {cnt[pl[i]]+=o/2; o/=2; }
			}
			int maxc=-1;
			int ok=false;
			string winner;
			for(map <string, int>::iterator mpi=cnt.begin(); mpi!=cnt.end(); mpi++) {
				if(mpi->second>maxc) {
					maxc=mpi->second;
					winner=mpi->first;
					ok=true;
				} else if(mpi->second==maxc) {
					ok=false;
				}
			}
			if(ok) ress.insert(winner);
		} while(next_permutation(pl.begin(), pl.end()));

		for(set <string>::iterator sti=ress.begin(); sti!=ress.end(); sti++) {
			res.push_back(*sti);
		}
		return res;
	}
};

TCO2012 Round1A 500 EllysFractions

| 16:30 | TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

分母と分子は互いに素なわけだから、同じ素因数を持つことができない

ということは、これまでに出てきた全ての素因数を2つに分けるだけの問題

ただし分母>分子の制約があるので、最後に2で割る必要がある

2つに分けるっていったって、同じ素因数は全部同じ側に入れるので、2^(素因数の種類数)するだけである

素因数分解してsetに突っ込んでいくコードを書いた

提出


チャレンジフェーズ

2^(素因数の種類数)を32bitで計算している人がいたので撃墜


後で

実は素因数分解はする必要がなかった

2つ以上に分解できる場合は、必ず既にその素因数が登場しているはずなので、素数かどうかだけを判定すれば良い


ソースコード

素因数分解しているコード

//素因数分解
vector <ll> factors(ll n) {
	vector <ll> f;

	for(ll i=2; i*i<=n; i++) {
		int cnt=0;
		while(n%i==0) { n/=i; cnt++; }
		if(cnt>0) f.push_back(i);
	}
	if(n>1) f.push_back(n);

	return f;
}

class EllysFractions {
public:
	long long getCount(int N) {
		long long res;
		set <int> pr;

		res=0;
		for(int i=2; i<=N; i++) {
			vector <ll> f=factors(i);
			for(int j=0; j<(int)f.size(); j++) {
				pr.insert((int)f[j]);
			}
			res+=(1LL<<(pr.size()-1));
		}
		
		return res;
	}
};

TCO2012 Round1A 1000 EllysLights

| 16:30 | TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1つのライトにつながるスイッチが最大2個っていうのがポイントだな

2個っていかにも2-SATっぽい

うーん

何か違う気もするなあ


というか、以前こんな感じの問題解いたことあるような・・・

(後で確認したら、SRM496 Div1 500 OneDimensionalBalls だった)

スイッチが2個しかないので、一つのスイッチを使うと、芋づる式に連結する他のスイッチのON/OFFが決まる

連結してるのは全部ひとまとまりで考えていいので、実は1つの連結成分ずつON/OFFを決めていけば状態数がすごく少ない

ということは適当にメモ化再帰すればいいんじゃないか


と思ったけどループするから再帰とか面倒くさい

BFSで書けばいいや・・・


書いた

うーん連結成分とか完全に無視して、前から1ビットずつ決める書き方にしちゃったけど大丈夫かなこれ・・

とりあえずサンプルは一瞬で答え出るので提出


ランダムな入力とか、全部のスイッチが連結している入力とか、色々試す

特に問題ない。一番やばそうなのでも手元で100ms以下。


チャレンジフェーズ

赤い人2人から合計3回もチャレンジ受けるが生き残る

ハニーポット状態になってしまった


システムテスト

通った。後でプラクティスで確認したらarenaでは最大で10msもかかっていない。


ソースコード

しかしこの書き方してる人、自分以外に見なかったのだが・・・

なぜだろう(一見TLEっぽいから?)

他の人はdfsしてたりunion-findしてたり色々

class EllysLights {
public:
	int getMinimum(string initial, vector <string> switches) {
		int res;
		vector <ll> sw;
		int sws, lts;
		sws=switches.size();
		lts=initial.size();

		for(int i=0; i<sws; i++) {
			ll v=0;
			for(int j=0; j<lts; j++) {
				if(switches[i][j]=='Y') v|=(1LL<<j);
			}
			sw.push_back(v);
		}

		ll ini=0;
		for(int i=0; i<lts; i++) {
			if(initial[i]=='Y') ini|=(1LL<<i);
		}

		queue <ll> q;
		q.push(ini);
		map <ll, int> memo;
		memo[ini]=0;
		while(!q.empty()) {
			ll qt=q.front(); q.pop();
			if(qt==0) break;
			for(int i=0; i<lts; i++) {
				if(qt&(1LL<<i)) {
					for(int j=0; j<sws; j++) {
						if(sw[j]&(1LL<<i)) {
							ll nv=qt^sw[j];
							if(!memo.count(nv)) {
								q.push(nv);
								memo[nv]=memo[qt]+1;
							}
						}
					}
					break;
				}
			}
		}
		
		if(!memo.count(0)) res=-1;
		else res=memo[0];
		return res;
	}
};

PutuPutu2012/11/14 17:34We've avrried at the end of the line and I have what I need!

qugzuwvdqugzuwvd2012/11/15 12:09hsO2Bf <a href="http://sgnsqmlhqiaa.com/">sgnsqmlhqiaa</a>

sbgfuadwnunsbgfuadwnun2012/11/17 11:17uDRxYO <a href="http://swfgvcnqwgxp.com/">swfgvcnqwgxp</a>

ppmzklppmzkl2012/11/17 20:51kG1Uk0 , [url=http://ybtvmgzaihcg.com/]ybtvmgzaihcg[/url], [link=http://hfpczhabiicm.com/]hfpczhabiicm[/link], http://gqoxvctjnvhq.com/

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120401