알고리즘/코드포스

Codeforces Round 923 (Div. 3) - 블루 달성

penguin12 2024. 4. 8. 21:05

대회 요약
스코어보드

여러가지 우여곡절이 있었지만 어쨌든 F까지 풀어서 높은 등수를 받고, 레이팅도 100점 넘게 올라서 블루를 달성하게 되었다. F번을 푼 사람이 290명인것을 생각하면 패널티로는 거의 맨 밑이었고, 스코어보드(C)만 봐도 벌써 두달이 지난 대회의 추억(?)이 떠오른다.

 

여러가지 우여곡절

대회시작 6분에 A를 풀고, B를 제출했는데 test1 에서 WA가 나와서 살짝 말렸음을 직감했다. 그래도 패널티가 누적되지는 않았으니 일단 빠르게 넘기고 C를 풀어서 test8 에서 WA를 받고 시원하게 패널티를 적립했다.

다시 B를 보니 문제를 잘못 이해했음을 발견하고, 고쳐서 AC를 받았다. 다시 C를 열심히 고쳐서 WA를 받고, D와 E를 약 20분동안 풀어서 맞췄다.

그리고 다시 C로 돌아와서 WA를 한번 더 받고, 그제야 배열 크기를 잘못 잡았음을 깨닫고, 고쳐서 제대로 TLE를 받고, 한번더 TLE를 받고, 배열 초기화 코드를 개선해서 AC를 받았다. 그리고 스코어보드를 보니 5솔 중에서는 거의 최하위였던 것 같다.

 

(그당시 1590점이었다)블루 달성을 10점밖에 안 남기고, 풀이는 처음부터 제대로 찾아놓고 삽질을 이렇게 해서 다시 미끄러지면 너무 안타까울 것 같아서, F를 각잡고 풀기 시작했다.

대충 보니까 그래도 자신있는 크루스칼 알고리즘인 것 같아서, 맨탈을 추스르고 머슬메모리로 크루스칼을 짰다. 제출해서 한번에 AC받고, G는 N이 100인것으로 봐서 이상한 N^3이나 N^4같은 알고리즘일 것 같아서 거르고 대회를 마쳤다.

 

F를 맞춘 덕분에 거의 퍼플에 가까운 퍼포먼스가 나왔고, 레이팅이 블루로 올랐다. 역시 사람은 배수진을 치고 좀 다급해져야 실력이 잘 나오는 것 같다. C이슈는 블루 달았으니 좋게 생각하기로 했고, 앞으로 계속 실수를 줄이는 노력을 해야겠다.

 

A. Make it White

https://codeforces.com/contest/1927/problem/A

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;
		string s;
		cin >> s;

		int m = 987654321;
		int M = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == 'B') {
				m = min(m, i);
				M = max(M, i);
			}
		}

		cout << M - m + 1 << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

문제가 굉장히 친절하다. B가 처음 등장하는 위치부터 B가 마지막으로 등장하는 위치까지 칠하면 되는데, B가 무조건 한번 이상 등장하므로 B가 없을 경우에 대한 예외처리도 필요 없다. 스트링의 양쪽에서 탐색해도 되지만, 나는 그냥 한 방향으로 스위핑 하면서 min, max를 사용했다. 시간복잡도는 O(N)이다.

 

B. Following the String

https://codeforces.com/contest/1927/problem/B

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

char res[200001];

int counts[256];

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;

		fill(&counts[0], &counts[256], 0);

		char curr = 'a';
		for (int i = 0; i < n; i++) {
			int input;
			cin >> input;

			if (input == 0) {
				res[i] = curr;
				counts[curr]++;
				curr++;
			}
			else {
				char c;
				for (c = 'a'; c <= curr; c++) {
					if (counts[c] == input) {
						break;
					}
				}
				res[i] = c;
				counts[c]++;
			}
		}
		res[n] = 0;
		cout << res << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

처음에 문제를 읽을 때, 등장 횟수가 아니라 등장 인덱스로 읽어서 WA를 한번 받았다. 알파벳별로 등장 횟수 테이블을 만들고, 입력이 k라면 등장횟수가 k-1인 "아무 알파벳이나"골라서 출력하고 등장 횟수를 1증가시키면 된다. 이 문제도 무조건 가능한 입력만 들어오기 때문에 쉽게 구현할 수 있다.

 

C. Choose the Different Ones!

https://codeforces.com/contest/1927/problem/C

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

