SRM 451 Div2

250 ReverseMagicalSource

やるだけ☆ぷろぶれむ。

class ReverseMagicalSource {
public:
	int find(int source, int A) {
		int t = 0 , k = 1;
		while(1){
			t += source * k;
			k *= 10;
			if(t > A)return t;
		}
	}
};

500 BoredPhilosophers

N人居て、1番目の人(1-indexed)は1単語連続した言葉でユニークなものの数数えて、

2番目の人は2単語連続した言葉でユニークなものの数数えて、

3番目の人は3単語連続した言葉でユニークなものの数数えて・・・って感じ。

多分愚直にやればよい。

class BoredPhilosophers {
public:
	vector <int> simulate(vector <string> text, int N) {
		vector <int> ret;
		string s;
		rep(i,text.size())s+=text[i];
		vector<string> data;
		stringstream ss(s);
		while(ss >> s) data.push_back(s);
		int n = data.size();
		for(int sz=1;sz<=N;sz++){
			set< deque<string> > get;
			deque<string> cur;
			rep(i,sz)cur.push_back(data[i]);
			get.insert(cur);
			rep(i,n-sz){
				cur.pop_front();
				cur.push_back(data[i+sz]);
				get.insert(cur);
			}
			ret.push_back(get.size());
		}
		return ret;
	}
};

1000 PizzaDelivery

なんか英文よく分からない。

ピザ屋さんが2人の配達人を雇っていて、

その二人が制約に基づいて上手く届け先に配達しまくった時、最後に配達し終わるまでの時間を求めよ。(一回配る毎にお店に戻るけど、最後は戻らなくて良い。)

2人は同じ時間軸で別々に動くことが出来る。みたいな問題。

移動元か移動先が{配達先・ピザ屋}の場合はコスト2で移動できて、

それ以外は、建物の高さの差が1以下なら移動できる。

1ならコスト3 , 0 なら　コスト1かかる。

まずダイクストラでピザ屋から全ての地点への最短距離を求めてから、

ビット使って2人の配るお店を分担して、最終的な経過時間が最小になるようなケースを求めた。

#define INF (1<<24)
struct P{
	int x,y;
	P(int a,int b){x = a , y = b;}
};
struct NODE{
	int x,y,depth;
	NODE(P a,int c){
		x = a.x , y = a.y ,depth = c;
	}
};
bool operator <(const NODE &a,const NODE &b){
	return a.depth > b.depth;
}
int get(char a,char b){
	if(a=='$'||b=='$'||a=='X'||b=='X') return 2;
	if(abs(a-b) == 1)return 3;
	else if(abs(a-b) == 0)return 1;
	else return -1;
}
class PizzaDelivery {
public:
	int deliverAll(vector <string> d) {
		int ret = 0;
		int done[50][50];
		rep(i,50)rep(j,50)done[i][j] = -1;
		priority_queue<NODE> Q;
		P s(0,0);
		vector<P> pos;
		rep(i,d.size())rep(j,d[0].size()){
			if(d[i][j]=='X'){
				s = P(j,i);
			}else if(d[i][j]=='$'){
				pos.push_back(P(j,i));
			}
		}
		Q.push(NODE(s,0));
		int dx[] = {-1,0,1,0} , dy[] = {0,1,0,-1};
		while(Q.size()){
			NODE q = Q.top(); Q.pop();
			if(~done[q.y][q.x])continue;
			else done[q.y][q.x] = q.depth;
			rep(i,4){
				P t(q.x+dx[i],q.y+dy[i]);
				if(t.y < 0 || t.y >= d.size() || t.x < 0 || t.x >= d[0].size()) continue;
				char a = d[q.y][q.x] , b = d[t.y][t.x];
				if(get(a,b) == -1) continue;
				Q.push(NODE(t,q.depth+get(a,b))	);
			}
		}
		int ans = INT_MAX;
		int N = pos.size();
		rep(i,pos.size()) if(done[pos[i].y][pos[i].x] == -1) return -1;
		rep(bit,1<<N){
			int s[2]={0},mx[2]={0};
			rep(i,N){
				s[!!((1<<i) & bit)] += done[pos[i].y][pos[i].x] * 2;
				mx[!!((1<<i) & bit)] = max(mx[!!((1<<i) & bit)],done[pos[i].y][pos[i].x]);
			}
			ans = min(ans,max(s[0]-mx[0],s[1]-mx[1]));
		}
		return ans;
	}
};