Member SRM 471

今さらですが、解答だけあっぷろーど。

PrimeContainers

与えられた数字Nを1になるまで、繰り返し2で割る。余りが出たら切り捨てる。
計算中にいくつ素数が現れるか。

class PrimeContainers {

public:
	int containerSize(int N) {
		int count = 0;

		for(; N!=1; N = N/2){
			int j=2;
			for(; j*j<=N; j++){
				if(N%j ==0) break;
			}
			if(j*j>N) count++;
		}

		return count;
	}

};

EllysPlaylists

複数の曲の題名が与えられる。曲のプレイリストを作りたい。
プレイリストの曲は全て、ある曲の題名の後ろ３文字と次に流れる曲の題名の始め３文字が完全に一致しなくてはならない。
同じ曲を何度でも用いてよい。
プレイリストの組み合わせは何種類あるか。1000000007組み合わせを超える場合は、その余りを示せ。

class EllysPlaylists {

	public: int countPlaylists(vector<string> songs, int K) {
		vector<vector<bool> > edge(songs.size(),vector<bool>(songs.size(),false));

		for(unsigned int i=0; i<songs.size(); i++){
			for(unsigned int j=0; j<songs.size(); j++){
				if(songs[i].substr(songs[i].size()-3,3) == songs[j].substr(0,3)){
					edge[i][j] = true;
				}
			}
		}

		vector<int> count((int)songs.size(),1);
		vector<int> tmp;

		for(int i=2; i<=K; i++){
			for(unsigned int k=0; k<songs.size();k++){

				int temp = 0;
				for(unsigned int l=0; l<songs.size(); l++){
					if(count[l]!=0){
						if(edge[l][k]){
							temp += count[l];
							if(temp > 1000000007 ) temp -= 1000000007;
						}
					}
				}
				tmp.push_back(temp);
			}

			count.swap(tmp);
			tmp.clear();
		}

		int ans = 0;
		vector<int>::iterator it = count.begin();
			while( it != count.end() )
			{
				ans += *it;
				if(ans > 1000000007 ) ans -= 1000000007;
				it++;
			}
		return ans;
	}
};