[210530] 2021 연세대학교 신입생 프로그래밍 경진대회 Open 후기

2021 연세대학교 신입생 프로그래밍 경진대회 Open

2021 연세대학교 신입생 프로그래밍 경진대회 Open

Math, Constructive, Ad_hoc 문제가 엄청나게 많았던 대회 셋이다.

왼쪽 문제들을 보면 알 수 있듯이, 문제마다 점수가 다르다.

당시 나는 5문제를 해결하였으며,

이번 대회 역시 aru0504님이랑 함께 응시하였다.

 

aru0504님이랑 응시하는 대회는 항상 재밌는 것 같다.

aru0504님은 F번, 나는 E번을 solve하였고, 개인적으로 이번 대회에서 F번이 진짜 어렵다고 생각한다. 대회 당시 아예 건들지도 않았던 G, H번도 끝나고 해결해보았는데, G, H보다 F가 순간적인 아이디어 생각해내기엔 더더욱 어려운 것 같다. 도대체 F번 어떻게 해결하신거지

대회가 끝나고 F, G, H번도 풀어보았다.

---

A. 추첨을 통해 커피를 받자

21866번: 추첨을 통해 커피를 받자

첫 문제부터 어려울려나 걱정했는데 다행히 그러지 않았다.

 

if문 노가다를 해야 되나 싶었는데

다행히 2문제씩 차례대로 배점이 100 씩 증가하여 for문으로 처리할 수 있었다.

 

그냥 for문으로 합이 100이 넘는지 아닌지를 체크해주면 될 듯하다.

다만, 배점보다 큰 경우가 있다면 언제든지 break를 해주자.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1000001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int a[9], ret;
string ans;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	for (int i = 0; i < 9; i++) {
		cin >> a[i];
		ret += a[i];
		if (a[i] > 100 * (1 + i / 2)) {
			cout << "hacker\n";
			return 0;
		}
	}
	if (ret >= 100)
		cout << "draw\n";
	else
		cout << "none\n";
}

---

B. Java Bitecode

21867번: Java Bitecode

개인적으론 제일 쉬웠던 문제.

그냥 J, A, V일 경우 따로 정답문자열에 insert해주지 않으면 된다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1000001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N;
string s, ans;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> s;
	for (int i = 0; i < N; i++) {
		if (s[i] == 'J' || s[i] == 'A' || s[i] == 'V')
			continue;
		ans += s[i];
	}
	if (ans.empty())
		cout << "nojava\n";
	else
		cout << ans << "\n";
}

---

C. 미적분학 입문하기

21868번: 미적분학 입문하기

일단 입실론-델타 논법이 무슨 소린지 몰라서 충격 1,

입실론-델타 논법 설명이 영어로 돼있어서 충격 2....

 

결국 입실론 델타 논법을 구글링하여 찾아보았다.

일단 극한값 L은 따로 검색하지 않아도 f(x)에 x0를 집어넣은 값임을 알 수 있고,

문제는 델타이다. 델타를 어떻게 구하나 했는데,

알고보니 그냥 abs(ax+b)<입실론일 때, abs(x+b/a)<델타였다.

따라서 델타는 입실론/a 가 답이다.

 

다만, 항상 양수여야 함에 주의하자! 그리고, 분자나 분모가 0일 경우 존재하지 않는다는 사실 또한 잊지 말자.

이러한 점 때문에 엄청나게 많이 틀렸기 때문이다...

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1000001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int e1, e2, a, b, x0;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> e1 >> e2 >> a >> b >> x0;
	cout << a * x0 + b << "\n";
	int ans1 = e1, ans2 = a * e2;
	if (!ans1 || !ans2) {
		cout << "0 0\n";
		return 0;
	}
	cout << abs(ans1) << " " << abs(ans2) << "\n";
}

문제를 이해하면 막상 풀기엔 많이 쉬워서 티어가 어떻게 나올지 궁금했는데,

역시나 생각보다 꽤 높은 티어이다.

---

D. Maximum Bishop

21869번: Maximum Bishop

이 문제를 보고 좀 많이 쫄았다.

백준 1699번 비숍 백트래킹 문제가 생각났기 때문이다.

심지어 모든 위치를 출력하라고 돼있었기에 출제진분들께서 D번부터 헬게이트로 냈구나 싶었다...

 

근데 N이 너무 커서 절대 백트래킹은 아닐 것 같았고, dp나 그리디이지 않을까 싶어 생각해봤는데,

