Hatena::Grouptopcoder

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

 | 

2014-05-10

TopCoder Single Round Match 620 Div 1 02:53 TopCoder Single Round Match 620 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - TopCoder Single Round Match 620 Div 1 - nodchipのTopCoder日記 TopCoder Single Round Match 620 Div 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 PairGame

  • (1,1)から全探索すると死ぬよなぁ・・・
  • 問題をよく読みなおしてみる
  • 上からやれば変化がひと通りに定まるのかな?
  • なら両方とも上からやって、後から共通部分を取ればいいか。
  • Passed System Test
class PairGame {
public:
	set<pair<int, int> > decompose(int x, int y) {
		set<pair<int, int> > decomposed;
		while (x >= 1 && y >= 1) {
			decomposed.insert(MP(x, y));
			if (x > y) {
				x -= y;
			}
			else {
				y -= x;
			}
		}
		return decomposed;
	}
	int maxSum(int a, int b, int c, int d) {
		set<pair<int, int> > A = decompose(a, b);
		set<pair<int, int> > B = decompose(c, d);

		int bestAnswer = -1;
		for (const auto& p : A) {
			if (B.count(p)) {
				MAX_UPDATE(bestAnswer, p.first + p.second);
			}
		}
		return bestAnswer;
	}
}

Medium 500 CandidatesSelection

  • 試しに前からナイーブな探索+メモを書いてみる
  • ・・・
  • 終わるはずがない
  • 後ろから探索とかできないかなぁ
  • 最終的に欲しい配列を分割しつつverifyする感じ
  • とりあえずかけた
  • 最大ケースはTLEしなさそう・・・
  • とりあえずsubmit
  • Failed System Test
  • [{"ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"}, {49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}] というテストケースで死んだっぽい。
  • これは無理っぽい。

Hard 800 PerfectSquare

  • ナイーブなDPO(2^(N * 2 + logN))とかになるのかな?
  • 分からない。

Challenge Phase

  • 500でナイーブなDPをしている人を探してみる
  • ・・・
  • 見つからなかったorz

System Test

oxx 229位 1864->1889 少しだけレーティングが上がりました。右肩下がりは止まったのでしょうか・・・。

追記 2014/05/11 10:07

  • 500をPracticeで通しました。ただし想定解法ではありません。
class CandidatesSelection {
public:
	vector <string> score;
	vector<int> result;
	set<ll> memo;
	ll hash(const vector<vector<int> >& v) const {
		ll hash = -1;
		for (const auto& x : v) {
			for (int w : x) {
				hash *= 31;
				hash += w;
			}
			hash *= 31;
		}
		return hash;
	}
	bool dfs(const vector<vector<int> >& v) {
		ll h = hash(v);
		if (memo.count(h)) {
			return false;
		}
		memo.insert(h);

		if (clock() / double(CLOCKS_PER_SEC) > 1.8) {
			return false;
		}

		bool ok = true;
		for (const auto& part : v) {
			if (!is_sorted(ALL(part))) {
				ok = false;
				break;
			}
		}
		if (ok) {
			return true;
		}

		for (const auto& magnitudeRelation : score) {
			bool ok = true;
			vector<vector<int> > next;
			for (const auto& part : v) {
				for (int i = 0; i + 1 < part.size(); ++i) {
					if (magnitudeRelation[part[i]] > magnitudeRelation[part[i + 1]]) {
						ok = false;
						break;
					}
				}

				if (!ok) {
					break;
				}

				map<char, vector<int> > m;
				for (int x : part) {
					m[magnitudeRelation[x]].push_back(x);
				}

				for (const auto& bucket : m) {
					next.push_back(bucket.second);
				}
			}

			if (!ok) {
				continue;
			}

			if (dfs(next)) {
				return true;
			}
		}

		return false;
	}
	string possible(vector <string> score, vector <int> result) {
		this->score.clear();
		this->score.resize(score[0].size());
		for (const string& s : score) {
			REP(i, s.size()) {
				this->score[i] += s[i];
			}
		}
		this->result = result;
		memo.clear();

		vector<vector<int> > initial;
		initial.push_back(result);

		string res = dfs(initial) ? "Possible" : "Impossible";
		return res;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140510
 |