Educational Codeforces Round 98 (Div.2)

 

 

그저께 밤에 있었던 Educational Codeforces Round 98 풀이이다. 총 3솔브를 했다.

 

A. Robot Program

 

주어지는 두 길이를 \( N, M \)이라 하자\(( N \ge M )\).

 

이 때, 아래 그림과 같이 움직이는 게 최선의 경로이며, 총 필요한 Command의 개수는 \(N=M\)일 때 \(2M\)개이고, \(N \neq M\)일 때 \(2N - 1\)개이다.

 

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	while (T--) {
		int N, M; cin >> N >> M;
		if (N < M)swap(N, M);
		int res = 0;
		res += 2 * M;
		if (N != M) res += 2 * (N - M) - 1;
		cout << res << '\n';
	}
}

 

B. Toy Blocks

 

못 풀었다. 작성 예정

 

 

C. Two Brackets

 

\((, ), [, ]\)만으로 이루어진 문자열이 주어질 때, 해당 문자열에서 몇 개의 괄호 쌍을 찾을 수 있는지 알아내는 문제이다. 간단한 아이디어만으로 풀어낼 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	while (T--) {
		string str;
		cin >> str;
		int a = 0, b = 0, ans = 0;
		for (int i = 0; i < str.length(); i++) {
			if (str[i] == '(') {
				a++;
			}
			if (str[i] == ')') {
				if (a >= 1)ans++, a--;
			}
			if (str[i] == '[') {
				b++;
			}
			if (str[i] == ']') {
				if (b >= 1)ans++, b--;
			}
		}
		cout << ans << '\n';
	}
}

 

D. Radio Towers

 

문제가 좀 난해한데, 관찰을 통해 다음과 같은 문제임을 알아낼 수 있다.

 

피보나치 수열의 \(N\)번째 항을 \(fib(N)\)라고 할 때, \(x = fib(N), y = 2^N\)라고 하자. 이 때, \(x \times y^{-1}\)을 구하시오. 이 때, \(y^{-1}\)는 \(988,244,353\)에 대한 모듈러 역원이다.

 

문제 자체에 모듈러 역원이라는 단어가 등장하기도 하니, 확장 유클리드 알고리즘을 이용해 구현하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
long long MOD = 998244353;
long long arr[200001] = { 0 };
long long n, a;
tuple<long long, long long, long long> euclid(long long x, long long y) {
	if (x < y) swap(x, y);
	if (y == 0) return { x,1,0 };
	long long g, x1, y1; tie(g, x1, y1) = euclid(y, x%y);
	return { g, y1, x1 - (x / y) * y1 };
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N; cin >> N;
	arr[0] = 0; arr[1] = 1;
	for (int i = 2; i <= N; i++)arr[i] = arr[i - 1] + arr[i - 2], arr[i] %= MOD;
	long long base = 1;
	for (int i = 0; i < N; i++) {
		base *= 2;
		base %= MOD;
	}
	tuple<long long, long long, long long> ret = euclid(base, MOD);
	long long inv = (get<2>(ret) + MOD) % MOD;
	cout << (inv * arr[N]) % MOD;
}

 

이번 문제 셋은 난이도 배치가 정말 엉망이었다. 전반적으로 문제 난이도가 \(C<A<D<B\)로 느껴졌고, \(E\)부턴 아예 손도 대지 못 할 정도로 어려웠다. \(C\)가 쉬운 문제인 것을 모르고 계속 \(B\)에 메달려있었고, 이 때문에 등수가 엄청나게 하락했다. 또한, \(D\)는 말 그대로 모듈러 역원을 구하라는 문제였는데, 이 문제가 정말로 Educational한 문제였는지 의문이 든다.

 

어쨌든 대회는 끝났고, 다음 대회부터 또 다시 열심히 할 예정이다.