Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-08-27SRM480 Div1

SRM480 Div1 250 InternetSecurity

| 21:31 | SRM480 Div1 250 InternetSecurity - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM480 Div1 250 InternetSecurity - SRM diary(Sigmar) SRM480 Div1 250 InternetSecurity - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→実装問題かな

→カタカタ

→うーん同じ要素がdangerousに入ると面倒そうだな

→dangerousをsetに入れ直そう

→カタカタカタカタ

→できた。意外と面倒だった

→サンプル通る→提出

→かなりstraightforwardなやり方で解けてしまったけど・・・

→ちょっと効率が・・悪いかも・・?最悪50^5で6億3億の比較をしている気がしてきた

→まあ・・大丈夫かな・・2億回足し算しても1秒だし・・find関数使ってるから多少は効率が良いだろう

→450へ


チャレンジフェーズ

→450に的を絞ったため何もせず


システムテスト

→Passed

計算時間は10ms以下で楽勝だったみたい。


それにしても、std::findじゃなくてset::findを使ったら良かった。

急いで書くと、効率に気が回らない・・・

以下、ソースです。

template <class T> vector <T> strspl(string str) {
	vector <T> res;
	istringstream iss(str);
	copy(istream_iterator <T>(iss), istream_iterator <T>(), back_inserter(res));
	return res;
}

class InternetSecurity {
public:
	vector <string> determineWebsite(vector <string> addr, vector <string> key, vector <string> dan, int thr) {
		vector <string> res;
		int r[50]={0};
		vector <vector <string> > k;
		set <string> d;
		int n=addr.size();
		
		for(int i=0; i<n; i++) k.push_back(strspl<string>(key[i]));
		for(int j=0; j<(int)dan.size(); j++) d.insert(dan[j]);

		bool cont=true;
		while(cont) {
			cont=false;
			for(int i=0; i<n; i++) {
				if(r[i]) continue;
				int cnt=0;
				set <string>::iterator ssi;
				for(ssi=d.begin(); ssi!=d.end(); ssi++) {
					if(find(k[i].begin(), k[i].end(), *ssi)!=k[i].end()) cnt++;
				}
				if(cnt>=thr) {
					cont=true;
					r[i]=1;
					for(int j=0; j<(int)k[i].size(); j++) {
						d.insert(k[i][j]);
					}
				}
			}
		}

		for(int i=0; i<n; i++) {
			if(r[i]) res.push_back(addr[i]);
		}
		return res;
	}
};

SRM480 Div1 450 NetworkSecurity

| 21:31 | SRM480 Div1 450 NetworkSecurity - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM480 Div1 450 NetworkSecurity - SRM diary(Sigmar) SRM480 Div1 450 NetworkSecurity - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→最小カット・・?じゃないですね

→何か、よくわからないなあ

→うーん・・・DAGだからトポロジカルソートすれば何かできるのかな

→トポロジカルソートのコードとか書いたことないし・・450だしそんなことしなくても解く方法がありそうな気がする

→とりあえず色々図を書いてみる

→実はサーバに直接つながるエッジにゲートを置けばいいんじゃないか

→そうすれば、それより上位のクライアントは全て条件を満たせる

→ただし、他のクライアントを経由して同じサーバに到達できるところにはゲートを置く必要がない

→これで必要最小限のゲートが置ける・・・うん・・・間違いない

→サーバ毎に隣接するクライアントを列挙し、各クライアントについてBFSで同じサーバに到達できるかチェックする

→計算量も問題ない

→書く→サンプルの最後が合わない

→あ・・・同じサーバじゃなくて、どのサーバにたどり着いてもOKになってた・・・サンプルに助けられた。危なすぎる・・

→サンプル通る→提出

→青い部屋とはいえルーム内1位なんだが・・大丈夫かこのコード。Adhocな解法は不安感を掻き立てる

→うーん・・・やっぱり問題ないとしか思えない・・


チャレンジフェーズ

→怪しげなコードを探す

→クライアントから辿っている人がいるんだが・・これ合わないだろう

→よく見るとうまく書けてる。こんな書き方もあるのか。。

→次の人

→どうみてもサーバの数を数え間違ってる。

→落とせるケースを考えている間に終了・・うーん間に合わなかった


システムテスト

→Passed

→よかった(ほっ


以下、ソースです。

class NetworkSecurity {
public:
	int secureNetwork(vector <string> cc, vector <string> sc) {
		int res=0;
		int ssz=sc[0].size();
		int csz=cc.size();

		for(int i=0; i<ssz; i++) {
			for(int j=0; j<csz; j++) {
				if(sc[j][i]=='N') continue;
				res++;
				int val[50];
				memset(val, -1, sizeof(val));
				queue <int> q;
				int qt;
				q.push(j);
				val[j]=0;
				while(!q.empty()) {
					qt=q.front(); q.pop();
					if(qt!=j) {
						if(sc[qt][i]=='Y') {
							res--;
							break;
						}
					}
					for(int k=0; k<csz; k++) {
						if(cc[qt][k]=='N') continue;
						if(val[k]>=0) continue;
						q.push(k);
						val[k]=val[qt]+1;
					}
				}
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100827