SRM 471 Div2 Practice

[Easy]250 PrimeContainers

問題文

与えられたNを切り捨てながら2で割っていって、操作の途中で何回素数が出てきたか。Nが素数の場合も含む。

解法

素数判定やるだけ。O(N)の素数判定でも、N log Nで間に合う。が、できればO(√N)以下にしたいところ。

bool isprime(int n){ if(n<2)return false;  for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true;} 
class PrimeContainers {
public:
	int containerSize(int N) {
		int ans = 0;
		while(N != 0){
			if(isprime(N))ans++;
			N/=2;
		}
		return ans;
	}
};

[Medium] 500 EllysPlaylists

問題文

タイトルが3文字以上の曲が複数含まれた曲名一覧がある。

なんか、主人公曰くタイトルの終わりの3文字と、始まりの3文字が一致するような曲の合間はスムーズらしい。とりあえず一覧からKコの曲取り出して全体がスムーズなプレイリストを作りたい。条件満たす限り何回曲を使っても良いし、同じ曲が連続しててもいい。作れる組み合わせは何通りある？

解法

明らかに組み合わせ数のDP。

dp[何曲目か][どの曲を選んだか]で、[1000][50]くらいの状態空間に収まる。

1曲目は何でも良いので特別に1で初期化。

#include <vector>
#include <string>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < N ; i++)
class EllysPlaylists {
public:
	int countPlaylists(vector <string> s, int K) {
		int N = s.size();
		long long dp[1001][51] = {0};
		bool ok[50][50] = {0};
		rep(i,N)rep(j,N) if(s[i].substr(s[i].size()-3) == s[j].substr(0,3) )ok[i][j] = true;
		for(int i = 0 ; i < N ; i++)dp[1][i] = 1;
		for(int i = 1 ; i < K ; i++){
			rep(j,N)rep(k,N) if(ok[j][k]) dp[i+1][k] = (dp[i+1][k]+dp[i][j])%1000000007;
		}
		int ans = 0;
		for(int i = 0 ; i < N ; i++) ans = (ans+dp[K][i])%1000000007;
		return ans;
	}
};

[Hard] 1000 Thirteen

問題文

長い。要約すると、

Nコの頂点があります。辺情報が隣接行列で与えられます。

今0番目の頂点にいます。N-1番目の頂点に移動するのに最短でどれだけ掛かりますか。

ただし、迷信深い人が連れにいるので、13で割り切れるようなコストで頂点にたどり着くようなことを許しません。(N-1番目だけじゃなくてどの頂点に対しても)

0番目に0分でいるっていうのは多分いいんでしょう。おわり。

解法

ダイクストラ。ただし、13で割った余りをさらに状態として持つダイクストラ。それが分かれば後は書くだけ。

#include <queue>
#include <vector>
#include <string>
using namespace std;


struct NODE{
	int to,cost;
	NODE(int a,int b){to = a , cost = b;}
};
bool operator < (const NODE &a , const NODE &b){
	return a.cost > b.cost;
}

int g(char c){
	if(c >= 'a') return 27 + c - 'a' ;
	else return 1 + c - 'A';
}

class Thirteen {
public:
	int calcTime(vector <string> city) {
		bool done[50][13] = {0};
		priority_queue<NODE> Q; 
		Q.push(NODE(0,0));
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if(done[q.to][q.cost%13])continue;
			else done[q.to][q.cost%13] = true;
			if(q.cost%13 == 0 && q.cost != 0) continue;
			if(q.to == city.size() - 1) return q.cost;
			
			for(int i = 0 ; i < city.size() ; i++){
				if(city[q.to][i] != '#') Q.push(NODE(i,q.cost+g(city[q.to][i])));
			}
		}
		return -1;
	}
};