Hatena::Grouptopcoder

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

 | 

2010-08-27

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

Easy 250 InternetSecurity

  • 書いてある通りに実装するだけ
  • 計算量も問題ないはず
  • submit

結果: Failed System Test

更新中フラグを立てるのを忘れていました。以下はPracticeで通ったコードです。

class InternetSecurity {
public:
	vector <string> determineWebsite(vector <string> address, vector <string> keyword, vector <string> dangerous, int threshold) {
		const int N = address.size();
		sort(ALL(dangerous));
		vector<vector<string> > keywords(keyword.size());
		REP(n, N) {
			istringstream iss(keyword[n]);
			string word;
			while (iss >> word) {
				keywords[n].push_back(word);
			}
			sort(ALL(keywords[n]));
		}

		vector<bool> danger(N);

		bool updated = true;
		while (updated) {
			updated = false;

			REP(n, N) {
				if (danger[n]) {
					continue;
				}

				vector<string> inter;
				set_intersection(ALL(keywords[n]), ALL(dangerous), back_inserter(inter));
				if (inter.size() >= threshold) {
					danger[n] = true;
					dangerous.insert(dangerous.end(), ALL(keywords[n]));
					sort(ALL(dangerous));
					dangerous.erase(unique(ALL(dangerous)), dangerous.end());
					updated = true;
				}
			}
		}

		vector <string> result;
		REP(n, N) {
			if (danger[n]) {
				result.push_back(address[n]);
			}
		}
		return result;
	}
}

Middle 450 NetworkSecurity

  • 450ならきっと解けるはず
  • ???
  • 何が何だかわからない
  • 問題を読み直してみる
  • 全てのクライアントとサーバーのペアについて、データの経路上に最低一つのゲートを設置するのか・・・
  • (考え中)
  • DAGだし、グラフの先の方から貪欲に置いていけばいいのかな?
  • 書いた
  • Submit

結果: Failed System Test

TLEしました。キャッシュを取らないと駄目だったようです。以下はPracticeを通したソースコードです。

class NetworkSecurity {
public:
	int N, M;
	vector <string> clientCable;
	vector <string> serverCable;
	set<pair<int, int> > answers;
	int memo[64][64];
	bool dfs(int srcClient, int server) {
		if (memo[srcClient][server]) {
			if (memo[srcClient][server] == 2) {
				return true;
			} else {
				return false;
			}
		}

		REP(dstClient, N) {
			if (clientCable[srcClient][dstClient] == 'Y') {
				if (dfs(dstClient, server)) {
					memo[srcClient][server] = 2;
					return true;
				}
			}
		}
		if (serverCable[srcClient][server] == 'Y') {
			answers.insert(make_pair(srcClient, server));
			memo[srcClient][server] = 2;
			return true;
		}
		memo[srcClient][server] = 1;
		return false;
	}
	int secureNetwork(vector <string> clientCable, vector <string> serverCable) {
		memset(memo, 0, sizeof(memo));
		answers.clear();
		this->clientCable = clientCable;
		this->serverCable = serverCable;
		N = clientCable.size();
		M = serverCable[0].size();
		REP(client, N) {
			REP(server, M) {
				dfs(client, server);
			}
		}
		int result = answers.size();
		return result;
	}
}

Hard 1100 StringDecryption

  • 問題が読めない・・・
  • ちゃんと読みなおしてみる
  • 読めた
  • きっとDP
  • どうせDP
  • どうせ・・・どうせ・・・orz

結果: Opened

Challenge Phase

  • 撃墜ポイントが良く分からない
  • 250で自分のコードが落ちるのに気づいたorz
  • 戦意喪失orz

System Test

x x x orz

1844->1684 再び上がることはできるのでしょうか・・・orz

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