Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2009-06-24

Single Round Match 443 @ TopCoder 17:34 Single Round Match 443 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 443 @ TopCoder - nodchipのTopCoder日記 Single Round Match 443 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 443 @ TopCoderの参加記録です。

Easy 300 CirclesCountry

二次元座標上に円がいくつか配置されている。これらの円は交点は持たないが、一方が他方の内部に配置されている場合がある。指定された二地点間を移動するとき、最低何回円をまたがなければならないか求めよ。

300なのでいやな予感がしていたのですが、案の定幾何で問答そうな問題でした。しばらく考えた後、一番外側まで行ってからもう一方の点に行くルートを考え、その間に同じ円を2回通ったら、その部分だけ削除すると言うアルゴリズムを考えました。一番外側に行くときは、x座標の正の大きいところまで行けば十分だと考え、円の交点を適当に求めていきました。

ソースコードは以下の通りです。

class CirclesCountry {
public:
	vector<int> checkBorders(vector <int> X, vector <int> Y, vector <int> R, int x, int y)
	{
		vector<pair<double, int> > crossPoints;
		const int n = X.size();
		for (int i = 0; i < n; ++i){
			const int a = X[i];
			const int b = Y[i];
			const int r = R[i];
			if (y <= b - r || b + r <= y){
				continue;
			}

			const int yb = y - b;
			crossPoints.push_back(make_pair(a + sqrt((double)(r * r - yb * yb)), i));
			crossPoints.push_back(make_pair(a - sqrt((double)(r * r - yb * yb)), i));
		}

		sort(crossPoints.begin(), crossPoints.end());

		vector<int> result;
		for (vector<pair<double, int> >::iterator it = crossPoints.begin(); it != crossPoints.end(); ++it){
			if (x < it->first){
				result.push_back(it->second);
			}
		}

		for (int i = 0; i < n; ++i){
			if (count(result.begin(), result.end(), i) == 2){
				result.erase(remove(result.begin(), result.end(), i), result.end());
			}
		}

		return result;
	}

	int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
		vector<int> a = checkBorders(X, Y, R, x1, y1);
		vector<int> b = checkBorders(X, Y, R, x2, y2);
		reverse(b.begin(), b.end());
		a.insert(a.end(), b.begin(), b.end());

		const int n = X.size();
		for (int i = 0; i < n; ++i){
			if (count(a.begin(), a.end(), i) == 2){
				a.erase(remove(a.begin(), a.end(), i), a.end());
			}
		}

		int result = a.size();
		return result;
	}
};

想定解法は二地点についてそれぞれどの円の内部にあるかを調べ、その集合をいじってどうのこうのするという物だったようです。

Middle 600 BinaryFlips

0がA個、1がB個ある。この数字の中からK個選んで反転させる操作を考える。全てを1にするには最低何回操作する必要があるか求めよ。

600なのでまたもやいやな予感がしたのですが、アドホック系なのか枝狩り探索なのか判断に困るような煮え切らない問題です。

普通の探索を書いて{100000,100000,20000}というケースでTLEしたため、諦めました。

解法は二つあり、1つは最適戦略を使って回数を数えるもの、2つ目は謎の枝狩り探索でした。

Hard 1000 ShuffledPlaylist

音楽プレイヤーの中に何曲か曲が入っており、それぞれの曲には曲の長さとジャンルが設定されている。曲順はランダムで決定されるが、遷移可能なジャンルにしか遷移しない。指定された長さだけ演奏させるとき、何通りの曲順があるか求めよ。

行列のN乗なのだそうですが、まったく持ってやり方がわかりませんorz

撃墜フェーズ

幅優先探索で怪しそうな人にチャレンジしてみましたが、失敗しました。

システムテスト

o x x -25

ぼちぼちです・・・。

結果

300位台でした。もう少しきりっとした成績をとりたいです。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20090624
 |