読者です 読者をやめる 読者になる 読者になる

SRM502~506 Div1Medium

TopCoder

4日間で100問Div1Medium解くとか言ってしまいましたが、どう考えても無謀だったのでゆっくりMedium解いています。

SRM502 Div1Med(500)
解法:ソートしてDPをする。ソート基準を考える。
久しぶりにこういう問題を見たのでかかる時間だけでソートしてしまい反省。
わざわざ狙ってオーバーフローさせにかかるあたりVasylは悪質だと思う。

#include<algorithm>
#include<vector>
using namespace std;
struct wolf{
	int B;
	int C;
	int D;
};
inline bool operator<(const wolf &a,const wolf &b){
	return (long long)a.C*b.D>(long long)b.C*a.D;
}
class TheProgrammingContestDivOne{
	public:
	long long dp[51][100001];
	wolf v[50];
	int find(int a,vector<int>b,vector<int>c,vector<int>d){
		int n=b.size();
		for(int i=0;i<n;i++){
			v[i].B=b[i];
			v[i].C=c[i];
			v[i].D=d[i];
		}
		std::sort(v,v+n);
		for(int i=0;i<n;i++){
			for(int j=0;j<=a;j++){
				dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
				if(j+v[i].D<=a){
					dp[i+1][j+v[i].D]=max(dp[i+1][j+v[i].D],dp[i][j]+v[i].B-(long long)v[i].C*(j+v[i].D));
				}
			}
		}
		long long ret=0;
		for(int i=0;i<=n;i++)
		for(int j=0;j<=a;j++)ret=max(ret,dp[i][j]);
		return ret;
	}
};

MSRM503 Div1Med(500)
解法:各村別々に考えて、それぞれどの頂点につながるかを確率求める。重要なのは何番目に距離が近いかだけ。
なかなか不安になる解法だけど、TopCoderらしいと思います。

import java.util.*;
public class KingdomXCitiesandVillages{
	
	public double determineLength(int []ax,int[]ay,int[]bx,int[]by){
		int m=ax.length;
		int n=bx.length;
		double ret=0;
		for(int i=0;i<n;i++){
			double Min=99999999;
			for(int j=0;j<m;j++){
				Min=Math.min(Math.sqrt((double)(ax[j]-bx[i])*(ax[j]-bx[i])+(double)(ay[j]-by[i])*(ay[j]-by[i])),Min);
			}
			double c[]=new double[n-1];
			int I=0;
			for(int j=0;j<n;j++){
				if(i!=j){
					c[I++]=Math.min(Min,Math.sqrt((double)(bx[j]-bx[i])*(bx[j]-bx[i])+(double)(by[j]-by[i])*(by[j]-by[i])));
				}
			}
			Arrays.sort(c);
			double now=1;
			for(int j=0;j<n-1;j++){
				ret+=c[j]/(j+1)/(j+2);
				now-=1.0/(j+1)/(j+2);
			}
			ret+=now*Min;
		}
		return ret;
	}
}

SRM504 Div1Med(500)
解法:上から忠実に処理する。2の累乗or0が答えになる。
DPかと思ったらぜんぜんDPじゃなかった。

public class AlgridTwo{
	public int makeProgram(String[]a){
		int m=a.length;
		int n=a[0].length();
		int MOD=1000000007;
		int ret=1;
		for(int i=0;i<m-1;i++){
			int []dat=new int[n];
			for(int j=0;j<n;j++){
				dat[j]=-1;
			}
			for(int j=0;j<n-1;j++){
				if(a[i].charAt(j)=='B'&&a[i].charAt(j+1)=='W'){
					dat[j]=1;
					dat[j+1]=1;
				}
				if(a[i].charAt(j)=='W'&&a[i].charAt(j+1)=='B'){
					dat[j]=0;
					dat[j+1]=0;
				}
				if(a[i].charAt(j)=='B'&&a[i].charAt(j+1)=='B'){
					int c=dat[j];
					dat[j]=dat[j+1];
					dat[j+1]=c;
				}
			}
			boolean ok=true;
			int count=0;
			for(int j=0;j<n;j++){
				if(dat[j]==1&&a[i+1].charAt(j)=='W')ok=false;
				if(dat[j]==0&&a[i+1].charAt(j)=='B')ok=false;
				if(dat[j]!=-1)count++;
			}
			if(!ok)return 0;
			for(int j=0;j<count;j++)ret=(ret+ret)%MOD;
		}
		return ret;
	}
}

MSRM505 Div1Med(500)
(解法:O(√n)くらいになるように上手く処理する?)
大変そう。本番でも40人しか解いてない。

SRM506 Div1Med(600)
解法:車を割り当てるのでフロー
こういう割り当てはどういう風に流せばいいのか(max flow? min cost flow?)迷ってた。フローは練習不足な気がする。
フロー慣れている人なら600というほど難しくなさそうだけど、アルゴリズム自体が難しいので600なのは仕方ないかもしれない。

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdio>
#include<string>
using namespace std;

typedef int Weight;
const Weight INF=99999999;

struct Edge{
	int dst,cap;Weight cost,rev;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

//srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する
void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){
	G[src].push_back((Edge){dst,cap,cost,G[dst].size()});
	G[dst].push_back((Edge){src,0,-cost,G[src].size()-1});
}

//sからtへの流量fの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(Graph &G,int s,int t,int f){
	typedef pair<int,int> P;
	int res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > que;
		vector<Weight> dist(V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();que.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			for(int i=0;i<(int)G[v].size();i++){
				Edge &e=G[v][i];
				if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){
					dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst];
					prevv[e.dst]=v;
					preve[e.dst]=i;
					que.push(P(dist[e.dst],e.dst));
				}
			}
		}
		if(dist[t]==INF){	
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];

		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			Edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
class SlimeXGrandSlimeAuto{
	public:
	int g[50][50];
	int travel(vector<int>a,vector<int>b,vector<string>c,int d,int e){
		int n=c.size();
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=99999999;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if('0'<=c[i][j]&&c[i][j]<='9')g[i][j]=c[i][j]-'0'+1;
				if('a'<=c[i][j]&&c[i][j]<='z')g[i][j]=c[i][j]-'a'+11;
				if('A'<=c[i][j]&&c[i][j]<='Z')g[i][j]=c[i][j]-'A'+37;
			}
			g[i][i]=0;
		}
		for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
		Graph wolf(2+b.size()+a.size());
		int at=0;
		for(int i=0;i<b.size();i++){
			add_edge(wolf,0,2+i,1,0);
			for(int j=0;j<a.size();j++){
				add_edge(wolf,2+i,2+b.size()+j,1,g[at][a[j]]*d+g[a[j]][b[i]]*e);
			}
			add_edge(wolf,2+i,1,1,g[at][b[i]]*d);
			at=b[i];
		}
		for(int i=0;i<a.size();i++)add_edge(wolf,2+b.size()+i,1,1,0);
		return min_cost_flow(wolf,0,1,b.size());
	}
};

Div1Med Solved
22 -> 26 (+4)