BAPC 2019

플랫과 함께 BAPC 2019 셋을 돌았다.

이번에는 11솔로 끝났다! 만족하는 점수다!

+ 수식 쓰는 법을 배워왔다. 이제 조금더 글이 예뻐질 거다!

 

합쳐서 11솔이다.

 

J - Jazz it Up! (gunwookim, 2분)

 

역시 시작은 gunwookim이다.

2부터 $n$까지 숫자 하나씩 보면서 $ gcd(n,i) = 1 $ 이라면 $i$를 출력한다.

 

#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> pii;
int n;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 2;i < n;i++) {
		if(__gcd(n,i) == 1) {
			cout << i;
			return 0;
		}
	}
	return 0;
}

 

B - Breaking Branches (urd05, 3분)

 

알고리즘 게임이라고 막 징얼징얼 대더니 이건가? 하고 proof by ac를 때렸다.

 

F - Find my Family (urd05, 15분)

 

내가 F 잡는다고 했는데 플랫이 잘못 들은 모양이다. F를 풀고 나니 이미 플랫이 풀어 있었다.

플랫은 $set$을 이용해 풀었다고 했는데, 나는 $segment$  $tree$를 사용했다.

맨 뒤부터 하나씩 업뎃하며 $a[i]$ 보다 작은 값 중 가장 인덱스가 작은거 하나 고르고($left$라 하겠다), $a[i]$ 보다 큰 값 중 인덱스가 $left$보다 큰 것들중에서 인덱스가 가장 큰 곳을 골라보자($right$라 하겠다).

이제 만족하는 $left$, $right$가 존재한다면, 추가적인 조사를 해봐야 하는 사진이다.

 

#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> pii;
int n,k,m,a[300005],l,r,mn[1200005],mx[1200005];
vector <int> ans;
vector <int> re;

int queryMin(int x,int l,int r,int rl,int rr) {
	if(l > r) return 1e9;
	if(rl > r||l > rr) return 1e9;
	if(rl <= l&&r <= rr) return mn[x];
	int mid = (l + r) >> 1;
	return min(queryMin(x*2,l,mid,rl,rr),queryMin(x*2+1,mid+1,r,rl,rr));
}

int queryMax(int x,int l,int r,int rl,int rr) {
	if(l > r) return -1e9;
	if(rl > r||l > rr) return -1e9;
	if(rl <= l&&r <= rr) return mx[x];
	int mid = (l + r) >> 1;
	return max(queryMax(x*2,l,mid,rl,rr),queryMax(x*2+1,mid+1,r,rl,rr));
}

void update(int x,int l,int r,int wh,int wi) {
	if(l > wh||wh > r) return;
	if(l == r) {
		mn[x] = min(mn[x],wi);
		mx[x] = max(mx[x],wi);
		return;
	}
	int mid = (l + r) >> 1;
	update(x*2,l,mid,wh,wi), update(x*2+1,mid+1,r,wh,wi);
	mn[x] = min(mn[x*2],mn[x*2+1]);
	mx[x] = max(mx[x*2],mx[x*2+1]);
}

void build(int x,int l,int r) {
	if(l == r) {
		mn[x] = 1e9, mx[x] = -1e9;
		return;
	}
	int mid = (l + r) >> 1;
	build(x*2,l,mid), build(x*2+1,mid+1,r);
	mn[x] = 1e9, mx[x] = -1e9;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> k;
	for(int g = 1;g <= k;g++) {
		cin >> n;
		re.clear();
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			re.push_back(a[i]);
		}
		sort(re.begin(),re.end()); re.erase(unique(re.begin(),re.end()),re.end());
		for(int i = 1;i <= n;i++) a[i] = lower_bound(re.begin(),re.end(),a[i])-re.begin()+1;
		m = re.size();
		build(1,1,m);
		for(int i = n;i >= 1;i--) {
			int wi = queryMin(1,1,m,1,a[i]-1);
			if(wi <= n) {
				int wi2 = queryMax(1,1,m,a[i]+1,m);
				if(wi2 > wi) {
					ans.push_back(g);
					break;
				}
			}
			update(1,1,m,a[i],i);
		}
	}
	cout << ans.size() << '\n';
	for(int i : ans) cout << i << '\n';
	return 0;
}

 

H - Historic Exhibition (urd05, 40분)

 

