PCK 2015 予選

9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。
1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした)
8ほぼ書き終わってたのに間に合わなくて辛い(TrieでやるとMLEするらしいのでどの道通せてなかったかも)
おそらく4位。去年より順位下がってつらい。

1 やるだけ

int main()
{
	int p,m,c;
	cin >> p >> m >> c;
	cout << p+m+c << endl;
	return 0;
}

2 やるだけ

int h1,h2;
int k1,k2;
int a,b,c,d;
int main()
{
	scanf("%d %d",&h1,&h2);
	scanf("%d %d",&k1,&k2);
	scanf("%d %d %d %d",&a,&b,&c,&d);
	int h = 0,k = 0;
	h = h1*a+h2*b+(h1/10)*c+(h2/20)*d;
	k = k1*a+k2*b+(k1/10)*c+(k2/20)*d;
	if(h>k)printf("hiroshi\n");
	else if(k>h)printf("kenjiro\n");
	else printf("even\n");
	return 0;
}

3 やるだけ

int D,L;
int main()
{
	scanf("%d %d",&D,&L);
	printf("%d\n",(D/L)+(D%L));
	return 0;
}

4 やるだけ

int N;
int a[105];
int main()
{
	memset(a,0,sizeof(a));
	scanf("%d",&N);
	for(int i=0;i<3;i++)
	{
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;j++)
		{
			int val;
			scanf("%d",&val);
			val--;
			a[val]|=(1<<i);
		}
	}
	int ans = 0;
	for(int i=0;i<N;i++)
	{
		//printf("%d %d\n",i,a[i]);
		if(a[i]==7||a[i]==6||a[i]==4)ans++;
	}
	printf("%d\n",ans);
	return 0;
}

5 やるだけ

int N;
int p[105];
int imos[105];
int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",&p[i]);
	for(int i=0;i<N;i++)imos[p[i]]++;
	for(int i=100;i>0;i--)imos[i-1]+=imos[i];
	for(int i=100;i>=0;i--)if(imos[i]>=i)
	{
		printf("%d\n",i);
		return 0;
	}
	return 0;
}

6 やるだけ

int C,N;
char ch[1010][1010];
int f[1010][1010];
bool ok[1010][1010];
int bad = 0;
bool check(int x,int y)
{
	if(f[x][y]==f[x][N-1-y]&&f[x][y]==f[N-1-x][y]&&f[x][y]==f[N-1-x][N-1-y])return true;
	return false;
}
int ans = 0;
int main()
{
	scanf("%d %d",&C,&N);
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> ch[i][j];
		}
	}
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(ch[i][j]=='0')f[i][j]=0;
			else f[i][j]=1;
		}
	}
	int M = N/2; 
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(check(i,j))ok[i][j]=true;
			else
			{
				ok[i][j]=false;
				bad++;
			}
		}
	}
	if(bad==0)ans++;
	for(int i=0;i<C-1;i++)
	{
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;j++)
		{	
			int x,y;
			scanf("%d %d",&x,&y);
			x--;y--;
			f[x][y]^=1;
			if(x>=M)x=N-1-x;
			if(y>=M)y=N-1-y;
			bool d = check(x,y);
			if(d!=ok[x][y])
			{
				if(d)bad--;
				else bad++;
			}
			ok[x][y]=d;
		}
		if(bad==0)ans++;
	}
	printf("%d\n",ans);
	return 0;
}

7 UnionFind使うだけ

