Hatena::Grouptopcoder

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

 | 

2011-03-09

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

Easy 250 ColorfulRabbits

  • うさぎ回きた!
  • ・・・猫なのにポチなのか? (<-想定されるツッコミ)
  • 同じ数字のうさぎはまとめて処理すればよさげ
  • サンプル合わない・・・
  • ちょっと修正
  • サンプル通った
  • Passed System Test
class ColorfulRabbits {
public:
	int getMinimum(vector <int> replies) {
		map<int, int> rabbits;
		REP(i, replies.size()) {
			rabbits[replies[i]]++;
		}

		int result = 0;
		while (!rabbits.empty()) {
			const int r = rabbits.begin()->first;
			rabbits.begin()->second -= r + 1;
			result += r + 1;
			if (rabbits.begin()->second <= 0) {
				rabbits.erase(rabbits.begin());
			}
		}

		return result;
	}
}

WhiteSpaceEditing

  • あふれんばかりのDP
  • どうせ解けないんだろうなぁ
  • ・・・
  • これ簡単じゃね
  • 上からやって行くだけなきがする (<- 間違い)
  • 書けた
  • サンプル通った
  • しかし「hosの550がこんなに簡単なはずがない!」
  • けど判例が思いつかないのでsubmit
    • Challenge Succeeded
  • 想定解はO(N)からO(N^5)など色々あるそうです
  • O(N^5)DP解法はよく理解できませんでした
  • 以下はTL上に流れていたコメントを元にしたO(N)解で、Practiceで通ったものです
class WhiteSpaceEditing {
public:
	int getMinimum(vector <int> lines) {
		lines.insert(lines.begin(), 0);
		int begin = 0;
		int result = 0;
		REP(i, lines.size() - 1) {
			if (lines[i] > lines[i + 1]) {
				result += lines[i] - lines[begin];
				begin = i + 1;
			}
		}

		result += lines.back() - lines[begin] + lines.size() - 2;

		return result;
	}
}

Hard 1000 ImpossibleGame

  • 内容を理解することができませんでしたorz

Challenge Phase

  • 550が撃墜祭りになるのは分かる
  • しかし、落とすための入力が思いつかないorz
  • 何もせずに終わったorz

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
ColorfulRabbitsgetMinimumLevel One0:04:36.324Passed System Test243.64
WhiteSpaceEditinggetMinimumLevel Two0:17:56.530Challenge Succeeded409.86
ImpossibleGamegetMinimumLevel Three0:48:52.539Opened0.00

2015->1989

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