bool A[400001];
bool B[400001];

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n, m, k;
		cin >> n >> m >> k;

		if (n >= k / 2 && m >= k / 2) {
			fill(&A[0], &A[k + 1], false);
			fill(&B[0], &B[k + 1], false);
		}

		for (int i = 0; i < n; i++) {
			int input;
			cin >> input;
			if (input <= 400000) {
				A[input] = true;
			}
		}

		for (int i = 0; i < m; i++) {
			int input;
			cin >> input;
			if (input <= 400000) {
				B[input] = true;
			}
		}

		if (n < k / 2 || m < k / 2) {
			cout << "NO" << '\n';
			continue;
		}

		int ao = 0;
		int bo = 0;
		int both = 0;
		int none = 0;
		for (int i = 1; i <= k; i++) {
			if (A[i]) {
				if (B[i]) {
					both++;
				}
				else {
					ao++;
				}
			}
			else {
				if (B[i]) {
					bo++;;
				}
				else {
					none++;
				}
			}
		}

		if (none > 0) {
			cout << "NO" << '\n';
		}
		else {
			if (both + bo >= k / 2 && both + ao >= k / 2) {
				cout << "YES" << '\n';
			}
			else {
				cout << "NO" << '\n';
			}
		}
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

3번의 WA와 2번의 TLE를 받고 나서야 맞은 그 문제.

풀이는 간단하다. a와 b를 입력받을때 어떤 원소를 두번 뽑을 일은 없으므로 A, B배열을 만들어 각 원소에 대한 존재유무만 boolean으로 관리한다. (A[i] == true라면 a에 i가 존재한다.)

그리고 i를 1부터 k까지 증가시키며 스위핑을 한다.

1) A[i] || B[i] 가 false인 i가 존재한다면 답은 무조건 No이다.

2) A[i] == true && B[i] == false이면 a에서 골라야 한다. 반대의 경우도 마찬가지이다. 이렇게 a에서만, b에서만 고를 수 있는 개수를 각각 ao, bo라는 변수에 저장한다.

3) A[i] && B[i]가 true라면 a, b중 어디서든 골라도 되므로 both라는 변수를 1증가시킨다.

이렇게 하고 나면, ac > k / 2이거나 bc > k / 2가 아니라면 both를 적절히 분배해서 양쪽에서 k / 2개씩 뽑을 수 있으므로 Yes이다.

대회 할 당시에는 생각을 편하게 하기 위해 b에서 k / 2개 있상 뽑을 수 있고(both + bo >= k / 2), 반대의 경우도 성립할 때 Yes를 출력하는 식으로 구현했다.

 

이 풀이에서 A와 B배열이 1~k까지의 인덱스를 커버하면 되는데,

2≤k≤2⋅min(n,m) 이 조건을 보고 n, m모두 최대 200000이므로 배열 크기를 200001로 잡았다가 3번 틀렸다.

이 조건을 고치고 나서 부터 TLE를 받았는데, A, B배열을 초기화하는 부분이 문제였다. 원래 0~400001까지 모두 false로 초기화하도록 코드를 짰는데, 테스크케이스가 최대 10000개이므로 40억 byte를 false로 초기화하게 되었다. fill이 아무리 빨라도 무리가 있었던 것 같다.

결국 필요한 경우에만 필요한 만큼 배열을 초기화하도록 코드를 고치고 첫 제출로부터 52분이 지나서야 AC를 받을 수 있었다.

 

C가 말려서 결국 어떻게든 F를 풀 의지가 생겼고, 결과적으로는 잘 됐지만, 이런 잔 실수를 조심해야 할 것 같다.

 

D. Find the Different Ones!

https://codeforces.com/contest/1927/problem/D

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int table[200000];

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n;
		cin >> n;

		int curr;
		cin >> curr;
		int idx = 0;
		for (int i = 1; i < n; i++) {
			int next;
			cin >> next;

			if (next != curr) {
				for (int j = idx; j < i; j++) {
					table[j] = i;
				}
				curr = next;
				idx = i;
			}
		}
		for (int i = idx; i < n; i++) {
			table[i] = n;
		}

		int q;
		cin >> q;
		for (int i = 0; i < q; i++) {
			int l, r;
			cin >> l >> r;
			l--, r--;

			if (table[l] > r) {
				cout << -1 << " " << -1 << '\n';
			}
			else {
				cout << l + 1 << " " << table[l] + 1 << '\n';
			}
		}
		cout << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

C에서 2번째 WA를 받고, D를 보고 바로 풀이가 나와서 8분만에 제출하고 AC를 받았다. 그리디한 접근이 가능한데, l, r이 입력되면 a[l] != a[i] (i > l)인 최소의 i가 r이하라면 l, r이 답이고, i가 r보다 크다면 a[l]~a[r]까지 전부 같은 것이므로 -1, -1을 출력하면 된다.

이제 a[l] != a[i]인 최소의 i를 찾는 것을 빠르게 하면 된다.

