Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-10-13SRM521 Div1

SRM521 Div1 500 RangeSquaredSubsets

| 00:43 | SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) SRM521 Div1 500 RangeSquaredSubsets - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは・・・いくら何でも問題文が意味不明すぎ

if and only ifってあるけど、ifのほうが成り立つとするなら正方形内の全ての点がPに含まれないといけないんだけど・・・そんな点って無限に存在するんですが・・・

しかも正方形に含まれるというのが、境界線にあるもののみのようにも読み取れるので更に良くない

何とかサンプルから類推すると、与えられたセット内の点のうち、あるサブセットをPとして、P以外のセット内の点が正方形に入ってはいけないということらしい

(一応後でメッセージで補足があったので無限に存在しないというのは分かるようになったようだが・・・)

ともかく題意を理解するのに10分以上かかった。解いた人が少ない原因の一つはこの意味不明な問題文だろう・・・


解法自体はとりあえず登場する全てのx座標とy座標で格子を作って、それで点集合を区切るのが良さそうである

要素数は40だから、セットの数は最大でも40^4/4くらいで64万程度。

重複するものを除くためにstd::setを利用したとしても十分に間に合うと思われる。


適当に書いた。

サンプルの最後が合わない。答えより1多い。

空集合を除くのを忘れていた。。。

修正。サンプルあった。

コーナーケースはないだろうか。ないようだ。

最大ケースで0.1秒くらい。楽勝っぽい。

提出。


ソースコード

class RangeSquaredSubsets {
public:
	long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) {
		long long res;
		int n=x.size();

		vector <int> xx=x, yy=y;
		xx.push_back(-300000000);
		xx.push_back(300000000);
		sort(xx.begin(), xx.end());
		xx.erase(unique(xx.begin(), xx.end()), xx.end());
		yy.push_back(-300000000);
		yy.push_back(300000000);
		sort(yy.begin(), yy.end());
		yy.erase(unique(yy.begin(), yy.end()), yy.end());

		set <vector <int> > ress;

		int xsz=xx.size(), ysz=yy.size();
		for(int i=1; i<xsz-1; i++) {
			for(int j=i; j<xsz-1; j++) {
				for(int k=1; k<ysz-1; k++) {
					for(int l=k; l<ysz-1; l++) {
						int xlo=xx[i], xhi=xx[j];
						int ylo=yy[k], yhi=yy[l];
						int xllo=xx[i-1], xlhi=xx[j+1];
						int yllo=yy[k-1], ylhi=yy[l+1];
						int minside=max(xhi-xlo, yhi-ylo);
						int maxside=min(xlhi-xllo, ylhi-yllo);
						if(minside>=maxside) continue;
						if(nhigh<minside) continue;
						if(nlow>=maxside) continue;
						vector <int> pts;
						for(int m=0; m<n; m++) {
							if(x[m]>=xlo && x[m]<=xhi && y[m]>=ylo && y[m]<=yhi) pts.push_back(m);
						}
						if(pts.empty()) continue;
						ress.insert(pts);
					}
				}
			}
		}

		res=ress.size();
		return res;
	}
};

prosho007prosho0072011/10/14 13:33赤おめでとうございます!

kojingharangkojingharang2011/10/14 17:46すごいっす、おめでとうございます~

SigmarSigmar2011/10/14 21:54prosho007さん、kojingharangさん、ありがとうございます!
何とかこの色を維持できるよう頑張ります。

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