const int SIZE = 250000;
struct UnionFind
{
	int par[SIZE];
	void init(int n)
	{
		for(int i=0;i<n;i++)
		{
			par[i] = i;
		}
	}
	int find(int x)
	{
		if(par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x,int y)
	{
		x = find(x);
		y = find(y);
		if(x==y)return;
		if(x > y)par[y] = x;
		else par[x] = y;
	}
	bool same(int x,int y)
	{
		return find(x) == find(y);
	}
}uf;
int N,M,K;
int main()
{
	scanf("%d %d %d",&N,&M,&K);
	//0 N-1 N N+M-1
	uf.init(N+M);
	for(int i=0;i<K;i++)
	{
		int type;
		int a,b,c,x;
		scanf("%d",&type);
		if(type==1)
		{
			scanf("%d %d",&a,&b);
			a--;b--;
			a = uf.find(a);
			b = uf.find(b);
			//cout << a << ' ' << b << endl;  
			if(a>=N&&b>=N&&a!=b)
			{
				printf("%d\n",i+1);
				return 0;
			}
			uf.unite(a,b);
		}
		else
		{
			scanf("%d %d",&c,&x);
			c--;x--;
			c = uf.find(c);
			//cout << c << ' ' << x+N << endl;
			if(c>=N&&c!=x+N)
			{
				printf("%d\n",i+1);
				return 0;
			}
			uf.unite(c,x+N);
		}
	}
	printf("0\n");
	return 0;
}

8 Trieで数えるだけだと思ったけどロリハじゃないと通らないらしい

9 二分探索

#define INF 100000000
using namespace std;
typedef pair<double,double> P;
long long x[100000];
long long r[100000];

double min(double a,double b){return a<b?a:b;}
double max(double a,double b){return a>b?a:b;}

P cross(P a,P b){
	return P(max(a.first,b.first),min(a.second,b.second));
}

bool solve(double w,int n){
	P seg=P(-INF,INF);
	for(int i=0;i<n;i++){
		if(w>r[i])return false;
		double left=x[i]-sqrt(r[i]*r[i]-w*w);
		double right=x[i]+sqrt(r[i]*r[i]-w*w);
		P cseg=cross(seg,P(left,right));
		if(cseg.first>cseg.second)return false;
		else seg=cseg;
	}
	return true;
}

int main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%lld %lld",&x[i],&r[i]);
	double bottom=0,top=1000001;
	for(int bi=0;bi<40;bi++){
		double mid=(bottom+top)/2;
		if(solve(mid,n))bottom=mid;
		else top=mid;
	}
	printf("%.12lf\n",bottom);
	return 0;
}

10 JOI春のオリエンテーリングみたいにトポソして片方先に行かせながらDP

#define INF 1000000000000LL
typedef pair<int,int> P;
vector<P> re[1000];
int cost1[2000];
int cost2[2000];
bool used[1000];
vector<int> ord;
long long dp[1000][1000];
int depth[1000];

long long min(long long a,long long b){return a<b?a:b;}

void dfs(int v){
	used[v]=true;
	for(int i=0;i<re[v].size();i++){
		int u=re[v][i].first;
		if(!used[u])dfs(u);
	}
	ord.push_back(v);
}

int main(){
	int n,m,i,j,k,l;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		int a,b;
		scanf("%d %d %d %d",&a,&b,&cost1[i],&cost2[i]);
		a--;b--;
		re[b].push_back(P(a,i));
	}
	for(i=0;i<n;i++)used[i]=false;
	dfs(n-1);
	for(i=0;i<n;i++)for(j=0;j<n;j++)dp[i][j]=INF;
	dp[ord[0]][ord[0]]=0;
	for(i=0;i<n;i++)depth[ord[i]]=i;
	for(i=0;i<n;i++){
		for(j=i;j<n;j++){
			int u=ord[i];
			int v=ord[j];
			if(u!=v){
				for(k=0;k<re[v].size();k++){
					int w=re[v][k].first;
					int e=re[v][k].second;
					if(depth[u]<=depth[w])dp[u][v]=min(dp[u][v],dp[u][w]+cost1[e]);
					else dp[u][v]=min(dp[u][v],dp[w][u]+cost1[e]);
				}
			}
			else{
				for(k=0;k<re[v].size();k++){
					for(l=0;l<re[v].size();l++){
						int w1=re[v][k].first;
						int e1=re[v][k].second;
						int w2=re[v][l].first;
						int e2=re[v][l].second;
						if(e1==e2)dp[v][v]=min(dp[v][v],dp[w1][w1]+cost1[e1]+cost2[e1]);
						else{
							if(depth[w1]<=depth[w2])dp[v][v]=min(dp[v][v],dp[w1][w2]+cost1[e1]+cost1[e2]);
							else dp[v][v]=min(dp[v][v],dp[w2][w1]+cost1[e1]+cost1[e2]);

						}
					}
				}
			}
		}
	}
	printf("%lld\n",dp[n-1][n-1]);
	return 0;
}