Codeforces Round #685 (Div.2)

 

 

 

 

11월 21일 있었던 코드포스 라운드 685의 풀이이다.

 

3솔브

 

A. Subtract or Divide

 

주어진 수 \(N\)을 두 가지 연산을 이용해 \(1\)로 만드는데, 필요한 연산 횟수의 최솟값을 구하는 문제이다.

두 가지 연산은 각각 수를 자신의 진약수로 나누거나, \(1\)을 빼는 연산이다.

 

결정적인 관찰은 \(N\)이 짝수이면 1번의 연산만으로 무조건 \(N\)을 \(2\)를 만들 수 있는 것이다. 이것을 늦게 발견해서 이 문제를 푸는 데 25분이나 걸렸다.

 

시간 복잡도는 테스트 케이스 당 \(O(1)\)이다.

 

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T; while (T--) {
		long long N; cin >> N;
		int cnt = 0;
		while (1) {
			if (N == 2) {
				cout << cnt + 1 << '\n';
				break;
			}
			if (N == 1) {
				cout << cnt << '\n';
				break;
			}
			if (N % 2 == 1) {
				N--; cnt++;
				continue;
			}
			N = 2; cnt++;
			continue;
		}
	}
}

 

 

 

B. Non-Substring Subsequence

 

주어진 문자열에 대해 쿼리를 처리하는 문제이다. 쿼리로 주어진 구간을 \([L, R]\)이라고 하면, \([0,L-1]\) 중에서 하나 이상의 문자가 \(L\)과 같거나, \([R+1, N-1]\)중에서 하나 이상의 문자가 \(R\)과 같으면 YES이다. 이것을 Naive하게 구현하면 쿼리 당 \(O(N)\)에 처리가 가능하고, 제한이 작기 때문에 이 방법도 Accepted를 받을 수 있다.

 

더 빠르게 하려면, Prefix Sum을 이용해 0과 1의 개수를 저장해놓고, 쿼리 당 \(O(1)\)으로 처리하면 된다. 대략적인 아이디어는, 먼저 \(psum_0[i] = i\)번째 index까지의 \(0\)의 개수, \(psum_1[i] = i\)번째 index까지의 \(1\)의 개수로 놓는다. 쿼리가 들어올 때  \(psum_i[L-1]\)과 \(psum_i[0]\)을 비교하고, \(psum_j[R]\)과 \(psum_j[N]\)을 비교해서 하나라도 다르다면 YES임을 알 수 있다\((\)단, \(i = str[L], j = str[R])\).

 

실제 대회에서는 Naive 풀이가 통과되는 것을 캐치하지 못하고 Prefix Sum으로 풀었다.

 

#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, Q; cin >> N >> Q;
		string str; cin >> str;
		vector<int> p1(N + 1), p0(N + 1);
		p1[0] = p0[0] = 0;
		for (int i = 0; i < N; i++) {
			p1[i + 1] = p1[i] + (str[i] == '1');
			p0[i + 1] = p0[i] + (str[i] == '0');
		}
		while (Q--) {
			bool good = 0;
			int L, R; cin >> L >> R;
			if (str[L - 1] == '0') {
				if (p0[L - 1] != 0)good = 1;
			}
			if (str[L - 1] == '1') {
				if (p1[L - 1] != 0)good = 1;
			}
			if (str[R - 1] == '0') {
				if (p0[N] != p0[R])good = 1;
			}
			if (str[R - 1] == '1') {
				if (p1[N] != p1[R])good = 1;
			}
			cout << (good ? "YES\n" : "NO\n");
		}
	}
}

 

 

 

C. String Equality

 

문자열을 적당히 변환시켜 다른 문자열로 만들 수 있는지 물어보는 문제이다. 가능한 연산은 연속된 두 개의 문자의 순서를 바꾸는 것과, \(k\)개의 연속된 문자열의 알파벳 순서를 \(1\) 올리는 것이다. 단, 두 번째 연산에서 모든 \(k\)개의 문자열은 같은 알파벳이어야 한다.

 

먼저 관찰을 통해 첫 번째 연산을 무한정 사용할 수 있으므로 문자열의 순서는 중요하지 않다는 것을 알 수 있다. 그러면 각 문자가 몇 개인지가 중요한데, 두 번째 연산으로는 문자열의 알파벳 순서를 올릴 수만 있고, 내릴 수는 없다. 그렇다면, 할 수 있는 최선의 수는 \(a\)부터 시작해서 해당 문자가 목표 문자열에 사용되는 만큼 개수를 빼준 뒤, 나머지를 모두 다음 알파벳으로 올리는 것이다. 이 때, 빼주고 나서의 값이 \(k\)로 나누어떨어져야 가능한 경우의 수가 된다. 만약 \(a\)부터 \(y\)까지 이 조건을 만족하고, \(z\)에서 원래 문자열이랑 목표 문자열이랑 개수가 같으면, 답이 YES이다.

 

#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, K; cin >> N >> K;
		string s1, s2;
		cin >> s1 >> s2;
		vector<int> m1(26, 0), m2(26, 0);
		for (int i = 0; i < N; i++) {
			m1[s1[i] - 'a']++;
			m2[s2[i] - 'a']++;
		}
		bool pos = 1;
		for (int i = 0; i < 26; i++) {
			int left = m1[i] - m2[i];
			if (left < 0) {
				pos = 0;
				break;
			}
			if (left%K != 0) {
				pos = 0;
				break;
			}
			m1[i + 1] += left;
			if (i == 25) {
				if (left != 0)pos = 0;
			}
		}
		cout << (pos ? "Yes\n" : "No\n");
	}
}

 

 

오랜만에 재미있었던 셋이었다.