Hatena::Grouptopcoder

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

 | 

2011-02-02

Single Round Match 496 10:29 Single Round Match 496  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 496  - nodchipのTopCoder日記 Single Round Match 496  - nodchipのTopCoder日記 のブックマークコメント

Class NameMethod NameDifficultyCoding TimeStatusPoints
ColoredStrokesgetLeastLevel One0:04:34.867Passed System Test243.71
OneDimensionalBallscountValidGuessesLevel Two0:38:19.832Passed System Test246.90
YetAnotherHamiltonianPathleastCostLevel Three0:19:24.687Challenge Succeeded683.23

Easy 250 ColoredStrokes

  • これ、めいいっぱい長く塗ればいいだけじゃね?
  • 二重ループに書い書いて終了
class ColoredStrokes {
public:
	int getLeast(vector <string> picture) {
		const int H = picture.size();
		const int W = picture[0].size();
		int result = 0;

		REP(x, W) {
			bool last = false;
			REP(y, H) {
				const char ch = picture[y][x];
				const bool is = (ch == 'B' || ch == 'G');
				if (last && !is) {
					++result;
				}
				last = is;
			}
			if (last) {
				++result;
			}
		}

		REP(y, H) {
			bool last = false;
			REP(x, W) {
				const char ch = picture[y][x];
				const bool is = (ch == 'R' || ch == 'G');
				if (last && !is) {
					++result;
				}
				last = is;
			}
			if (last) {
				++result;
			}
		}

		return result;
	}
}

Middle 500 OneDimensionalBalls

  • なんじゃこりゃ?
  • DP
  • とりあえず考えてみる
  • ボールは+-speedだけ動く
  • となると二部マッチング
  • 連結成分について独立に計算してかけあわせればよいらしい。
  • 二部マッチングの個数が求まれば良い
  • ググッてみた
  • ・・・
  • 我に返って、グラフの形の特殊性から別の計算方法がないか考えてみる
  • 位置はユニークなので、三つ以上のボールが一つの地点に集まる可能性はない。高々2個まで。
  • となるとグラフの形は一直線っぽい
  • これを使えないだろうか?
  • グラフの右と左の個数が同じ場合は1通り
  • 右が1個多い場合は右+1通りっぽい
  • あとはかけ合わせておしまい
class OneDimensionalBalls {
public:
	long long countValidGuesses(vector <int> firstPicture, vector <int> secondPicture) {
		long long result = 0;
		set<ll> lefts(ALL(firstPicture));
		set<ll> rights(ALL(secondPicture));
		set<ll> speeds;
		REP(i, firstPicture.size()) {
			REP(j, secondPicture.size()) {
				speeds.insert(ABS(firstPicture[i] - secondPicture[j]));
			}
		}
		speeds.erase(0);

		for (set<ll>::iterator it = speeds.begin(), itEnd = speeds.end(); it != itEnd; ++it) {
			const ll speed = *it;
			ll answer = 1;
			map<ll, vector<ll> > leftToRight;
			map<ll, vector<ll> > rightToLeft;

			bool ok = true;
			REP(i, firstPicture.size()) {
				ok = false;

				const ll left = firstPicture[i];
				if (rights.count(left - speed)) {
					leftToRight[left].push_back(left - speed);
					rightToLeft[left - speed].push_back(left);
					ok = true;
				}

				if (rights.count(left + speed)) {
					leftToRight[left].push_back(left + speed);
					rightToLeft[left + speed].push_back(left);
					ok = true;
				}

				if (!ok) {
					break;
				}
			}

			if (!ok) {
				continue;
			}

			set<ll> visitedLeft;
			set<ll> visitedRight;
			REP(leftIndex, firstPicture.size()) {
				if (visitedLeft.count(firstPicture[leftIndex])) {
					continue;
				}
				visitedLeft.insert(firstPicture[leftIndex]);

				// value, isLeft
				vector<pair<ll, bool> > stk;
				int numberOfLefts = 0;
				int numberOfRights = 0;
				stk.push_back(MP(firstPicture[leftIndex], true));
				while (!stk.empty()) {
					const ll value = stk.back().first;
					const bool isLeft = stk.back().second;
					stk.pop_back();

					if (isLeft) {
						++numberOfLefts;
						const vector<ll>& edges = leftToRight[value];
						assert(!edges.empty());
						REP(edgeIndex, edges.size()) {
							const ll right = edges[edgeIndex];
							if (visitedRight.count(right)) {
								continue;
							}
							visitedRight.insert(right);
							stk.push_back(MP(right, false));
						}

					} else {
						++numberOfRights;
						const vector<ll>& edges = rightToLeft[value];
						assert(!edges.empty());
						REP(edgeIndex, edges.size()) {
							const ll left = edges[edgeIndex];
							if (visitedLeft.count(left)) {
								continue;
							}
							visitedLeft.insert(left);
							stk.push_back(MP(left, true));
						}
					}
				}

				if (numberOfLefts > numberOfRights) {
					answer = 0;
					break;
				}

				if (numberOfLefts < numberOfRights) {
					answer *= numberOfRights;
				}
			}

			result += answer;
		}

		return result;
	}
}

Hard 950 YetAnotherHamiltonianPath

  • も、もしかして貪欲法?
  • 950だし・・・
  • やってみた
  • だめだったorz

Challenge Phase

  • 250で{"G"}で落ちる人を探す
  • ・・・
  • いないっぽい
  • しーん・・・

System Test

o o x 1901->1977 レーティングが結構上がりました。2000台回復したいです。

ctwclcctwclc2011/02/28 00:07bhEhNN <a href="http://shlbipvzqaxh.com/">shlbipvzqaxh</a>, [url=http://kpachxtktqgm.com/]kpachxtktqgm[/url], [link=http://aukfwkotnopp.com/]aukfwkotnopp[/link], http://wehgwsiyfimv.com/

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