CTU 2017

문제 : https://www.acmicpc.net/category/detail/1781

CTU Open Contest, 2017

https://codeforces.com/gym/101670

Dashboard - 2017-2018 CTU Open Contest - Codeforces

22/05/18 팀연습이었지만 이제.. 포스팅을 올리게 되었다.

GYM에 있어서 GYM에서 진행하였다.

혼자 생각해내기보다 같이 생각하고 구현은 직접 많이 안했던 것 같다. (= 아이디어만 내고 두 세 문제정도를 직접 푼 것 같다)

CTU의 특이한점은 옛날 방식을 고수하는건지, input을 EOF까지 받아야 했다.

 

A. Amusement Anticipation

문제

끝에서 시작해서 등차수열이 아니게 되는 첫 인덱스를 출력해야한다.

 

풀이

Naive하게 하나씩 돌아보면 된다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1007;
int a[N];
int main() {
	for(int n, k;~scanf("%d",&n);){
		for(int i=0;i<n;++i) scanf("%d",&a[i]);
		if(n<3) {printf("1\n");continue;}
		for(k=n-3; k>=0 && (a[k]-a[k+1]==a[k+1]-a[k+2]); --k);
		printf("%d\n",k+2);
	}
}

 

B. Pond Cascade

문제

그릇이 일렬로 있다. 모든 그릇에 동시에 수도꼭지가 열려서 k만큼 물이 쏟아진다. 위쪽 그릇의 물이 넘치면 아래로 넘친 양만큼 더 흐른다. 마지막 그릇이 넘치기 시작하는 시점과 모든 그릇이 다 차는 시점을 구하라.

 

풀이

연습 중에 아이디어를 떠올리고 구혔했는데 맞왜틀하다가 업솔빙에 성공하였다.

priority queue와 union find를 사용했는데, 그릇이 다 차는데 걸리는 시간이 가장 작은걸 높은 우선순위로 해서 채워나가면서 다음 그릇(찾는걸 union find로 함)에 현재 그릇 flow를 넘겨주고 시간을 업데이트해서 priority queue에 다시 넣어준다. 채워진 그릇이 마지막 그릇이었다면 시간을 체크하고, 모든 그릇이 채워졌으면 시간을 체크한 후 출력한다.

 

소스코드

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int MAX = 100007;
int R[MAX], V[MAX];
double C[MAX], f[MAX], T[MAX];
priority_queue<pair<double, int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;

int uf(int c) {
	if (c == R[c]) return c;
	return R[c] = uf(R[c]);
}

int main() {
	//freopen("in", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
	int N; double F;
	for (;~scanf("%d%lf",&N,&F);) {
		for (int i = 0; i < N; ++i) {
			scanf("%lf",&C[i]);
			V[i] = 0;
			R[i] = i;
			T[i] = 0;
			f[i] = F;
			pq.push({ C[i]/f[i],i });
		}
		R[N]=N;
		double e_time=0, t_time=0; // end, total
		while(!pq.empty()) {
			auto [t, i] = pq.top(); pq.pop();
			//printf("%lf %d\n",t,i);
			if(V[i]) continue;
			V[i]=1;
            if(i == N || f[i] <= 0) continue;
			if (i == N - 1) e_time = t;
			t_time = max(t_time,t);
			int j = R[i] = uf(i + 1);
			if (j >= N) continue;
			C[j] -= (t-T[j]) * f[j];
			f[j] += f[i];
			T[j] = t;
			//printf("%lf %lf %d\n",t+C[j]/f[j],C[j],i);
			pq.push({ t+C[j]/f[j],j });
		}
		printf("%.8lf %.8lf\n",e_time,t_time);
	}
	return 0;
}

 

C. Chessboard Dancing

문제

King Rook Bishop Knight 4가지 말에 대해서 i종류 말이 이동할 수 있는 다른 위치에 같은 종류의 말이 있으면 안될 때, 각 그리드 크기에 대해서 말 종류의 최소 개수를 구하여라.

 

풀이

에디토리얼 풀이 그림이 깔끔하여 인용했다.

룩    | 킹

비숍 | 나이트 순서이다.

Bishop	Knight

 

소스코드

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
int main(){
	int n;
	for(char c;~scanf("%d %c",&n,&c);){
		if(c=='N') printf("%d\n",(n>2)+1);
		else if(c=='R') printf("%d\n",n);
		else if(c=='B') printf("%d\n",n);
		else if(c=='K') printf("%d\n",3*(n>1)+1);
	}
	
}

 

D. Equinox Roller Coaster

문제

점들이 주어질 때 변이 x, y축에 평행한 가장 큰 정사각형을 구하라.

 

풀이

점 개수가 많은 편이다. 연습 중에 떠올린 풀이가 설마 정해겠어~ 했는데 정해였다.

임의의 점 i에 대해서 i의 x축 또는 y축에 놓인 점의 개수 중 작은 값의 방향으로 점들을 확인한다.

각 점에 대한 worst case는 N/2개의 점이 있을 수 있지만 모든 점에 대한 평균의 worst case는 sqrt N개이다.

즉, map 등의 자료구조를 사용하면 O(N sqrt N log n)에 구할 수 있다.

 

소스코드