플랫이 슥삭 했다. (와아아아아아아아ㅏㅏ 갓플랫! 갓플랫!)

 

E - Efficient Exchange (gunwookim, 45분)

 

알고리즘 : 그리디

$i$번째 자리수를 $b[i]$ 라 두자.

이때 $b[i] < 5$ 라면 무조건 없애는게 이득이고, $b[i] > 5$라면 무조건 넘기는게 이득이다.

그렇다면 $b[i] = 5$인 경우는 어떨까?

그럴때는 앞자리의 수까지 확인해 봐야 한다.

앞자리 수가 5 이상이라면 무조건 넘기는게 이득이고, 아닌 경우는 그냥 없애는게 이득이다.

 

#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> pii;
char a[1005];
int n,b[1005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a+1; n = strlen(a+1);
	int cnt = 0;
	for(int i = 1;i <= n;i++) b[i] = a[i]-'0';
	for(int i = n;i >= 1;i--) {
		b[i-1] += b[i]/10;
		b[i] %= 10;
		if(b[i] > 5||(b[i] == 5&&b[i-1] >= 5)) {
			cnt += 10-b[i];
			b[i-1]++;
		}
		else cnt += b[i];
	}
	cout << cnt+b[0];
	return 0;
}

 

 

K - Keep Him Inside (urd05, 69분)

 

플랫이 슥삭 했다. (와아아아앙아ㅏ앙ㅇ아아아아ㅏㅏ 갓플랫! 갓플랫! 갓플랫!)

 

A - Appeal to the Audience (gunwookim, 74분)

 

하.. 진짜 쓰고 싶은데 제가 설명을 잘 못해서 말이 안튀어 나와요 ㅠㅠ

이건 어쩔 수 없이 코드를 보시길 바랍니다 ㅠ

대신 주석을 좀 넣었어요!

 

#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> pii;
vector <int> v[100005];
int n,k,a[100005],dep[100005],maxMatch;
ll ans;
vector <int> cnt;
// 1-index 이다. (인덱스가 1부터 시작)
//cnt : 리프 노드에서 매칭되는 최대 매칭 횟수를 저장
// maxMatch : 최대로 싸울 수 있는 수
// dep : 높이 
// 여기서의 높이는 좀 다르다.
// 리프노드인 경우 : depth
// 리프노드가 아닌경우 : max(dep[u]) (u는 자식)

void getDepth(int x,int depth) { // depth 구하기
	dep[x] = depth;
	for(int i : v[x]) {
		getDepth(i,depth+1);
		dep[x] = max(dep[x],dep[i]);
	}
}

void getAns(int x) {
	if(!(int)v[x].size()) {
		cnt.push_back(maxMatch);
		maxMatch = 0; return;
	}
	for(int i : v[x]) {
		if(dep[x] == dep[i]) {
			maxMatch++;
			getAns(i);
		}
	}
	for(int i : v[x]) {
		if(dep[x] != dep[i]) {
			maxMatch++;
			getAns(i);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= k;i++) cin >> a[i];
	for(int i = 1;i <= n-1;i++) {
		int x; cin >> x;
		v[x+1].push_back(i+1);
	}
	sort(a+1,a+k+1);
	getDepth(1,1); getAns(1);
	sort(cnt.begin(),cnt.end());
	for(int i = 1;i <= k;i++) ans += 1LL*a[i]*cnt[i-1]; // 최대 매칭될 수 있는 수의 자리에 최대의 수를 넣어준다. 
	cout << ans;
	return 0;
}

 

G - Gluttonous Goop (gunwookim, 117분)

 

먼저 나이브로 20번 정도 돌려본다. 그러면 중간의 뻥 뚫린 공간이 있더라도 다 메꿔질 것이다.

어느정도 모양이 잡히면 일정 간격만큼 늘어난다는 것을 알 수 있다.

이제 그 뒤는 규칙을 찾아서 그냥 더하면 된다,

 

#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> pii;
int n,m,k;
char a[105][105],b[105][105],in[105];
int nx[9] = {1,1,1,0,0,0,-1,-1,-1}, ny[9] = {1,0,-1,1,0,-1,1,0,-1};
vector <ll> cnt;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> k;
	int sum = 0;
	for(int i = 1;i <= 100;i++) {
		for(int j = 1;j <= 100;j++) {
			a[i][j] = b[i][j] = '.';
		}
	}
	for(int i = 1;i <= n;i++) {
		cin >> in+1;
		for(int j = 1;j <= m;j++) {
			a[i+40][j+40] = in[j];
			sum += (in[j]=='#');
		}
	}
	cnt.push_back(sum);
	for(int i = 1;i <= 20;i++) {
		for(int x = 1;x <= 100;x++) {
			for(int y = 1;y <= 100;y++) {
				if(a[x][y] == '.') continue;
				for(int l = 0;l < 9;l++) {
					b[x+nx[l]][y+ny[l]] = '#';
				}
			}
		}
		sum = 0;
		for(int x = 1;x <= 100;x++) {
			for(int y = 1;y <= 100;y++) {
				if(b[x][y] == '#') sum++;
				a[x][y] = b[x][y];
				b[x][y] = '.';
			}
		}
		cnt.push_back(sum);
	}
	int gap = (cnt[20]-cnt[19])-(cnt[19]-cnt[18]);
	for(int i = 21;i <= k;i++) {
		cnt.push_back(cnt[i-1]+cnt[i-1]-cnt[i-2]+gap);
	}
	cout << cnt[k];
	return 0;
}

 

