SRM 236

練習です．

Massive Number(Div2 Easy)

指示通りに比較する

class MassiveNumbers {

	public:
	typedef pair<int,int> P;
	P get(string s){
		int a,b;
		sscanf(s.c_str(),"%d^%d",&a,&b);
		cout<<a<<","<<b<<endl;
		return P(a,b);
	}
	double calc(P a){
		return (double)a.second*log(a.first);
	}
	string getLargest(string numberA, string numberB) {
		P a=get(numberA);
		P b=get(numberB);
		if(calc(a)>calc(b))return numberA;
		return numberB;
	}
};

BusinessTasks(Div2 Medium,Div1 Easy)

問題文通りにシミュレートする

class BusinessTasks {
	public: string getTask(vector<string> list, int n) {
		int now=0;
		while(list.size()>1){
			now+=n-1;
			now%=list.size();
			list.erase(list.begin()+now);
		}
		return *list.begin();
	}
};

ComputerExpert(Div2 Hard)

文字列の集合が収束するまで回す．
split関数あたりを作っておくと楽に書けそう．

void solve(set<string> &a,const string &rule){
	string left,right;
	right=rule.substr(rule.find("->")+3);
	left=rule.substr(0,rule.find("->")-1);
	if(a.count(right)>0)return;//必要無い
	//次のカンマまで読み出す
	while(left.size()>0){
		string tmp;
		REP(i,left.size()){
			if(left[i]==','){
				left=left.substr(i+1);
				break;
			}
			tmp.push_back(left[i]);
		}
		if(tmp==left)left="";
		//OR
		bool ok=false;
		while(tmp.size()>0){
			string tar;
			REP(i,tmp.size()){
				if(tmp[i]=='/'){
					tmp=tmp.substr(i+1);
					break;
				}
				tar.push_back(tmp[i]);
			}
			if(tmp==tar)tmp="";
			if(a.find(tar)!=a.end()){
				ok=true;
				break;
			}
		}
		if(!ok)return;
	}
	a.insert(right);
}
class ComputerExpert {
	public: vector<string> operate(vector<string> facts, vector<string> rules) {
		set<string> ss;
		REP(i,facts.size()){
			ss.insert(facts[i]);
		}
		REP(i,100){
			show(ss);
			REP(j,rules.size()){
				solve(ss,rules[j]);
			}
		}
		vector<string> ans;
		REP(i,facts.size()){
			ss.erase(facts[i]);
		}
		FOR(it,ss){
			ans.push_back(*it);
		}
		return ans;
	}
};

HammingNumber(Div1 Medium)

ハミングDPをする

const lli MAX=2147483647;
typedef pair<int,lli> P;
class HammingNumbers {
	public: int getNumber(vector<int> factors, int n) {
		vector<lli> ans(n+1);
		vector<P> dp(factors.size());
		REP(i,factors.size()){
			dp[i]=P(0,factors[i]);
		}
		ans[0]=1;
		for(int i=1;i<=n;i++){
			//一番小さい要素を得る
			lli MIN=1e15;
			REP(j,factors.size()){
				MIN=min(MIN,dp[j].second);
			}
			ans[i]=MIN;
			if(n==15)cout<<ans[i]<<endl;

			REP(j,factors.size()){
				if(MIN==dp[j].second){
					dp[j].first++;
					dp[j].second=ans[dp[j].first]*factors[j];
				}
			}
		}
		REP(i,n){
			if(ans[i]>MAX)return -1;
		}
		return ans[n-1];
	}
};

Parking(Div1 Hard)

ある時間Tで全ての車がどこかの駐車場に行けるかどうかは二部マッチングで求めることが出来る
時間Tを二分探索で求める．

typedef pair<int,int> P;
int dx[4]={1,0,-1,0},
	dy[4]={0,1,0,-1};
int W,H;
vector<int> BFS(int x,int y,vector<string> &MAP,vector<P> &parks){
	vector<int> dist(parks.size(),-1);
	vector<vector<int> > d(W,vector<int>(H,999999));
	d[x][y]=0;
	queue<P> que;
	que.push(P(x,y));
	while(!que.empty()){
		P now=que.front();que.pop();
		if(MAP[now.first][now.second]=='P'){
			REP(i,parks.size()){
				if(parks[i]==now){
					dist[i]=d[now.first][now.second];
				}
			}
		}
		REP(i,4){
			int nx=now.first+dx[i],
				ny=now.second+dy[i];
			if(nx>=0&&ny>=0&&nx<W&&ny<H){
				if(MAP[nx][ny]=='X')continue;
				if(d[nx][ny]>d[now.first][now.second]+1){
					d[nx][ny]=d[now.first][now.second]+1;
					que.push(P(nx,ny));
				}
			}
		}
	}
	return dist;
}
typedef vector<int> Edges;
typedef vector<Edges> Graph;
bool dfs(const Graph &G,int v,vector<int> &match,vector<bool> &used){
	if(v<0)return true;
	for(int i=0;i<(int)G[v].size();i++){
		int src=v,dst=G[v][i];
		if(used[dst])continue;
		used[dst]=true;
		if(dfs(G,match[dst],match,used)){
			match[src]=dst;
			match[dst]=src;
			return true;
		}
	}
	return false;
}
int bipartite_matching(const Graph &G,int L){
	int res=0;
	vector<int> match(G.size(),-1);
	for(int i=0;i<L;i++){
		vector<bool> used(G.size(),false);
		if(dfs(G,i,match,used))res++;
	}
	return res;
}
class Parking {
public:
	int minTime(vector<string> park) {
		vector<string> &MAP=park;
		W=park.size();H=park[0].size();
		vector<P> cars,parks;
		REP(x,W)REP(y,H){
			if(MAP[x][y]=='C'){
				cars.push_back(P(x,y));
			}
			if(MAP[x][y]=='P'){
				parks.push_back(P(x,y));
			}
		}
		vector<vector<int> > mindist;
		REP(x,W)REP(y,H){
			if(MAP[x][y]=='C'){
				mindist.push_back(BFS(x,y,MAP,parks));
			}
		}
		int low=-1,high=99999999;
		while(low+1<high){
			int mid=(low+high)/2;
			Graph G(cars.size()+parks.size());
			REP(i,cars.size()){
				REP(j,parks.size()){
					if(mindist[i][j]!=-1&&mindist[i][j]<=mid){
						G[i].push_back(cars.size()+j);
					}
				}
			}
			if(bipartite_matching(G,cars.size())==(int)cars.size()){
				high=mid;
			}else{
				low=mid;
			}
		}
		if(high>9999999)return -1;
		return high;
	}
};