USACO US Open 2016 Contest - Silver

팀 연습용

1시간 설정하고 진행하였다.

무지성 제출만 해서 많이 틀렸었다.

 

1. Field Reduction (Silver)

풀이

좌표 상에서 상하좌우 최대 3개씩 총 12C3가지의 점을 빼는 모든 경우를 확인해보자

소스코드

#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647;
struct po{int x, y, i;};
vector<po> v;
inline bool cmpx(po a,po b){return a.x<b.x;}
inline bool cmpy(po a,po b){return a.y<b.y;}
int main() {
	int n, c=0;
	scanf("%d",&n); v.resize(n);
	for(auto&[x,y,i]:v) scanf("%d%d",&x,&y), i=++c;
	
	set<int> st;
	sort(v.begin(),v.end(),cmpx);
	for(int i=0; i<3; ++i) st.insert(v[i].i), st.insert(v[n-i-1].i);
	sort(v.begin(),v.end(),cmpy);
	for(int i=0; i<3; ++i) st.insert(v[i].i), st.insert(v[n-i-1].i);
	
	int ans=INF;
	for(auto i:st){
		for(auto j:st){
			for(auto k:st){
				if(i==j || j==k || k==i) continue;
				int mnx=INF, mxx=0, mny=INF, mxy=0;
				for(auto w:v){
					if(w.i==i || w.i==j || w.i==k) continue;
					if(mnx>w.x) mnx=w.x;
					if(mny>w.y) mny=w.y;
					if(mxx<w.x) mxx=w.x;
					if(mxy<w.y) mxy=w.y;
				}
				//printf("%d %d %d | %d %d %d %d | %d\n",i,j,k,mxx,mnx,mxy,mny,(mxx-mnx)*(mxy-mny));
				ans=min(ans,(mxx-mnx)*(mxy-mny));
			}
		}
	}
	printf("%d",ans);
}

 

2. Diamond Collector (Silver)

풀이

겹치지 않는 구간 중 2개의 합이 최대인 것을 구한다.

소스코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v, m;
int main() {
	ll n, k;
	scanf("%lld%lld",&n,&k); v.resize(n), m.resize(n);
	for(auto &t:v) scanf("%lld",&t);
	sort(v.begin(),v.end());
	ll ans=0;
	for(ll i=0, j=0; i<v.size(); ++i){	
		while(j<i && v[i]-v[j]>k) ++j;
		ll t=j?m[j-1]:0;
		ans=max(ans,t+i-j+1);
		m[i]=max(t,i-j+1);
	}
	printf("%lld",ans);
}

 

3. Closing the Farm (Silver)

풀이

i번째 점을 제거할 때 아무 점에서나 dfs를 돌았을 때 방문 가능한 점이 n-i개 있으면 YES 아니면 NO

소스코드

#include <bits/stdc++.h>
using namespace std;

int vis[4000];
vector<int> v[4000];

int dfs(int w,int &i){
	if(vis[w]==i || vis[w]==-1) return 0; vis[w]=i;
	int t=1;
	for(auto u:v[w]) t+=dfs(u,i);
	return t;
}

int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	for(int i=0, x, y; i<m; ++i) scanf("%d%d",&x,&y), v[x].push_back(y), v[y].push_back(x);
	for(int i=1, w; i<=n; ++i){
		scanf("%d",&w);
		int t=dfs(w,i);vis[w]=-1;
		puts(t==n-i+1?"YES":"NO");
	}
}