Hatena::Grouptopcoder

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

 | 

2010-05-21

SRM 470@TopCoder 10:05 SRM 470@TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - SRM 470@TopCoder - nodchipのTopCoder日記 SRM 470@TopCoder - nodchipのTopCoder日記 のブックマークコメント

Easy 250 DoorsGame

  • ゲーム木・・・だと・・・
  • いやいや250でゲーム木要求するってのは何かの間違いだろ
  • きっと簡単に計算する方法があるはず
  • 取り敢えず条件をよく読んでみる
  • なるべく相手がゴールに到達するのを遅らせれば良いらしい
  • なんとなくだけど
    • 相手の持っていないドアを持っていたらそれを開ける
    • そうでなければ相手と同じドアを開ける
  • というGreedyのような気がする
  • 直感的には条件文と合っている
  • 合っているかどうかちゃんと証明はできてない
  • submit

結果:Passed System Test

class DoorsGame {
public:
	char select(const set<char>& I, const set<char>& YOU) {
		char cand = 0;
		for (set<char>::const_iterator it = I.begin(), itEnd = I.end(); it != itEnd; ++it) {
			if (YOU.count(*it)) {
				cand = *it;
			} else {
				return *it;
			}
		}
		return cand;
	}
	int determineOutcome(string doors, int trophy) {
		set<char> john(doors.begin(), doors.begin() + trophy);
		set<char> gogo(doors.begin() + trophy, doors.end());

		int result = 0;
		while (true) {
			char c;

			++result;
			c = select(john, gogo);
			john.erase(c);
			if (gogo.count(c)) {
				gogo.erase(c);
			}
			if (john.empty()) {
				if (gogo.empty()) {
					return 0;
				} else {
					return result;
				}
			}

			++result;
			c = select(gogo, john);
			gogo.erase(c);
			if (john.count(c)) {
				john.erase(c);
			}
			if (gogo.empty()) {
				if (john.empty()) {
					return 0;
				} else {
					return -result;
				}
			}
		}
	}
};

Middle 500 DrawingLines

  • どう見てもDP臭・・・
  • そして全く取っ掛かりがつかめない
  • もうだめだ・・・

結果:Opened

Hard 1000 BuildingRoads

  • きっとグラフに落とすんだろうなぁ・・・
  • 最大流にでも落とすのかなぁ・・・
  • 全く分から無いorz

結果:Opened

Challenge Phase

  • 今回は撃墜ポイントが全く分から無い
  • 250が続々と落ちてる
  • もしかしてTLE狙えば良かった?
  • ・・・時すでに遅しorz

SystemTest

o x x 192.82

総評

レーティングが落ちなかったので安心した。

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