나이브하게 구현한다면 쿼리가 들어올 때마다 l~r까지 탐색하면 되고, 배열의 원소가 모두 같고 l, r구간이 가장 큰것만 들어온다면 O(N^2)시간이 걸려 TLE를 받게 된다.

 

f(k) = (i > k && a[i] > a[k]인 최소의 i값)이라 해보자. 연속된 구간에 대해서 f(k)값은 모두 같게 된다.

그러므로 f값을 저장할 table배열을 만들고, a를 스위핑하면서 연속된 구간들을 탐색하고, 값이 달라질때 마다 가장 최근 구간은 그 인덱스로 설정해줄 수 있다.

구간의 크기가 최대 N이므로 O(N^2)이 걸릴 것 같지만, 모든 구간의 길이 합이 N이므로 amortized O(N)시간 안에 전처리를 할 수 있다.

 

이후에 쿼리는 각각 O(1)시간에 처리할 수 있다.

잘 생각해보면 a[i] == a[i + 1]일경우 table[i] = table[i + 1]이고, a[i] != a[i + 1]이면 table[i] = i + 1이므로 DP로 테이블을 뒤에서부터 전처리하는 것이 가장 깔끔했을 것 같지만, 어쨌든 풀었으니 됐다.

 

E. Klever Permutation

https://codeforces.com/contest/1927/problem/E

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>

using namespace std;

int res[200000];

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n, k;
		cin >> n >> k;

		bool up = true;
		int start = 1;
		int end = n;

		for (int i = 0; i < k; i++) {
			if (up) {
				for (int j = i; j < n; j += k) {
					res[j] = start;
					start++;
				}
			}
			else {
				for (int j = i; j < n; j += k) {
					res[j] = end;
					end--;
				}
			}
			up = !up;
		}

		for (int i = 0; i < n; i++) {
			cout << res[i] << " ";
		}
		cout << '\n';
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

이 문제도 D를 풀고 나서 보자마자 풀이가 나오고, 11분만에 제출해서 AC가 나왔다. 문제에서 요구하는 것은 굉장히 단순하다. 어떤 permutation을 슬라이딩 윈도우로 훓었을 때, 가장 큰 값과 가장 작은 값이 1이하로 차이 나면 된다.

몇가지 관찰과 증명을 하면 구현은 굉장히 단순해지는, 코포스러운 문제였다.

 

1) s[i]와 s[i]+1은 무조건 1이 차이난다.

s[i] = a[i] + ... + a[i + k - 1], s[i + 1] = a[i + 1] + ... + a[i + k]이므로 s[i + 1] - s[i] = a[i + k] - a[i]이다. 이때, a의 모든 원소는 서로 다르므로 s[i + 1] - s[i] != 0이고, s[i + 1] - s[i]의 절대값이 2 이상이라면 문제의 조건에 위배되기 때문에 abs(s[i + 1] - s[i]) == 1이 성립한다.

 

2) s[i] - s[i  - 1] == 1이라면 s[i + 1] - s[i] == -1이다.

관찰 1) 로 인해서 s[i + 1] - s[i] == 1 or -1이다. 이때 s[i + 1] - s[i] == 1이라면 s[i + 1] - s[i - 1] == 2이므로 문제의 조건에 위배된다.

 

관찰 2에 의해서 s[i]는 1씩 증가했다 감소하는 수열을 이룬다.

그 조건을 만족시키는 a는 a[k] = a[0] + 1, a[k + 1] = a[1] - 1 ... a[k + p] = a[p] + (-1)^p이 된다. low = 1, high = n으로 잡고 a[0]부터 k칸씩 건너뛰며 잘 채우면 조건을 만족시키는 a를 쉽게 만들 수 있다.

 

F. Microcycle

https://codeforces.com/contest/1927/problem/F