#include <bits/stdc++.h>
#define first x
#define second y
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll N = 100007;
int main() {
	for (ll n; ~scanf("%lld", &n);) {
		vector<pii> pt(n);
		map<ll, vector<pii>> mpx, mpy;
		map<pii, bool> mp;
		for (ll i = 0; i < n; ++i) {
			ll x, y;
			scanf("%lld %lld", &x, &y);
			mpx[x].push_back({ x,y });
			mpy[y].push_back({ x,y });
			pt[i] = { x,y };
			mp[{x, y}] = 1;
		}
		sort(pt.begin(), pt.end());
		ll prevx = -2e9, lx, mx = 0;
		for (auto& [x, y] : pt) {
			if (x != prevx) prevx = x, lx = mpx[x].size();
			if (lx > n / lx) {
				for (auto& [X, Y] : mpy[y]) {
					ll r = abs(x - X);
					if (r <= mx) continue;
					if (x < X && mp[{x, y + r}] && mp[{x + r, y + r}]) mx = r;
					else if (x >= X && mp[{x, y - r}] && mp[{x - r, y - r}]) mx = r;
				}
			}
			else {
				for (auto& [X, Y] : mpx[x]) {
					ll r = abs(y - Y);
					if (r <= mx) continue;
					if (y < Y && mp[{x + r, y}] && mp[{x + r, y + r}]) mx = r;
					else if (y >= Y && mp[{x - r, y}] && mp[{x - r, y - r}]) mx = r;
				}
			}
		}
		printf("%lld\n", mx);
	}
}

 

E. Forest Picture

문제

숲을 그리는 구현 문제인걸로 기억하지만 자세하게 기억나지 않는다..

 

F. Shooting Gallery

문제

가장 두꺼운 괄호쌍의 개수를 찾는 문제라고 생각할 수 있다.

 

풀이

n^2 DP를 이용한 풀이를 작성했지만 gym에서는 A/C, boj에서는 W/A이다.

업솔빙 예정

 

G. Ice cream samples

문제

아이스크림 가게가 원형으로 배치되어있다.

각 아이스크림 가게에는 여러개의 아이스크림을 팔고 있다.

연속된 아이스크림 가게의 모든 아이스크림을 살 때, 모든 종류의 아이스크림을 살 수 있는 가장 작은 연속된 길이를 출력하라.

 

풀이

투포인터를 이용하여 풀 수 있는 문제다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
const int N = 1000007;
int c[N];
vector<int> e[N];
int main() {
	for(int n, k;~scanf("%d%d",&n,&k);){
		for(int i=1; i<=k; ++i) c[i]=0;
		for(int i=0, m; i<n; ++i){	
			scanf("%d",&m);
			e[i].clear(), e[i].resize(m);
			for(auto& t:e[i]) scanf("%d",&t);
		}
		int ans=2e9;
		for(int L=0, R=-1, cc=0, cans=0; L<n; ++L){
			int l=0, ch=0;
			while(cc!=k){
				if(++l>n+1) {ch=1; break;}
				R=(R+1)%n;
				for(auto&t:e[R]){
					if(!c[t]++) ++cc;
					++cans;
				}
			}
			if(ch) break;
			ans=min(ans,cans);
			for(auto&t:e[L]){
				if(!--c[t]) --cc;
				--cans;
			}
			if(L==R){
				R=(R+1)%n;
				for(auto&t:e[R]){
					if(!c[t]++) ++cc;
					++cans;
				}
			}
		}
		printf("%d\n",ans==2e9?-1:ans);
	}
}

 

H. Dark Ride with Monsters

문제

주어진 수열을 최소한의 swap으로 오름차순 수열로 바꿀 때 그 횟수를 구하여라

 

풀이

간단하게 범위 [i,n]에 대해서 i에 있어야 할 값이 위치 j에 있다면 swap(i,j)를 하고 [i+1,n]을 확인하면 된다.

 

소스코드

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 200007;
int a[N], b[N];
int main(){
	for(int n;~scanf("%d",&n);){
		int p=0;
		for(int i=1; i<=n; ++i) scanf("%d",&a[i]), b[a[i]]=i;
		for(int i=1, j; i<n; ++i){
			if(a[i]!=i){
				j = b[i];
				swap(b[i],b[a[i]]);
				swap(a[i],a[j]);
				++p;
			}
		}
		printf("%d\n",p);
	}
}

 

I. Go Northwest!

 

J. Punching Power

문제

점들이 주어질 때 최대한 많은 punching machine을 해당 점에 놓으려고 한다. 단, 1가지 조건이 있다.

임의의 machine에 대해 거리 1.3이내에는 다른 machine을 설치할 수 없다.

놓을 수 있는 punching machine의 최대값을 구하라.

 

풀이

Grid에서 가장 짧은 거리는 1 그 다음은 1.414..이므로 인접하게 놓지만 않으면 된다.

이분매칭을 사용하여 해결할 수 있다.

 

K. Treetop Walkway

문제

단방향 그래프가 주어진다.

임의의 간선을 더 연결하여 모든 정점 쌍 (i, j)에 대해 i->j 경로가 존재하도록 만들어라.

 

풀이

풀이는 쉽게 생각할 수 있어보이지만 사용되는 방법이 복잡하다.

SCC를 구하여 DAG Forest를 만들 수 있다.

1. 각 DAG Tree의 root들과 tail들에 대해서 대표 root, leaf 1개씩을 고르고, 인접한 forest를 cycle을 이루도록 연결한다.

수업들으면서 그림판으로 그린 cycle

2. 남은 roots, leafs들끼리 최대한 쌍을 이루고, 남은 roots 혹은 leafs는 아무 leaf 혹은 root에 연결한다.

 

사용되는 알고리즘이 어려워 티어가 높을 것 같다.