L - Lucky Draw (urd05, 139분)

 

플랫이 슥삭 했다. (와아아아앙아ㅏ앙ㅇㅏ아아ㅏ아ㅏㅏ아앙ㅇ아앙아아아ㅏㅏ 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫!)

 

I - Inquiry II (gunwookim, 169분)

 

일단 생각해본게 트리로 만들어 보는것이다.

트리로 만드는거는 유니온 파인드를 통해 적절히 만들어 줄 수 있고, 나머지 $m-n+1$ 개의 간선을 가지고 풀어볼거다.

여기서 만약 나머지 간선이 없다면 다이나믹 프로그래밍을 통해 풀 수 있다.

$dp[i][j] : i$번 노드에서 $j$는 $i$번 노드가 포함되면 $1$, 아니면 $0$ 이라 할때 가능한 최대 독립 집합 크기

이런 정의를 하면 $O(n)$에 가능하다.

 

이제 간선을 추가해 보자. 간선의 양 끝점이 $u, v$라 하면 $u$와 $v$ 중에 하나는 무조건 독립집합으로 포함되면 안된다. 그러면 $2^ {m-n+1}$ 개수 만큼의 상태가 나올 것이다. 이제 이 모든 상태에 대해 다이나믹을 돌려서 나온 값들중 최댓값을 출력하면 된다. 시간 복잡도는 $O(n\cdot 2^ {m-n+1})$ 다.

 

#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> pii;
int n,m,p[105],dont[105],d[105][2];
vector <int> v[105];
vector <pii> no;

int Find(int x) {
	return ((x == p[x]) ? x : p[x] = Find(p[x]));
}

void Merge(int x,int y) {
	x = Find(x), y = Find(y);
	p[x] = y;
}

void dfs(int x,int la) {
	d[x][1] = 1;
	for(int i : v[x]) {
		if(i == la) continue;
		dfs(i,x);
		d[x][0] += d[i][1];
		d[x][1] += d[i][0];
	}
	if(dont[x]) d[x][1] = d[x][0];
	else d[x][1] = max(d[x][1],d[x][0]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++) p[i] = i;
	for(int i = 1;i <= m;i++) {
		int x,y; cin >> x >> y;
		if(Find(x) == Find(y)) {
			no.push_back({x,y});
			continue;
		}
		Merge(x,y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	int k = (m-n+1),ans = 0;
	for(int i = 0;i < (1 << k);i++) {
		memset(dont,0,sizeof(dont));
		memset(d,0,sizeof(d));
		for(int j = 0;j < k;j++) {
			if(i & (1 << j)) dont[no[j].y] = 1;
			else dont[no[j].x] = 1;
		}
		dfs(1,-1);
		ans = max(ans,d[1][1]);
	}
	cout << ans;
	return 0;
}

 

D - Deck Randomisation (urd05, 284분)

 

플랫이 슥삭 했다. (와아아아앙아ㅏ앙ㅇㅏ아아앙ㅇ아ㅏㅏ아아아아아ㅏ아아앙아ㅏ아ㅏ아ㅏㅏ아앙ㅇ아앙아아아ㅏㅏ 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫! 갓플랫!)

 

풀이 끝!