Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-21SRM470 Div1

SRM470 Div1 250 DoorsGame

| 21:58 | SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

こういうのをゲーム木というんですね。以前も同じような問題が出たような気がします。250にしては複雑だなと思いつつもそのまんま実装してしまいましたので30分以上もかかってしまいました。250らしくGreedyに解けたようですね。。

チャレンジタイムはTLEの人がいましたので50点いただきました。

特に問題なくシステムテストはパスしました。

source

SRM470 Div1 500 DrawingLines

| 21:58 | SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) のブックマークコメント

Problem Statement

DPかなと思いつつ最後まで方針が分かりませんでした。

ゆる系エンジニアさんによると、上辺のみに着目して全ての2点のペアが交わる期待値を独立に計算し合計すれば答えが出るとのこと。E(X+Y)=E(X)+E(Y)ですね。5000万回の足し算なので、計算時間も問題なしです。DPじゃないし・・・

一般的で、ひねった複雑なやり方ではないのに、なぜかその切り口に至らない辺りに自分の視野の狭さを感じます。。。

こちらの問題もチャレンジでTLEの人がいたので50点いただきました。

以下、コンテスト後に書いたコードです。


class DrawingLines {
public:
	double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) {
		double result=0;
		int se[10010], left[10010], right[10010];
		double rem=n-startDot.size();

		memset(se, 0, sizeof(se));
		memset(left, 0, sizeof(left));
		memset(right, 0, sizeof(right));
		for(int i=0; i<(int)startDot.size(); i++) {
			se[startDot[i]]=endDot[i];
		}
		for(int i=0; i<(int)endDot.size(); i++) {
			for(int j=0; j<(int)endDot.size(); j++) {
				if(endDot[j]<endDot[i]) left[startDot[i]]++;
				if(endDot[j]>endDot[i]) right[startDot[i]]++;
			}
		}

		for(int i=1; i<=n-1; i++) {
			for(int j=i+1; j<=n; j++) {
				if(se[i]==0 && se[j]==0) result+=0.5;
				else if(se[i]>0 && se[j]==0) result+=(se[i]-1-left[i])/rem;
				else if(se[i]==0 && se[j]>0) result+=(n-se[j]-right[j])/rem;
				else if(se[i]>se[j]) result+=1;
			}
		}

		return result;
	}
};

MarkMark2013/02/17 00:33That's way more cvleer than I was expecting. Thanks!

kqqrytedphbkqqrytedphb2013/02/18 06:35xPNt08 , [url=http://gjdzistspmta.com/]gjdzistspmta[/url], [link=http://lbucohbaehdl.com/]lbucohbaehdl[/link], http://jpslatqfcovk.com/

pwzcytpwzcyt2013/02/19 19:43inRfr9 , [url=http://uoklvogqeeon.com/]uoklvogqeeon[/url], [link=http://dcqqpgtkbqzr.com/]dcqqpgtkbqzr[/link], http://cvifolqjcbmx.com/

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