Codeforces Round #322 (Div. 2)

Contest Problems / Contest Result

A. Vasya the Hipster

빨간 양말의 개수 a와 파란 양말의 개수 b가 주어졌을 때, 서로 다른 색으로 짝을 지을 수 있는 최대 양말 쌍의 개수와 그렇게 쌍을 지은 양말을 제외하고, 한 가지 양말 색깔만으로 만들 수 있는 양말 쌍의 개수를 출력하는 문제이다.

전자는 min(a, b)이고 후자는 (max(a, b)-min(a,b))/2이다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	int c = a;
	if (c > b) c = b;
	printf("%d ", c);
	a -= c;
	b -= c;
	printf("%d", max(a / 2, b / 2));
}

B. Luxurious Houses

n개의 건물 높이가 주어진다. 매 index의 건물 a( i )마다 오른쪽 건물들의 높이가 모두 a( i )보다 작아지려면, a( i )를 얼마나 증가시켜야 하는지 그 값을 출력하는 문제이다.

가장 큰 index부터 작은 index순으로 a( i )의 최댓값을 저장하여 O(N)에 해결할 수 있다.

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

C. Developing Skills

n개의 수 a( i )가 주어진다. total rating은 int( a( i ) / 10 )의 합으로 정의된다. 수열의 어떤 원소를 1 증가시키는 것을 1 improvement를 했다고 정의할 때(단, improve된 a( i )는 100 이하), 전체 수열 a에 k improvement를 하여 total rating을 최대화하는 것이 문제이다.

각 a( i )의 십의 자리 숫자를 증가시키는데 필요한 비용으로 오름차순 정렬한 다음에 가능한 한 최대한 improvement해보고, 모든 a( i )들의 십의 자리 숫자를 1번씩 증가시켜보았다면 100을 넘지 않는 선에서 k를 각 a( i )에 순서대로 분배하는 greedy algorithm으로 해결 가능하다. O(n log n)이다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, k, a[100005], m, b[100005], v;
long long res;
inline bool cmp(int x, int y) {
	return (x / 10 + 1) * 10 - x < (y / 10 + 1) * 10 - y;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (a[i] == 100) {
			res += 10;
			n--; i--;
		}
	}
	while (n && k) {
		sort(a + 1, a + n + 1, cmp);
		for (int i = 1; i <= n; i++) {
			v = (a[i] / 10 + 1) * 10 - a[i];
			if (k < v) {
				k = 0;
				break;
			}
			else k -= v;
			a[i] = (a[i] / 10 + 1) * 10;
		}
		m = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == 100) {
				res += 10;
				continue;
			}
			b[++m] = a[i];
		}
		n = m;
		for (int i = 1; i <= n; i++) a[i] = b[i];
	}
	for (int i = 1; i <= n; i++) res += a[i] / 10;
	printf("%I64d", res);
}

D. Three Logos

3개의 직사각형이 주어지면 그걸 잘 배치해서 하나의 정사각형으로 만드는 문제이다.

일반화를 잘 시켜서 아래와 같이 해결할 수 있다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int ok;
void chk(int x1, int y1, int x2, int y2, int x3, int y3, char A, char B, char C) {
	if (x1 + x2 == x3 && y1 == y2 && y1 + y3 == x3) {
		ok = x3;
		printf("%d\n", x3);
		for (int i = 1; i <= x3; i++) {
			for (int j = 1; j <= y1; j++) {
				if (i <= x1) printf("%c", A);
				else printf("%c", B);
			}
			for (int j = 1; j <= y3; j++) printf("%c", C);
			puts("");
		}
	}
}
void solve(int x1, int y1, int x2, int y2, int x3, int y3) {
	if (ok) return;
	if (x1 + x2 + x3 == y1 && y1 == y2 && y1 == y3) {
		ok = y1;
		printf("%d\n", y1);
		for (int i = 1; i <= x1; i++) {
			for (int j = 1; j <= y1; j++) printf("A");
			puts("");
		}
		for (int i = 1; i <= x2; i++) {
			for (int j = 1; j <= y2; j++) printf("B");
			puts("");
		}
		for (int i = 1; i <= x3; i++) {
			for (int j = 1; j <= y3; j++) printf("C");
			puts("");
		}
		return;
	}
	chk(x1, y1, x2, y2, x3, y3, 'A', 'B', 'C');
	chk(x1, y1, x3, y3, x2, y2, 'A', 'C', 'B');
	chk(x2, y2, x3, y3, x1, y1, 'B', 'C', 'A');
}
int main() {
	int x1, x2, x3, y1, y2, y3;
	scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				solve(x1, y1, x2, y2, x3, y3);
				swap(x3, y3);
			}
			swap(x2, y2);
		}
		swap(x1, y1);
	}
	if (!ok) puts("-1");
}

