SRM 384 250pt: Library

TopCoder

問題概要

所属しているグループ名の集合と、アクセス可能な部屋名の集合と、(書名、部屋名、グループ名)の集合が与えられる。部屋名とグループ名がどちらも集合に含まれるような書名は何通りあるか求める問題。

考えたこと

  • setなりなんなりに突っ込んで調べるだけにしか見えない。
  • コンストラクタ覚えておくと簡潔に書けて非常によろしい。
    • 大抵のコンテナ(含string)のコンストラクタはイテレータ渡すことができる。
    • ところで、stringのコンストラクタstring(size_t, char)は順番をいつも間違えてしまう。
  • ついでに、ある集合にある値が含まれるかどうかってs.count(x)とs.find(x)!=s.end()どっちの書き方がいいんだろう。findの方が意味は分かりやすいけど条件に否定が入っているのがミスを誘発しそう。

practiceで通したコード

計算量O(MAX_LEN * N * log N)くらい。

#include <set>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

struct Library {

	int documentAccess(vector <string> records, vector <string> userGroups, vector <string> roomRights) {
		set<string> rooms(roomRights.begin(), roomRights.end()),
				users(userGroups.begin(), userGroups.end()),
				can_access;

		for(int i=0; i<(int)records.size(); i++){
			stringstream ss(records[i]);
			string doc, room, user;
			ss >> doc >> room >> user;
			if( rooms.find(room) != rooms.end() && users.find(user) != users.end() ){
				can_access.insert(doc);
			}
		}

		return can_access.size();
	}

};