N이 1일 때는 1가지 경우,

N이 2일 때엔 그냥 맨위, 맨 아래에 몰아서 붙이면 절대 충돌하지 않는 경우임을 깨닫고

생각보다 어렵지 않게 해결하였다.

 

증명은 잘 모르겠고... proof by ac... (ad_hoc, constructive 문제들이 특히 뭔가 확신은 안드는데 이거 외엔 안될것이다! 하는 뭔가가 있는 듯하다.)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 524289;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
int N;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	if (N == 1)
		cout << "1\n1 1\n";
	else {
		cout << (N-1) * 2 << "\n";
		for (int i = 2; i <= N; i++) {
			cout << 1 << " " << i << "\n";
		}
		for (int i = 2; i <= N; i++) {
			cout << N << " " << i << "\n";
		}
	}
}

---

E. 시철이가 사랑한 GCD

21870번: 시철이가 사랑한 GCD

dfs로 모든 경우를 다 탐색해보면 되는데,

왼쪽은 버림, 오른쪽은 올림인데,

둘 다 버림으로 잘못보고 계속 하다가 틀렸다.

 

재귀 성질을 알면 쉽게 풀리는데,

처음엔 재귀로 접근하지 않고 그리디로 해결할 수 있을 듯하여 그리디/정렬로 해결해보다가 큰코당한 문제이다.

 

개인적으로 G5는 좀 낮아보인다. G4, 높게주면 G3까지 줘도 된다고 생각한다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 200001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
ll N, a[MAX];
ll gcd(ll a, ll b) {
	ll r = a % b;
	if (!r)
		return b;
	return gcd(b, r);
}
ll solve(int s, int e) {
	ll ret = a[s];
	for (int i = s + 1; i <= e; i++) {
		ret = gcd(ret, a[i]);
	}
	return ret;
}
ll dfs(int s, int e) {
	if (s==e) {
		return a[s];
	}
	int mid = (e - s + 1) / 2;
	int mid2 = (int)(0.5 + (double)(((double)e - s + 1) / 2));
	ll ret2 = dfs(s + mid, e) + solve(s, s + mid - 1);
	ll ret1 = dfs(s, e - mid2) + solve(e - mid2 + 1, e);
	ll ans = max(ret1, ret2);
	return ans;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	cout << dfs(1, N) << "\n";
}

---

여기서부턴 대회가 끝나고 해결해보았다.

F. 화석 발굴 이벤트

21871번: 화석 발굴 이벤트

대회 도중에 해결해보려하다가 식이 도저히 보이지 않아 포기한 문제이다.

좌표평면에 N=1~3, K=1~3일 때까지 다 그려보면 뭔가 규칙이 보인다. (이 그리는 과정도 엄청나게 시간에 걸림...ㅋㅋ큐ㅠㅠㅠ)

 

바로 삼각형 꼴이라는 것. 참고로 짝수일 땐 뒤집을 때 절댓값이 같은 경우가 존재하므로 +1을 해줘야한다.

(배고파서 풀이 좀 급하게 쓰는중이다.)

 

이 때 일반항을 세우는 과정이 좀 많이 더러운데, 

그냥 열심히 식정리하면 된다.

 

주의할점은 K가 2N보다 크면 딱히 오염되는 구역이 없다는 점을 명시하자! 이걸 체크하지 않으면 답이 음수가 나온다.

다른 분들을 보니까 일반항을 세우지 않고 푸신 분들도 꽤 있었다. N이 10억인데 어떻게 그렇게 하신지는 잘 모르겠다...

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <numeric>
#include <set>
#include <string>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 200001;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
const int MOD = 1e9 + 7;
ll N, K;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> K;
	if (K > 2 * N)
		cout << (2 * N + 1) * (2 * N + 1) << "\n";
	else if (K % 2)
		cout << (2*N+1)*(2*N+1)-(2*N-K+1)*(2*N-K+3)/2 << "\n";
	else
		cout << 2 * N * N + 2 * N * K - K*K/2+K << "\n";
}

---

G. Deque Game

21872번: Deque Game

처음엔 구현 문제인 줄 알았는데 알고보니 조합론 문제였다.

쌓아야 하는 층 높이는 같으므로, 자신의 층이 더 낮은 사람이 더 많은 경우의 수를 쌓을 수 있어 승리한다.

 

문제는 같은 층일 때이다.

