Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-11-15SRM487 Div1

SRM487 Div1 250 BunnyComputer

| 01:18 | SRM487 Div1 250 BunnyComputer - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM487 Div1 250 BunnyComputer - SRM diary(Sigmar) SRM487 Div1 250 BunnyComputer - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

全探索系か・・?

・・・

あ、、全然違いますね。。

(約10分思考停止・・)

あー何だ、mod (k+1)でグループに分類すればいいんじゃないか

だめだ、理解するまでに時間がかかりすぎ・・ちょっと酷い・・

さて分類したグループの要素数が偶数なら全部足すだけだが

要素数奇数のとき、どうするか・・

んーこれは・・奇数番目のうち最小値を捨てればいいっぽい

→書く

→サンプル通った

→提出

175点とか・・駄目すぎる・・・


チャレンジフェーズ

TLEしそうな人が2人いたので適当に大きいケースを投げる

→1成功1失敗

どうやら成功したほうもTLEじゃなかったみたい。最近どうも適当になりすぎてるような・・・


システムテスト

Passed


ソースコード

class BunnyComputer {
public:
	int getMaximum(vector <int> pref, int k) {
		int res;
		int n=pref.size();

		res=accumulate(pref.begin(), pref.end(), 0);
		for(int i=0; i<=k; i++) {
			int cnt=0;
			int minp=1000000000;
			for(int j=i; j<n; j+=k+1) {
				cnt++;
				if(cnt%2==1) {//奇数番目の最小値を選択
					minp=min(minp, pref[j]);
				}
			}
			if(cnt%2==1) {//要素数が奇数個なら最小値を破棄
				res-=minp;
			}
		}
		return res;
	}
};


SRM487 Div1 550 BunnyExam

| 01:18 | SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

え・・?これはm/kするだけじゃないの?

直感的にはlinkageとかの制約でRandomな機械が期待値を上げられるとは思えないし・・・

(結局正答率を上げる上で何のプラス情報にもなってないよね?)

証明はうまくできないけどm/kじゃなかったら多分解けないだろう。

ということは-1になるかどうかの判定問題と見た

-1になるのは、サンプル見る限りではk<=2のときはすぐ分かる

とりあえずk>2のときは置いておいて、これで書いてみるか

→サンプル合う

10分くらいでできてしまった。

って550がこんなのでいいわけないよね。

一応m/kになるか、いくつか試しておくか

(手計算でちょっと試す)

あれ?m/kにならない

やっぱりちゃんと期待値を求める問題なのか?

うーん・・・

(約30分経過)

やっぱりlinkageとかの制約が期待値に関係するなら、Sampleの5番目がm/kになると思えない

この手計算もしかして間違ってないか?

あ・・・間違ってる・・・・・・最悪だ・・・30分無駄にした・・・

残り5分くらいなんだけど、k>2は結局考える時間もなかったし良くわからん

時間ないし出してしまうか・・・

→提出


チャレンジフェーズ

予想通り即撃墜される


後で

他の人のブログを見たところ、こういうのはグラフ彩色問題というらしい

地図の彩色問題は知ってるけどそんな一般的なのがあったのね。。知識不足すぎる・・

Wikipedia先生によると、貪欲彩色法(Welsh-Powell)というアルゴリズムでグラフの最大次数+1以上の色があれば必ず塗り分けられるらしい(詳細は分からんが・・)

この問題では最大次数はlinkageの制約から4なので、5色以上だと必ず塗り分け可能ということで、3色と4色で塗り分け可能か探索すればOKみたい

(3色以上ならlinkageに含まれない部分は必ず塗り分け可能なのでlinkageに含まれるもののみ探索する)

ちなみにブルックスの定理とやらで、奇閉路か完全グラフでなければ最大次数の色で塗り分け可能だそうだ

奇閉路だと3色にしかならないので問題にならないとして、この問題ではlinkageの要素中の最小値を持つペアは他のlinkage要素ペアと最大3つしかつながらない(最大値も同様)ので次数4の完全グラフにはならない。なので4色だと必ず塗り分けが可能。

どちらにしても4色全探索が計算時間的には十分可能なので、そこまでする必要はないが・・・


色々書いたけどちょっと知識問題的だなあ。

kohyatohさんによるとグラフ彩色だとか気づかなくて貪欲彩色法も知らなくても解けるということなんできっとそっちが想定解法なんだろうなあ。

とにかく今回は手計算で変な思考ループに入ったのがいけてなかった。

なるべく検算はプログラムでやるようにしたほうが良いのかな。。。

期待値の線形性が成り立つことも未証明だしちょっと厳しい感じでした。。


ソースコード

4色以下全探索で解いてみました

システムテストは通ります

class BunnyExam {
public:
	int n, m, k;
	vector <int> linkage;
	int num[10];

	bool check(int idx) {
		if(idx==n/2) {
			for(int i=0; i<n/2; i++) {
				for(int j=0; j<n/2; j++) {
					if(i==j) continue;
					if(num[i]!=num[j]) continue;
					if(abs(linkage[i*2]-linkage[j*2])==1 || abs(linkage[i*2]-linkage[j*2+1])==1 

|| abs(linkage[i*2+1]-linkage[j*2])==1 || abs(linkage[i*2+1]-linkage[j*2+1])==1) {
						return false;
					}
				}
			}
			return true;
		}
		for(int i=0; i<k; i++) {
			num[idx]=i;
			if(check(idx+1)) return true;
		}
		return false;
	}

	double getExpected(int m, int k, vector <int> linkage) {
		double res;
		n=linkage.size();
		this->linkage=linkage;
		this->m=m;
		this->k=k;

		for(int i=0; i<n/2; i++) {
			if(abs(linkage[i*2]-linkage[i*2+1])==1) return -1;
		}
		if(k==1) {
			if(m>1) return -1;
		}
		if(k==2) {
			for(int i=0; i<n/2; i++) {
				if(abs(linkage[i*2]-linkage[i*2+1])%2==1) return -1;
			}
		}
		if(k>=3 && k<=4) {
			if(!check(0)) return -1;
		}
		res=m/(double)k;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101115