AtCoder Beginner Contest 165

오랜만에 앳코더를 봤다. 그럭저럭 본것 같다. (안친 사이에 실력이 꽤 늘었다)

간략하게 풀이 설명을 한다!

 

A 번 문제

A~B 사이에 K의 배수가 있는지 없는지 판별하는 문제다.

B/K - (A-1)/K 가 0인지 아닌지 판별하면 된다.

#include <bits/stdc++.h>
using namespace std;
int n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	int a,b;
	cin >> a >> b;
	cout << (b/n-(a-1)/n?"OK":"NG");
}

B번 문제

계속 지금 있는 돈의 1%만큼 늘려갔을때 언제 X원을 넘느냐는 문제다.

10^18원을 모을때 까지 3670년 이 안걸리므로 시뮬레이션을 해본다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll x,g = 100,ans = 0;
	cin >> x;
	while(g < x) {
		g += g/100;
		ans++;
	}
	cout << ans;
}

C번 문제

문제를 읽어보세요.

직접 돌려보니 경우의 수가 30만개밖에 안나온다!

모든 경우에 대한 d합의 최댓값을 구해주자.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,Q,ans;
int a[15];
 
struct Query {
	int a,b,c,d;
}q[55];
 
void dfs(int x) {
	if(x == n+1) {
		int res = 0;
		for(int i = 1;i <= Q;i++) {
			if(a[q[i].b]-a[q[i].a] == q[i].c) res += q[i].d;
		}
		ans = max(ans,res);
		return;
	}
	for(int i = a[x-1];i <= m;i++) {
		a[x] = i; dfs(x+1);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> Q;
	for(int i = 1;i <= Q;i++) {
		cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d;
	}
	a[0] = 1;
	dfs(1);
	cout << ans;
} 

D번 문제

그리디 적으로 생각해보자.

floor(Ax/B)는 최대한 키우고 A*floor(x/B)는 0으로 만들어보자.

그런 경우는 x = B-1인 경우밖에 없다.

N이 B-1보다 작은 경우는 예외처리를 해주자.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	long double a,b,c;
	cin >> a >> b >> c;
	if(c < b-1) cout << floor(a*c/b)-a*floor(c/b);
	else cout << floor(a*(b-1)/b);
} 

E번 문제

내가 생각한 건

예제가 10 4 로 주어지면

3 1 1 3 4 2 0 2 4 0 이런 식으로 짝수와 홀수를 따로 분류해서 처리한다.

저렇게 하면 1~N까지의 거리가 골고루 나올 것이다. (proof by ac)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
 
void dfs(int x,int y) {
	if(x >= y) return;
	cout << x << ' ' << y << '\n';
	dfs(x+1,y-1);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	dfs(1,(m/2+m%2)*2);
	dfs((m/2+m%2)*2+1,(m/2+m%2)*2+1+(m-m%2));
} 

F번 문제

O(n log n) 방법의 lis를 알고 있다면 이 문제를 풀 수 있다.

1번 정점부터 dfs를 돌면서 lis를 구할건데 Roll-Back을 구현해야 한다.

x의 서브 트리정점은 모두 x번 정점을 경로로 가지므로 가능한 이야기다.

Roll-Back을 구현하기 위해 set으로 짰다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[200005];
vector <int> v[200005];
set <int> s;
int ans[200005];
 
void dfs(int x,int p) {
	auto it = s.end();
	int val,val2,ch = 0;
	if(s.empty()) s.insert(a[x]);
	else {
		it--; val = *it;
		if(a[x] > val) ch = 1,s.insert(a[x]);
		else {
			it = s.lower_bound(a[x]);
			val2 = *it;
			s.erase(it);
			s.insert(a[x]);
			ch = 2;
		}
	}
	ans[x] = s.size();
	for(int i : v[x]) {
		if(i == p) continue;
		dfs(i,x);
	}
	if(!ch) s.erase(a[x]);
	if(ch == 1) s.erase(a[x]);
	if(ch == 2) {
		s.erase(a[x]);
		s.insert(val2);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i < n;i++) {
		int x,y; cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	for(int i = 1;i <= n;i++) {
		cout << ans[i] << '\n';
	}
}