Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-09-09SRM481 Div1

SRM481 Div1 250 ChickenOracle

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

Problem Statement

問題を見る

→何か、ややこしそう

→うーん・・・eggのうち、嘘つきの人数をi人と仮定するとchickenのうちの嘘つきはliarCount-i人か

→そうすると、、iを0からliarCountまでイテレートして、eggかchickenがlieCountと一致するか確かめれば良いのかな

→書く→サンプル合わない

→条件を色々間違えている。eggとchickenで嘘つきがそれぞれの人数を超えるとcontinueしなければ・・・

→書き直す→サンプル合う→提出

→・・・間違ってないな・・よし

→500へ


チャレンジフェーズ

→たぶん、イテレートせずに数学的な条件式で答えを出す人はいるだろう

→そうすると、間違えやすそうなのは・・・eggをliar数で補正すると常に奇数か偶数のどちらかにしかならないところか

→%2という記載がない人を2人撃墜


システムテスト

→Passed


以下、ソースです。

class ChickenOracle {
public:
	string theTruth(int n, int ec, int lc, int lac) {
		string res;
		bool e=0, c=0;

		int cc=n-ec;

		for(int i=0; i<=lac; i++) {
			int cec=ec-i;
			int ccc=cc-(lac-i);
			if(cec>n || ccc>n || cec<0 || ccc<0) continue;
			cec+=lac-i;
			ccc+=i;
			if(cec==lc) c=1;
			if(ccc==lc) e=1;
		}
		if(e&&c) res="Ambiguous";
		else if(e&&!c) res="The egg";
		else if(!e&&c) res="The chicken";
		else if(!e&&!c) res="The oracle is a lie";

		return res;
	}
};

SRM481 Div2 500 BatchSystemRoulette

| 01:19 | SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→何かすごく難しいような・・

→とりあえず、同じ人のタスクは連続でやったほうが良いのかどうなのか・・?

→1の人のタスク1a, 1bと2の人のタスク2aがあった場合、1a->2a->1bとやるより、2a->1a->1bとやったほうが1の人の終了時間は変わらないが2の人の終了は早くなり全体として良くなる

→ということは常に同じ人のタスクは連続でやるのが良い

→次に、何となく軽いタスクから終わらせたほうが良いように見えるがどうなのか?

→軽い順に1,2のタスクがあったとする

→1と2を入れ替えると、2->1となるが・・2つ目が終わる時間は変わらないのに、1つ目が終わる時間が遅くなり平均時間は長くなる

→タスクを増やして一般化しても同じことが成り立つので、軽い順に終わらせるのが良い

→何だ、簡単なGreedyじゃないか

→よし、書こう

→うまく書けない・・・同じ大きさのタスクがあるとランダム性が生まれるので混乱する

→複数のタスクを持つ場合の平均時間も良くわからない

→色々ぐだぐだになりつつようやく書けた

→何とか終了3分前くらいに提出

→何かミスってそうな気がする・・


チャレンジフェーズ

→出してる人もほとんどいないので何もせず

→あ・・撃墜された・・何を間違えたんだ・・


終了後

→一部オーバーフローしていた。基本的なところができていない。もったいなさすぎる。

→というか、コードが長すぎる。他の人を見て短く書く工夫を勉強しなければ。。。


(9/10追記)

ということで提出が早い5人くらいのコードを見てみましたが、この問題で見落としていた重要な点が分かりました。

タスクの処理順がGreedyに求まるというところが分かった時点で、何とでもなると思い書き始め、途中でコーディングが難しいことに気づいて「実装が難しい問題なのかな」と思い込んでいました。

よく考えると期待値の問題では基本的なテクニックである線形性を利用すれば、非常にコードが簡単になるんですね。もう一つブレイクスルーがあると思っていませんでした。。

線形性というのは、X,Yを確率変数、E(X)をXの期待値としたとき、E(aX+bY)=aE(X)+bE(Y)となる性質のことを言っています。

この問題では確率変数はタスクが終わる時間となりますが、全タスク実行時間の総和で表すことができます。つまり、あるタスクiが終わる時間をXiとし、各タスクjを1つだけ実行する時間をxj、タスクの数をnとすると、Xi=x1+x2+...+xnとなります。(xjはiの前に実行される場合duration[j]、iの後に実行される場合0になります)

