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
複数の曲の題名が与えられる。曲のプレイリストを作りたい。
プレイリストの曲は全て、ある曲の題名の後ろ3文字と次に流れる曲の題名の始め3文字が完全に一致しなくてはならない。
同じ曲を何度でも用いてよい。
プレイリストの組み合わせは何種類あるか。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; } };