더보기 
/*
여호와를 경외하는 것이 지혜의 근본이요 거룩하신 자를 아는 것이 명철이니라
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

// uf
int uftable[200001];

int find(int a) {
	if (uftable[a] <= 0) {
		return a;
	}

	int r = find(uftable[a]);
	uftable[a] = r;
	return r;
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) {
		return false;
	}

	uftable[b] = a;
	return true;
}

// kruskal
class Edge {
public:
	int u, v, w;
	Edge() {}
	Edge(int u, int v, int w) : u(u), v(v), w(w) {}
	bool operator < (const Edge& e) const {
		return w < e.w;
	}
};

Edge edges[200000];
bool used[200000];

vector<int> tree[200001];

bool DFS(int p, int o, stack<int>& edges, int target) {
	edges.push(p);
	if (target == p) {
		return true;
	}

	bool flag = false;
	for (int n : tree[p]) {
		if (n == o) {
			continue;
		}

		if (DFS(n, p, edges, target)) {
			flag = true;
			break;
		}
	}

	if (!flag) {
		edges.pop();
	}
	return flag;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int T;
	cin >> T;

	for (int tc = 0; tc < T; tc++) {
		int n, m;
		cin >> n >> m;

		for (int i = 0; i < m; i++) {
			int u, v, w;
			cin >> u >> v >> w;

			edges[i] = Edge(u, v, w);
		}

		sort(&edges[0], &edges[m]);

		fill(&used[0], &used[m], false);
		fill(&uftable[0], &uftable[n + 1], 0);
		fill(&tree[0], &tree[n + 1], vector<int>());
		for (int i = m - 1; i >= 0; i--) {
			int u = edges[i].u;
			int v = edges[i].v;

			if (merge(u, v)) {
				tree[u].push_back(v);
				tree[v].push_back(u);
				used[i] = true;
			}
		}

		for (int i = 0; i < m; i++) {
			if (!used[i]) {
				stack<int> res;
				DFS(edges[i].u, 0, res, edges[i].v);

				cout << edges[i].w << " " << res.size() << '\n';
				while (!res.empty()) {
					cout << res.top() << " "; res.pop();
				}
				cout << '\n';
				break;
			}
		}
	}

	return 0;
}

/*
싸울 날을 위하여 마병을 예비하거니와 이김은 여호와께 있느니라
*/

C에서 패널티는 다 모은 뒤에, 억울해서라도 F를 풀어야겠다는 생각을 하고 문제를 봤다. 다행이 문제가 내가 좋아하는 그래프를 스패닝트리로 만들고 LCA를 돌리는 류의 문제라 마음을 비우고 코드를 2KB정도 뽑아내서 AC를 받았다.

사이클을 찾는 여러가지 방법이 있는데, 그중에서 스패닝 트리를 만들고 스패닝 트리에 속하지 않은 에지가 연결하는 두 정점의 LCA(단순경로)를 구해서 사이클을 찾는 방법이 있다.

 

문제를 나이브하게 풀어보자. 간선을 가중치 순서대로 정렬한 후 가장 작은 가중치를 가진 간선부터 순서대로 보면서 그 간선이 사이클에 포함되는지 확인하면 가장 먼저 사이클이 확인될 때가 답이다. 이것을 구현하면 모든 에지에 대해 사이클 탐색을 위해서 DFS를 돌려야 하고, 각 간선에 대해 O(M)시간, 총 O(M^2)시간이 걸린다.

 

풀이를 최적화해보자. 풀이에서 가장 많은 시간을 잡아먹는 것은 어떤 간선이 사이클에 포함되는지 확인하는 부분이다. 위에서 언급한 스패닝 트리를 활용해보자. 크루스칼 알고리즘을 돌리면서 각 에지가 스패닝트리에 포함되었는지를 기록한다면(used배열) used가 false인 모든 에지는 사이클의 일부가 된다.

이 방법은 그냥 쓰기에는 무리가 있다. 정점 1, 2, 3이 있고, 간선 3개의 가중치가 a.1-2:3, b.2-3:2, c.3-1:1인데, a, c를 활용해서 스패닝 트리를 만든다면 used[c] = true이므로 최소 가중치인 c를 건너뛰게 된다.

이런 상황을 방지하기 위해서 간선의 가중치가 큰 순서부터 크루스칼을 돌린다. 그러면 사이클에서 가장 가중치가 작은 간선들은 크루스칼 알고리즘의 대상이 되지 않으므로 위의 풀이를 적용할 수 있다.

 

이제 문제에서 요구하는 사이클에 포함되는 에지 하나를 찾았다. 문제에서는 사이클 전체를 출력해야 한다. 이때 DFS를 활용할 수 있다. 크루스칼을 돌리면서 트리를 만들어놨고, 이후에 크루스칼의 대상이 되지 않은 최소 가중치 에지가 u, v를 연결한다고 하면 트리에서 u에서 v까지 가는 경로를 DFS로 찾으면 그것이 사이클의 나머지 부분이 된다.

풀이가 길긴 하지만 부분부분 나눠서 구현하다보면 AC를 받을 수 있다.

'알고리즘 > 코드포스' 카테고리의 다른 글

think-cell Round 1  (0) 2024.04.23
Codeforces Round 924 (Div. 2)  (1) 2024.04.12
Educational Codeforces Round 161 (Rated for Div. 2)  (1) 2024.04.04
Codeforces Round 920 (Div. 3)  (0) 2024.03.19
배치 여섯째 판  (3) 2024.02.13

'알고리즘/코드포스'의 다른글

  • 현재글Codeforces Round 923 (Div. 3) - 블루 달성

관련글

티스토리툴바