Hatena::Grouptopcoder

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

 | 

2010-05-04

SRM 469 22:39 SRM 469 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SRM 469 - nodchipのTopCoder日記 SRM 469 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 TheMoviesLevelOneDivOne

  • 答えがlong longなので全部調べるのは無理・・・と
  • 予約されてる席は高々47行しか無いから、予約の入っている行と入っていない行に分けて考えればおk
  • 予約されていない列はかけ算するだけ
  • 予約されている行は席を列でソートして間をカウントしていけばいいはず
  • 書けた
  • サンプル通った
  • 64bitあふれ多分ない・・・
  • submit

結果:Accepted

class TheMoviesLevelOneDivOne {
public:
	long long find(int n, int m, vector <int> row, vector <int> seat) {
		const ll height = n;
		const ll width = m;
		long long result = 0;

		map<int, set<int> > reserved;
		for (int i = 0; i < row.size(); ++i) {
			const int x = seat[i];
			const int y = row[i];
			reserved[y].insert(x);
		}

		result += (width - 1) * (height - reserved.size());

		for (map<int, set<int> >::iterator it = reserved.begin(), itEnd = reserved.end(); it != itEnd; ++it) {
			it->second.insert(0);
			it->second.insert(width + 1);
			vector<int> r(it->second.begin(), it->second.end());

			for (int i = 0; i + 1 < r.size(); ++i) {
				result += max(0, r[i + 1] - r[i] - 2);
			}
		}

		return result;
	}
};

Middle 500 TheMoviesLevelTwoDivOne

  • 巡回セールスマン問題きた!
  • O(2^20*20)だから通る!
    • ところで47って誰だろう・・・?
    • 58じゃないからいいか・・・。
  • 書けた!
  • ・・・映画を観る順番が辞書順になってなくね?
  • ・・・
  • dfsでメモ探できる?
  • 先頭から順番に見て行って、
  • それまでの経路より良かったら経路更新
  • 辿ったノードはビットフラグで管理して、
  • 同じフラグが出てきたら、そいつは辞書順で前に出てきたやつより遅いやつだから棄却
  • 計算量はO(2^20*20)だから行けそう・・・
  • 書けた
  • サンプル通った
  • 最大ケースも大丈夫そう
  • submit

結果:Accepted

static bool dp[1 << 20];

int countBits(int x){
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
	x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
	x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
	return x;
}
bool compairByBitCount(int lh, int rh) {
	return countBits(lh) < countBits(rh);
}

class TheMoviesLevelTwoDivOne {
public:
	int n;
	vector<int> answer;
	vector <int> length;
	vector <int> scary;
	void dfs(int currentFlag, int currentSleep, vector<int>& currentPath) {
		if (dp[currentFlag]) {
			return;
		}
		dp[currentFlag] = true;

		if (answer.size() < currentPath.size()) {
			answer = currentPath;
		}

		for (int next = 0; next < n; ++next) {
			if (currentFlag & (1 << next)) {
				continue;
			}

			const int nextFlag = (currentFlag | (1 << next));
			if (dp[nextFlag]) {
				continue;
			}

			if (currentSleep < scary[next]) {
				continue;
			}

			const int nextCost = currentSleep - length[next] + 47;
			if (nextCost < 0) {
				continue;
			}

			currentPath.push_back(next);
			dfs(nextFlag, nextCost, currentPath);
			currentPath.pop_back();
		}
	}

	vector <int> find(vector <int> length, vector <int> scary) {
		answer.clear();
		n = length.size();
		memset(dp, 0, sizeof(dp));
		this->length = length;
		this->scary = scary;

		vector<int> currentPath;
		dfs(0, 74, currentPath);

		vector<int> result = answer;
		for (int i = 0; i < n; ++i) {
			if (std::find(result.begin(), result.end(), i) == result.end()) {
				result.push_back(i);
			}
		}

		return result;
	}
};

Hard 1000 TheMoviesLevelThreeDivOne

  • 20なら全探索+シミュレーションだよねぇ・・・。
  • DPっぽくやるのかな?
  • 分からない

