티스토리 뷰

카테고리 없음

BAPC 2017

[gunwookim] 2020. 5. 5. 11:28

놀고만 있던 저에게 urd05가 셋을 돌자고 제안을 했다.

그 셋은 바로 BAPC 2017

같이 푸는거라 그나마 재미가 더 있었다!

5시간동안 했는데, 너무 힘들었다. (오랜만에 몇시간 연속으로 코딩..)

 

간략하게 내가 아는 풀이를 적어보겠다!

 

B - Amsterdam Distance

 

15003번: Amsterdam Distance

Your friend from Manhattan is visiting you in Amsterdam. Because she can only stay for a short while, she wants to see as many tourist attractions in Amsterdam in as little time as possible. To do that, she needs to be able to figure out how long it takes

www.acmicpc.net

플랫이 슥삭해서 나는 모른다.

 

C - Collatz Conjecture

 

15005번: Collatz Conjecture

In 1978 AD the great Sir Isaac Newton, whilst proving that P is a strict superset of N P, defined the Beta Alpha Pi Zeta function f as follows over any sequence of positive integers a1, . . . , an. Given integers 1 ≤ i ≤ j ≤ n, we define f(i, j) as gcd(ai,

www.acmicpc.net

플랫이 최적화 어쩌구 저쩌구 하면서 추하게 뭘 엄청 박았다.

난 뭔지 모른다.

 

D - Detour

 

15006번: Detour

After last year’s edition of the BAPC, you are still stuck in Delft. In order to participate again this year, you are going to Amsterdam by bus. During the journey you look out of the window and look for traffic signs that point in the direction of Amsterd

www.acmicpc.net

다익스트라를 짯는데 틀렸습니다가 나왔다.

플랫이 뭘 더 어떻게 슥삭슥삭 하면 나온다고 하고 슥삭했다.

 

F - Falling Apart

 

15008번: Falling Apart

After acquiring a new integer and showing it off to other couples at a cocktail party, Alice and Bob headed home for a good night of sleep. As their integer was quite large, they were forced to carry it together. Then, on the Boole Boulevard, right by the

www.acmicpc.net

내림차순 정렬후 A_1+A_3+A_5+... , A_2+A_4+A_6+... 를 출력하면 된다.

 

H - Manhattan Morning

 

15015번: Manhattan Mornings

As a New Yorker you are always very busy. Apart from your long work day you tend to have a very long list of errands that need to be done on any particular day. You really hate getting up early so you always end up going over your to-do list after work, bu

www.acmicpc.net

대회때 3팀 밖에 풀지 못했는데, 내 생각에는 뒤에 있는 문제는 더 어려울 것이라 생각해서 앞에 문제들을 잡고 있다가 못 본거 같다.

 

sx < ex, sy < ey 이라면, (sx,sy) -> (ex,ey) 로 갈때 심부름 들을 x좌표로 정렬하면

가장 긴 증가하는 부분 수열 을 구하는 문제가 된다! 

이때 조심해야 할 점은, y좌표가 같은 경우에도 가능하다.

즉, A가 가장 긴 증가하는 부분 수열이라고 하면, 어떤 i에 대해 A_i <= A_i+1 이여야 한다.

x좌표로 정렬하고 좌표 압축을 한 후에 lis를 구하면 된다.

이때 조심해야 할 점은, x좌표가 같다면 y좌표가 작은 것 부터 넣는다.

sx > ex, sy > ey 인 경우에도 똑같다. 

 

이제, sx < ex, sy > ey 인 경우에는 생각해보면

가장 긴 감소하는 부분 수열을 구하는 문제가 된다!

sx > ex, sy < ey 인 경우에도 똑같다.

이것도 똑같은 방법으로 한다.

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
int n;
int sx,sy,ex,ey;
pi a[100005];
vector <int> rex;
vector <int> rey;
vector <int> num[100005];
vector <int> lis;
int b[100005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> sx >> sy >> ex >> ey;
	int rn = 0,v = 0;
	if(sx > ex) swap(sx,ex),swap(sy,ey);
	if(sy > ey) {
		v = 1;
		swap(sy,ey);
	}
	for(int i = 1;i <= n;i++) {
		int x,y;
		cin >> x >> y;
		if(x < sx||x > ex||y < sy||y > ey) {
			rn++;
			continue;
		}
		a[i-rn] = {x,y};
		rex.push_back(x);
		rey.push_back(y);
	}
	n -= rn;
	sort(rex.begin(),rex.end()); rex.erase(unique(rex.begin(),rex.end()),rex.end());
	sort(rey.begin(),rey.end()); rey.erase(unique(rey.begin(),rey.end()),rey.end());
	for(int i = 1;i <= n;i++) {
		a[i].x = lower_bound(rex.begin(),rex.end(),a[i].x)-rex.begin()+1;
		a[i].y = lower_bound(rey.begin(),rey.end(),a[i].y)-rey.begin()+1;
		num[a[i].x].push_back(a[i].y);
	}
	int g = 0;
	for(int i = 1;i <= n;i++) {
		if(!v) sort(num[i].begin(),num[i].end());
		else sort(num[i].rbegin(),num[i].rend());
		for(int j : num[i]) {
			b[++g] = j;
		}
	}
	if(!v) {
		lis.push_back(b[1]);
		for(int i = 2;i <= n;i++) {
			if(lis.back() <= b[i]) lis.push_back(b[i]);
			else lis[upper_bound(lis.begin(),lis.end(),b[i])-lis.begin()] = b[i];
		}
	}
	else {
		lis.push_back(b[n]);
		for(int i = n-1;i >= 1;i--) {
			if(lis.back() <= b[i]) lis.push_back(b[i]);
			else lis[upper_bound(lis.begin(),lis.end(),b[i])-lis.begin()] = b[i];
		}
	}
	if(n == 0) cout << 0;
	else cout << lis.size();
}

 내 코드는 뒤에서 부터 가장 긴 증가하는 부분 수열을 구하는 걸로 바꿨다.

 

J - Irrational Division

 

15011번: Irrational Division

Your family has been blessed with chocolate! A huge piece of chocolate has been given to you and your sister to share. However, as you gobbled up the large majority last time, your parents have invented a game to keep things fair (and to keep you occupied

www.acmicpc.net

 

케이스 분류를 해보자.

 

i) p = 1

이때는 내가 맘대로 자를 수 있다.

그래서 q가 홀수 일때는, 그냥 다 가져가는게 이득이고 (답 : 1)

짝수 일때는, 1개빼고 다 가져가는게 이득이다. (답 : 2)

 

ii) q = 1