F. Zublicanes and Mumocrates

n개의 정점과 n-1개의 간선으로 구성된 트리가 주어진다. 이 때, 각 정점들에 2가지 종류의 색깔을 반드시 칠해야한다. 색칠을 다 했을 때, (항상 짝수개인) 말단 노드들은 2가지 종류의 색깔로 균등하게 색칠되어야 한다. 조건에 맞게 색칠을 하면서, 간선 양쪽의 정점에 서로 다른 색깔이 칠해진 간선의 수를 최소화해야하는 것이 문제이다.

D( a , b , c ) : a번 노드의 색깔이 c(0 또는 1)이고 a의 부트리(a를 포함) 중 말단 노드의 색깔이 0인 것의 개수가 b개일 때, a의 부트리 간선들 중 간선 양쪽 정점에 서로 다른 색깔이 칠해진 것들의 최소 갯수

어떤 노드 a를 고려할 때, a의 자식들에 대한 계산은 끝났다고 가정하고(말단 노드인 경우는 별도의 계산없이 초기화만 해주면 되므로), a의 자식들이 p(1), p(2), ... p(k)가 있다고 하자.

이제 냅색하듯이 T(x, i+j, x_color) = min ( T(x, i+j, x_color), D(x, i, x_color) + D(p(k), j, p(k)_color + (x_color != p(k)_color) ) 라는 점화식으로 매 p(k)마다 D(x)를 T(x)로 갱신해주면 된다. D(x)에 누적해서 계산하다보면 p(k-1)까지 고려한 것과 p(k)까지 고려하는 것이 뒤섞이므로 저런식으로 테이블을 채웠다.

각 노드 a의 dp값인 D(a)의 상태들에 대한 정보를 처음에 D(a)를 채울 때 한 번, a의 부모에서 D(a)를 참조할 때 한 번 더 참조한다. 따라서 각 상태에 대해서 상수번의 참조만이 일어나므로 의 시간복잡도를 가진다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MN 5005
const int oo = (int)(1e9);
int n, sz[MN], d[MN][MN][2], t[MN][2];
vector <int> v[MN];
void dfs(int x, int par) {
	if (v[x].size() == 1) {
		d[x][1][0] = d[x][0][1] = oo;
		sz[x] = 1;
		return;
	}
	for (int k = 0; k < v[x].size(); k++) {
		int u = v[x][k];
		if (u == par) continue;
		dfs(u, x);
		for (int i = 0; i <= sz[u] + sz[x]; i++) t[i][0] = t[i][1] = oo;
		for (int i = 0; i <= sz[x]; i++) {
			for (int j = 0; j <= sz[u]; j++) {
				for (int xc = 0; xc < 2; xc++) {
					for (int vc = 0; vc < 2; vc++) {
						if (t[i + j][xc] > d[x][i][xc] + d[u][j][vc] + (xc != vc))
							t[i + j][xc] = d[x][i][xc] + d[u][j][vc] + (xc != vc);
					}
				}
			}
		}
		sz[x] += sz[u];
		for (int i = 0; i <= sz[x]; i++) {
			d[x][i][0] = t[i][0];
			d[x][i][1] = t[i][1];
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int p, q;
		scanf("%d%d", &p, &q);
		v[p].push_back(q);
		v[q].push_back(p);
	}
	if (n == 2) puts("1");
	else {
		int res;
		for (int i = 1; i <= n; i++) {
			if (v[i].size() > 1) {
				dfs(i, 0);
				res = min(d[i][sz[i] / 2][0], d[i][sz[i] / 2][1]);
				break;
			}
		}
		printf("%d", res);
	}
}