従ってE(Xi)=E(x1)+E(x2)+...+E(xn)で計算できますので、P(xj=duration[j])(以下Pと省略)が計算できれば簡単に解けることになります。ここで、人ごとにタスクの総和を求めると、タスクjを実行する人のタスク総和がタスクiを実行する人のタスク総和より短い場合、P=1となり、jとiのタスク総和が等しい場合はP=0.5となり、jの総和がiより長い場合P=0となるのは明らかです。また、jとiが同じ人が実行するタスクだった場合、P=0.5となるのは明らかです。

というわけで、jとiが同じ人の場合、タスク総和が自動的に等しくなりP=0.5となるので、同じ人かどうかは特に判別しなくても良いです。


この問題を解いた本番時に立ち返ると、Greedyだと分かった時点で解けた気になってしまうのは、うまく思考的な罠が仕掛けられていた気がします。やっぱり難しいなと思った時点で一度立ち止まって、再考してみることが必要ですね。


以下、上記解法を反映したソースを追記します。

簡単なコード

class BatchSystemRoulette {
public:
	vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) {
		vector <double> res(user.size());
		map <string, ll> mp;

		for(int i=0; i<(int)user.size(); i++) {
			mp[user[i]]+=duration[i];
		}

		for(int i=0; i<(int)user.size(); i++) {
			res[i]+=duration[i];
			for(int j=0; j<(int)user.size(); j++) {
				if(i==j) continue;
				if(mp[user[j]]<mp[user[i]]) res[i]+=duration[j];
				if(mp[user[j]]==mp[user[i]]) res[i]+=duration[j]/2.;
			}
		}

		return res;
	}
};

元のコード(のオーバーフローを修正したもの)

class BatchSystemRoulette {
public:
	vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) {
		vector <double> res;
		map <string, int> mp;

		int id=0;
		for(int i=0; i<(int)user.size(); i++) {
			if(!mp.count(user[i])) {
				mp[user[i]]=id++;
			}
		}
		vector <int> idv;
		for(int i=0; i<(int)user.size(); i++) {
			idv.push_back(mp[user[i]]);
		}
		vector <pair <ll, int> > task(id, make_pair(0LL, 0));//taskをvector <pair <int, int> >にしてオーバーフローした
		for(int i=0; i<(int)idv.size(); i++) {
			task[idv[i]].first+=duration[i];
			task[idv[i]].second=idv[i];
		}
		sort(task.begin(), task.end());

		vector <double> avtask(id);
		ll time=0;
		ll ptask=-1;
		ll ptime=0;
		ll pcnt=0;
		for(int i=0; i<id; i++) {
			if(ptask!=task[i].first) {
				if(pcnt>0) {
					for(int j=i-pcnt; j<i; j++) {
						avtask[j]=ptime+(double)ptask*(pcnt*(pcnt-1)/2)/pcnt;
					}
				}
				ptime+=ptask*pcnt;
				ptask=task[i].first;
				pcnt=1;
			} else pcnt++;
		}
		for(int j=id-pcnt; j<id; j++) {
			avtask[j]=ptime+(double)ptask*(pcnt*(pcnt-1)/2)/pcnt;
		}
		vector <int> mpt(task.size());
		for(int i=0; i<(int)task.size(); i++) {
			mpt[task[i].second]=i;
		}

		res.resize(user.size());
		for(int i=0; i<id; i++) {
			vector <ll> v;
			for(int j=0; j<(int)idv.size(); j++) {
				if(idv[j]==i) {
					v.push_back(duration[j]);
				}
			}
			vector <double> rv(v.size());
			ll sum=accumulate(v.begin(), v.end(), 0LL);
			for(int j=0; j<(int)v.size(); j++) {
				rv[j]=(sum-v[j])/2.+v[j];
			}
			int jj=0;
			for(int j=0; j<(int)idv.size(); j++) {
				if(idv[j]==i) {
					res[j]=avtask[mpt[i]]+rv[jj++];
				}
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100909