이때는 여동생이 모든걸 가져가는 것만이 최소이므로

가 홀수 일때 (답 : 1)

짝수 일때 (답 : 0) 이다.

 

iii) p > 1, q > 1, p is even

내가 어떻게 가져가도 여동생이 남은 모든걸 가져가면 둘다 0이 된다. (답 : 0)

 

iV) p > 1, q > 1, p is odd, q is odd

내가 홀수개의 열을 끊는다고 하면, 여동생이 남은걸 다 가져가 버린다. (나 : 1, 여동생 : 0)

짝수개의 열을 끊는다고 하면, 여동생이 남은걸 다 가져가 버린다. (나 0 : 여동생 : 1)

그러므로 답은 1이다.

 

V) p > 1, q > 1, p is odd, q is even

최적의 방법으로 플레이 할때는 맨 처음 내가 한줄 가져가고

그 다음 서로 2줄씩 가져가는 것이다.

그러면, 먼저 2줄을 가져갈 수가 없는 사람에 따라 결과가 달라진다.

 

ㄱ) 내가 가져갈 수가 없는 경우 (p >= q)

여동생이 1개빼고 다 가져가면, 나는 0점, 여동생도 0점이 된다. (답 : 0)

 

ㄴ) 여동생이 가져갈 수가 없는 경우 (p < q)

내가 1개빼고 다 가져가면, 나는 1점, 여동생은 -1점이 된다. (답 : 2)

 

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

int main() {
	int p,q;
	cin >> p >> q;
	if(p == 1) cout << 2-q%2;
	else if(q == 1) cout << p%2;
	else {
		if(p % 2 == 0) cout << 0;
		else if(q % 2) cout << 1;
		else cout << 2*(p < q);
	}
}

 

L - King of the Waves

 

15013번: King of the Waves

You are organising a king of the hill tournament, the Buenos Aires Paddleboarding Competition (BAPC), with n participants. In a king of the hill tournament, one person starts as a “king” and is then challenged by another person, the winning person becomes

www.acmicpc.net

잘 생각을 해보면, A[i][j] 가 1일때, i -> j로 가는 간선을 잇는다.

만드면 이제 루트에서 모든 정점을 갈 수 있는지 판별하자.

만약 모든 정점을 갈 수 있다면, PostOrder 로 선택을 해보면 가능 한 경우가 나온다.

갈 수 없다면, 불가능 하다.

(매우 설명이 부실하다..)

#include <bits/stdc++.h>
using namespace std;
int n,c[1005],cnt;
vector <int> v[1005];
char str[1005];

void dfs(int x,int pr) {
	if(c[x]) return;
	c[x] = 1; cnt++;
	for(int i : v[x]) dfs(i,pr);
	if(pr) cout << x-1 << ' ';
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) {
		cin >> str+1;
		for(int j = 1;j <= n;j++) {
			if(i == j) continue;
			if(str[j] == '1') v[i].push_back(j);
		}
	}
	dfs(1,0);
	if(cnt != n) {
		cout << "impossible";
		return 0;
	}
	memset(c,0,sizeof(c));
	dfs(1,1);
}

 

M - Lemonade Trade

 

15014번: Lemonade Trade

Output a single line containing a single floating point number M, the maximum amount (in litres) of blue lemonade that you can obtain. In case you could obtain more than 10 litres, M is considered to be 10. You are required to output M with absolute precis

www.acmicpc.net

레몬에이드를 적절히 잘 교환해보자.

long double 같은데에 담으면, 최대 2^100000 까지 될 수 있으므로, 담을때 log2 로 담아보자.

그러면, 최대 10만까지 담을 수 있고, 소수차이는 믿음을 가지고 짰는데, 맞아서 기분이 좋았다.

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef pair<int,int> pi;
int n;
map <string,int> name;
string str1,str2;
ld x;
ld ans[100005],INF = 1e18;

struct GG {
	int x,y;
	ld g;

}a[100005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	int g = 2;
	name["pink"] = 1;
	name["blue"] = 2;
	for(int i = 1;i <= n;i++) {
		cin >> str1 >> str2 >> x;
		if(name.find(str1) == name.end()) name[str1] = ++g;
		if(name.find(str2) == name.end()) name[str2] = ++g;
		a[i].x = name[str1];
		a[i].y = name[str2];
		a[i].g = x;
	}
	for(int i = 1;i <= g;i++) ans[i] = -INF;
	ans[1] = log2(1.0);
	for(int i = 1;i <= n;i++) {
		if(ans[a[i].y] == -INF) continue;
		ans[a[i].x] = max(ans[a[i].x],ans[a[i].y]+log2(a[i].g));
	}
	if(ans[2] > log2(10.0)) cout << "10.000000000000000";
	else cout << fixed << setprecision(15) << pow(2.0,ans[2]);
}

 

힘들다 이렇게 BAPC 2017 글을 마친다!

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함