사실 처음에는 스택에 있는 문자열들의 중복을 제거하여 종류가 더 많은 사람이 승리하는 줄 알았고, WA를 받았다.

그런데 생각해보니 중간에 끼어넣을 수 있다 해도, 원래 쌓여있는 순서는 바뀌지 않으므로 종류가 더 다양하든 말든 간에 끼워넣을 수 있는 경우는 똑같다!

따라서 그냥 층 높이가 같으면 무승부이다.

 

근데 함정이 하나 있다.

블록의 종류가 오직 한 가지라면, 어떤 경우이든 간에 항상 1가지 경우만 존재하므로 항상 무승부이다....

맞왜틀하기도 쉽고, 증명도 쉽지 않은 꽤 난이도있는 문제였다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 3001;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int K, L, N, M;
string S, T;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int t;
	cin >> t >> K >> L;
	while (t--) {
		cin >> N >> S;
		cin >> M >> T;
		if (K == 1) {
			cout << "YS\n";
			continue;
		}
		if (N == M)
			cout << "YS\n";
		else
			cout << (N > M ? 'S' : 'Y') << "\n";
	}
}

---

H. 개구리 징검다리 건너기

21873번: 개구리 징검다리 건너기

 

N이 1일 때와 2일 때, 3일 때를 해보면 느낌이 올 것이다.

서로 다른 색깔의 개구리를 한 칸 이상 뛰어넘을 수 없기 때문에 

빈칸이 따로 없는 이상 색깔이 서로 다른 개구리끼리 번갈아 위치해 있어야 한다.

 

실제로 되는 경우를 나열하다보면 아래와 같다.

흰 색 개구리를 A, 검은색 개구리를 B라 할 때 아래와 같다.

업무 중간 쉬는시간에 고민하고, 집 가서 이렇게 solve하면 되겠다 싶어 카톡에 기록

결국 A와 B가 번갈아가면서 1~N까지,

그다음에 1~N까지 다른 색 개구리들이 이동하고,

다음 1~N까지 A와 B가 번갈아가면서 이동하므로

 

총 2 * N(N+1)/2 + N = N^2 + 2N 번 이동한다.

 

뭔가 나열하다보니 일반적인 규칙을 찾은 것 같고, 정확한 증명은 솔직히 잘 모르겠다... proof by AC...

 

#include <iostream>
#include <algorithm>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 1001;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	cout << N * N + 2 * N << "\n";
	for (int j = 1; j <= N; j++) {
		for (int i = 1; i <= j; i++) {
			if (j % 2)
				cout << 1 << " " << i << "\n";
			else
				cout << 2 << " " << i << "\n";
		}
	}
	for (int i = 1; i <= N; i++) {
		if (N % 2)
			cout << 2 << " " << i << "\n";
		else
			cout << 1 << " " << i << "\n";
	}
	for (int j = N; j >= 1; j--) {
		for (int i = N - j + 1; i <= N; i++) {
			if (j % 2)
				cout << 1 << " " << i << "\n";
			else
				cout << 2 << " " << i << "\n";
		}
	}
}

번갈아가는 과정을 XOR로 처리해도 될 듯하다.

---

I. 모자 게임

21874번: 모자 게임

함수 구현하는 인터랙티브 문제를 백준에서 어떻게 해결해야 하는지 방법을 모르겠다....

init 함수로 N을 설정해주면 벡터 F, B를 init 함수에서 초기화해주는건가? init 함수에서 call 함수를 불러야 하는건가...?

전혀 모르겠다...

 

뒤에서 불러주는 수와, 자기 앞에 있는 사람들의 모자 수를 모두 알 수 있기 때문에

결국 자기 자신과 맨 뒷사람 모자에 쓰여진 수만 모르는 것이다.

이것을 통해 잘 구현하면 될 듯하다. 이 문제는 내가 풀어보지 않았으므로 더 이상 언급하지 않아야겠다.

---

ad_hoc, constructive, math 문제들이 이렇게 많은 대회는 첨보는 듯하다.

자료구조와 알고리즘 없이 오로지 수학만으로 대회를 치뤄보는 느낌이었다.

실력이 많이 늘었는지는 잘 모르겠지만... 이런 종류의 문제들도 많이 풀다보면 어느새 감각이 좋아지리라 믿는다.

 

constructive 문제들은 정말 증명이 뭔가 어려운 것같다.

최대한 경험을 많이 해서 경험으로 메꿔봐야겠다.