Codeforces Round #323

Contest Problems(Div.1) / Contest Problems(Div .2)

Div.2A-Asphalting Roads

가로로 n개, 세로로 n개의 도로가 있고, 교차로가 n*n개 있다. 가로와 세로 각각 1번부터 n번까지 번호가 붙여질 때, n*n개의 교차로가 주어졌을 때 그 교차로에서 만나는 가로 도로와 세로 도로 둘 다에 이미 아스팔트가 칠해지지 않았다면 아스팔트를 둘 다에 칠한다. 아스팔트를 칠하게 되는 교차로들을 출력하는 문제이다.

그냥 간단하게 체크해주면서 하라는대로 출력하면 된다.

#include <stdio.h>
int n, r[55], c[55];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n*n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (!r[x] && !c[y]) {
			r[x] = c[y] = 1;
			printf("%d ", i);
		}
	}
	return 0;
}

Div.2B-Robot's Task

컴퓨터가 n개 있고, 하나의 로봇이 있다. 로봇은 1번 컴퓨터에서부터 시작해서 돌아다니면서 컴퓨터를 해킹하고 다닌다. i번째 컴퓨터를 해킹하려면 a(i)개 이상의 컴퓨터를 해킹했어야한다. 돌아다니다보면 방향을 바꾸는 경우가 있을텐데, 모든 컴퓨터를 해킹하는데 필요한 최소 방향 전환 횟수를 출력하는 문제이다.

1번에서부터 n번까지 해킹할 수 있는 거 순서대로 다 해킹하고, 마지막으로 해킹했던 컴퓨터에서 1번 컴퓨터 방향으로 해킹하고...를 반복하다가 다 해킹했을 때 그만두면 된다.

#include <stdio.h>
int n, a[1005], b[1005];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int cnt = 0, m = n, d = 0, p = 1, res = -1;
	while (m) {
		res++;
		if (!d) {
			for (int i = p; i <= n; i++) {
				if (a[i] <= cnt && !b[i]) cnt++, p = i, b[i] = 1, m--;
			}
		}
		else {
			for (int i = p; i >= 1; i--) {
				if (a[i] <= cnt && !b[i]) cnt++, p = i, b[i] = 1, m--;
			}
		}
		d = !d;
	}
	printf("%d", res);
}

Div.1A/Div.2C-GCD Table

n개의 수 A(1), A(2), ... , A(n)이 있을 때, A(i)와 A(j) (1≤i,j≤n)의 최대공약수를 원소로 하는 n*n 행렬 G를 생각할 수 있다. G의 원소들이 주어졌을 때, 다시 A를 복원하는 것이 문제이다.

가장 먼저 발견할 수 있는 게, i=j인 경우 G(i,i)=A(i)이다. 그리고 G(i, k)나 G(k, i)는 A(i)보다 작거나 같다. 왜냐하면 G(i, k)나 G(k, i)는 A(i)와 A(k)의 최대공약수인데, 최대공약수는 두 수 중 최솟값보다 작거나 같기 때문이다. 편의상 A(1)≤A(2)≤...≤A(n)이라 하자. A(n)에 대해서 생각을 해보면, G(n, i)나 G(i, n)의 원소들은 다 A(n)보다 작거나 같을텐데, G(n, n)은 정의에 의해 A(n)과 같게 된다. 그런데 A(n)은 원소들 중 최댓값이므로 G(n, n) 역시 G의 원소들 중 최댓값이 된다. 따라서 G값 중 최댓값이 A의 최댓값과 같다.

이제 A(n)을 빼고 생각을 해보자. 그 다음 G의 최댓값은 G(n-1, n-1)이거나 G(n-1, n)이거나 G(n, n-1)일텐데, 3항 모두 A(n-1)보다 작거나 같다. 그리고 G(n-1, n-1)은 정의상 A(n-1)과 같다. 따라서 G(n-1, n-1)이 G(n, n-1)과 G(n-1, n) 이상이며 G의 남은 값들 중 최댓값이다. 따라서 G에서 2번째 최댓값이 A(n-1)이 된다. 여태 A(n)과 A(n-1)이 결정되었으므로, GCD(A(n), A(n-1))과 GCD(A(n-1), A(n))을 G에서 제거해주고 위의 과정을 귀납적으로 반복하면 된다.

#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
int n, g, a[505];
int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x%y);
}
int main() {
	scanf("%d", &n);
	multiset <int> s;
	for (int i = 1; i <= n*n; i++) scanf("%d", &g), s.insert(g);
	for (int i = 1; i <= n; i++) {
		multiset <int>::iterator p = s.end(); p--;
		a[i] = (*p);
		s.erase(p);
		for (int j = 1; j < i; j++) {
			int v = gcd(a[j], a[i]);
			s.erase(s.find(v));
			s.erase(s.find(v));
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", a[i]);
}

Div.1B/Div.2D-Once Again...

n*T의 원소를 가진 수열 A가 있다. 그런데 이 수열은 주기가 n이다. 즉, i>n일 때, A(i) = A(i-n)이다. 이러한 수열에 대해서 최장 비감소 부분수열의 길이를 구하는 것이 문제이다.

maxplus algebra를 써서 문제를 풀 수 있다. matrix M(i, j)을 원소 i에서 시작해서 j에서 끝이 날 때(반드시 j를 부분 수열에 포함시켜야한다), 최장 비감소 부분수열의 길이라고 정의한다. M(i, j)는 k<j인 모든 k에 대해서 A(k)≤A(j)라면 M(i, k)+1값들 중 최댓값으로 계산된다. 그러면 초기 행렬 M은 길이가 n인 수열에 대한 답을 들고 있고, M^2은 n*2, ... , M^T은 n*T인 수열에 대한 답으로 정의가 확장된다. 만약 A(i) > A(j)라면 -infinte값을 주어 행렬 연산 P(i, j) = max(Q(i, k) + R(k, j))연산에서 자동적으로 선택되지 않게 할 수 있다. 이 때, 주의할 점으로 i ≤j인 경우만 채우면 되는 것이 아니라 i>j인 경우도 고려를 해줘야한다. A(1), A(2), ... , A(j) 이전에 A(i)가 있었을 경우에 1~j에서의 답이 되는 것이다. 전체적인 시간복잡도는 가 된다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll oo = (1e12);
int n, T, a[105];
ll M[105][105], A[105][105], M2[105][105], R[105][105];
int main() {
	scanf("%d%d", &n, &T);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i] > a[j]) M[i][j] = -oo;
			else {
				M[i][j] = 1;
				for (int k = 1; k < j; k++) if (a[k] <= a[j] && M[i][j] < M[i][k] + 1) M[i][j] = M[i][k] + 1;
			}
		}
	}
	while (T) {
		if (T & 1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					M2[i][j] = -oo;
					for (int k = 1; k <= n; k++) M2[i][j] = max(M2[i][j], R[i][k] + M[k][j]);
				}
			}
			for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) R[i][j] = M2[i][j];
		}
		T /= 2;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				M2[i][j] = -oo;
				for (int k = 1; k <= n; k++) M2[i][j] = max(M2[i][j], M[i][k] + M[k][j]);
			}
		}
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) M[i][j] = M2[i][j];
	}
	ll res = 0;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) res = max(res, R[i][j]);
	printf("%I64d", res);
}