Hatena::Grouptopcoder

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

 | 

2011-02-11

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

Class NameMethod NameDifficultyCoding TimeStatusPoints
PermutationSignaturereconstructLevel One0:09:36.101Passed System Test225.36
CssRulesgetMinimalCssRuleCountLevel Two1:03:46.818Opened0.00
ModuleSequencecountElementsLevel Three0:41:13.145Opened0.00

Easy 250 PermutationSignature

  • dfsで行けたりしないかなぁ?
  • いけそうな気もするけど怖いのでやめておこう
  • となると貪欲法的な何かかなぁ
  • Dが始まるところから降順に数字を割り当てるだけで行けないかな
  • いけそう
  • Passed System Test
class PermutationSignature {
public:
	vector <int> reconstruct(string signature) {
		set<int> numbers;
		for (int i = 1; i <= signature.size() + 1; ++i) {
			numbers.insert(i);
		}

		vector <int> result;
		int lastD = 0;
		REP(i, signature.size()) {
			const char ch = signature[i];
			if (ch == 'I') {
				while (lastD) {
					set<int>::iterator it = numbers.begin();
					advance(it, lastD);
					result.push_back(*it);
					numbers.erase(it);
					--lastD;
				}

				result.push_back(*numbers.begin());
				numbers.erase(numbers.begin());

			} else {
				++lastD;
			}
		}

		while (lastD) {
			set<int>::iterator it = numbers.begin();
			advance(it, lastD);
			result.push_back(*it);
			numbers.erase(it);
			--lastD;
		}

		result.push_back(*numbers.begin());
		numbers.erase(numbers.begin());

		return result;
	}
}

Middle 550 CssRules

  • 見た感じでパース+メモ探だなぁ
  • とりあえずパース部分を書いてみる
  • 書けた・・・と思う
  • メモ探索部分を書いてみる
  • あれ?再帰関数の中身が書けない・・・
  • ここがこうなってああなって・・・
  • ・・・
  • タイムアップorz
  • Opened

Hard 1000 ModuleSequence

  • 見た感じ数論なのでパス

Challenge Phase

  • 250でTLEで落ちそうな人は居ないかなぁ?
  • 居ないっぽい
  • あとは落ちそうなところは無し

System Test

o x x 88位 1977->2015 2000台を回復することができました。この調子で上げていきたいです。

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