結果:Opened

Challenge Phase

  • 今回のポイントは
    • 250でintで和を取っている
    • 250でTLEする
  • という感じで見ていくことにしよう
  • 見た感じでそういう人はいないっぽなぁ
  • あれ?
  • この人最後の集計がおかしい気がする
  • rows[k-1]じゃなくてrow.size()じゃね?
  • これだとぜんぜん違う答になるよなぁ・・・。
  • Challenge!
  • Success!
  • 50ゲットした
  • 時間ないからこれで終りかな・・・

System Test

o o x +50 551.62 34位

やったね!

かなりいい感じだったと思います。なんとなくDPが解けるようになり始めた気がしてきました。

2010 TCO Algorithm Qualification Round 1 09:17 2010 TCO Algorithm Qualification Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - 2010 TCO Algorithm Qualification Round 1 - nodchipのTopCoder日記 2010 TCO Algorithm Qualification Round 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 GirlsAndBoys

  • ええっと・・・
  • バブルソートの回数を数えるのかな?
  • 男子が左に寄る場合と右に寄る場合の二つを考えれば良いはず
  • できた
  • submit

結果: Passed System Test

class GirlsAndBoys {
public:
	int count(vector<int> v) {
		const int n = v.size();
		bool updated = true;
		int counter = 0;
		while (updated) {
			updated = false;
			for (int i = 0; i + 1 < n; ++i) {
				if (v[i] > v[i + 1]) {
					swap(v[i], v[i + 1]);
					updated = true;
					++counter;
				}
			}
		}
		return counter;
	}
	int sortThem(string row) {
		vector<int> gb, bg;
		for (int i = 0; i < row.size(); ++i) {
			gb.push_back(row[i] == 'G' ? 0 : 1);
			bg.push_back(row[i] == 'B' ? 0 : 1);
		}

		int result = min(count(gb), count(bg));
		return result;
	}
}

Middle 500 RobotSimulation

  • 200,000,000は全部シミュレーションで回すとTLEだ・・・
  • どうやるんだろう
  • 1ループ当たりの増分は同じになるのかな?
  • 最初のループとそれ以降のループの回数を数えて最後にかけ算してみた
  • なんか答えが違う・・・
  • 最初の方はループの増分が一定にならないらしい
  • 1000回くらい回してからにしてみよう
  • 答えが合った
  • submit

結果: Passed System Test

class RobotSimulation {
public:
	int cellsVisited(string program, int times) {
		set<pair<int, int> > memo;
		int dx[0x100], dy[0x100];
		memset(dx, 0, sizeof(dx));
		memset(dy, 0, sizeof(dy));
		dx['R'] = 1;
		dx['L'] = -1;
		dy['U'] = 1;
		dy['D'] = -1;

		int x = 0;
		int y = 0;
		memo.insert(make_pair(x, y));

		int result = 0;
		int lastDelta = -1;

		int safeCounter = 0;
		for (int step = 0; step < times; ++step) {
			for (int i = 0; i < program.size(); ++i) {
				x += dx[program[i]];
				y += dy[program[i]];
				memo.insert(make_pair(x, y));
			}

			const int nextResult = memo.size();
			if (lastDelta == nextResult - result && ++safeCounter == 1000) {
				result += (times - step) * lastDelta;
				break;
			}
			lastDelta = nextResult - result;
			result = nextResult;
		}

		return result;
	}
}

Hard 1000 SequenceMerger

  • 数字を全部生成するとTLEか・・・
  • ここを高速化しなきゃいけないんだろうなぁ
  • 二分探索か?
  • ある数字を決め打ちして、それより小さい数が何個あるかはすぐに求められる
  • 数字で二分探索してpositionに変換すれば良いはず
  • 書き始めた
  • バグが取れない・・・

結果: Opened

Challenge Phase

  • コーナーケースがexampleに含まれているから挑戦しにくいなぁ
  • というかexampleなかったら自分が落ちてた
  • ・・・
  • 挑戦出来そうなもの無いや・・・

System Test

o o x

終りに

普通の成績でした・・・

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