GCJ 2017 Quals 후기

들어가며

대회 덕분에 오랜만에 또 문제풀이 코딩을 했다. 전부 풀긴 했는데 시간을 좀 오래 썼다. D에서 코딩 미스가 한 번 있었다. 문제풀이를 좀 쉬었을 때 풀 수 있는 문제 풀은 크게 안 변하는데, 코딩 속도나 풀이를 떠올리는 속도가 좀 줄어든 것 같다는 기분을 느꼈다.

풀이

Problem A. Oversized Pancake Flipper

같은 위치에서 두 번 뒤집는 것은 불필요하므로 왼쪽부터 하나씩 뒤집어보면 된다. $O(N^2)$ 으로 Large input이 풀리기 때문에 특별히 자료구조를 쓸 필요도 없다.

A.cpp

#include <cstdio>
#include <cstring>

const int MAX = 1020;

char cake[MAX];
int flipSize;

void solve() {
	int ans = 0;

	int len = strlen(cake);
	for (int i = 0; i <= len-flipSize; i++) {
		if (cake[i] == '-') {
			ans++;
			for (int j = i; j < i+flipSize; j++) {
				cake[j] = cake[j] == '+' ? '-' : '+';
			}
		}
	}

	// final check
	for (int i = len-flipSize+1; i < len; i++) {
		if (cake[i] == '-') {
			puts("IMPOSSIBLE");
			return;
		}
	}

	printf("%d\n", ans);
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s%d", cake, &flipSize);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem B. Tidy Numbers

입력이 tidy한 경우 그대로 출력한다. 입력이 tidy가 아닌 경우 112333445552 형태로 증가하다가 감소하는 지점이 있을텐데, 그 감소하기 직전의 반복되는 부분(여기서는 555)의 첫 숫자를 1 낮추고, 그 뒤쪽을 전부 9로 채우면 된다.

B.cpp

#include <cstdio>
#include <cstring>

const int MAX = 20;

char data[MAX];

void solve() {
	int len = strlen(data);
	int lastIncrease = 0;

	int now;
	for (now = 1; now < len; now++) {
		if (data[now-1] > data[now]) {
			break;
		} else if (data[now-1] < data[now]) {
			lastIncrease = now;
		}
	}

	if (now == len) {
		// monotonic
		puts(data);
	} else {
		char ans[MAX];
		for (int i = 0; i < lastIncrease; i++)
			ans[i] = data[i];
		ans[lastIncrease] = data[lastIncrease]-1;
		for (int i = lastIncrease+1; i < len; i++)
			ans[i] = '9';
		ans[len] = 0;

		for (int i = 0; i < data[i]; i++) {
			if (ans[i] != '0') {
				puts(ans+i);
				return;
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s", data);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem C. Bathroom Stalls

시뮬레이션으로 풀 수 있다. 당연히 한 명씩 넣는 건 아니고, 연속된 구간의 크기와 개수를 이용해 시뮬레이션 하면 지수적으로 수를 줄여나가면서 $O(log K)$ 만에 해결 가능하다. 한 가지 관찰이 필요한데, 반씩 줄여 나가는 방식으로 시뮬레이션 하더라도 어떤 시점에서 구간의 크기의 종류가 최대 두 종류라는 사실이다. (n) -> (a, a+1) -> (b, b+1)과 같이 연속한 두 수에 대해서만 관리하면 되고, atomic하게 처리하지 않는 경우에도 최대 네 종류만 관리하면 된다. 탐색 최대 크기가 작아 굳이 Balanced Binary Tree를 쓸 필요는 없었지만 코딩하기 귀찮아서 set을 발라서 해결했다.

C.cpp

#include <cstdio>
#include <set>

typedef long long ll;

ll total, k;

struct state {
	ll n;
	mutable ll count;

	bool operator < (const state &t) const {
		return n < t.n;
	}
};

void insertToSet(std::set < state > &set, ll n, ll count) {
	auto it = set.find(state {n, 0});
	if (it != set.end()) {
		it->count += count;
	} else {
		set.insert(state { n, count });
	}
}

void solve() {
	state start = { total, 1 };

	std::set < state > set;
	set.insert(start);

	while (k) {
		auto it = --set.end();
		if (it->count >= k) {
			printf("%lld %lld\n", it->n/2, (it->n-1)/2);
			return;
		} else {
			k -= it->count;
			insertToSet(set, it->n/2, it->count);
			insertToSet(set, (it->n-1)/2, it->count);
			set.erase(it);
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%lld%lld", &total, &k);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem D. Fashion Show

굉장히 마음에 드는 문제였다. 독립된 두 개의 문제를 하나의 문제인 것처럼 섞어서 꼬아 놓았는데, 두 제한조건이 사실 독립이라는 것을 깨달아야 해결할 수 있다. 임의의 같은 가로줄/세로줄에 있는 두 모델을 골랐을 때 둘 중 최소 하나가 +여야 한다는 말은, 바꿔서 말하면 +가 아닌 칸은 같은 가로줄/세로줄에 최대 하나 존재할 수 있다는 말이다. 비숍 배치 문제처럼 가로세로, 대각선 조건에 대해 각각 이분매칭으로 해결한 뒤 겹치는 칸은 o로, 겹치지 않는 칸은 x와 +로 설정해 주면 된다.

D.cpp

#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 110;

class BipartiteMatcher {
public:
	const int size;
	int *matched;
	bool *visited;

	vector < int > *edge;

	BipartiteMatcher(int size) : size(size) {
		matched = new int[2*size];
		visited = new bool[2*size];
		edge = new vector < int >[2*size];

		for (int i = 0; i < 2*size; i++) {
			matched[i] = -1;
		}
	}

	~BipartiteMatcher() {
		delete[] matched;
		delete[] visited;
		delete[] edge;
	}

	void addConnection(int a, int b) {
		assert(0 <= a && a < size && 0 <= b && b < size);
		b += size;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	vector < pair < int, int > > match() {
		for (int left = 0; left < size; left++) {
			memset(visited, 0, sizeof(bool)*(2*size));
			tryMatch(left);
		}

		vector < pair < int, int > > ret;
		for (int left = 0; left < size; left++) {
			if (matched[left] != -1) {
				ret.push_back(make_pair(left, matched[left]-size));
			}
		}

		return ret;
	}

private: 
	bool tryMatch(int left) {
		for (auto right : edge[left]) {
			if (!visited[right]) {
				visited[right] = 1;
				if (matched[right] < 0 || tryMatch(matched[right])) {
					matched[right] = left;
					matched[left] = right;
					return 1;
				}
			}
		}
		return 0;
	}
};

int gridSize, numModel;
char original[MAX][MAX], ans[MAX][MAX];

void input() {
	scanf("%d%d", &gridSize, &numModel);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			original[r][c] = '.';
		}
		original[r][gridSize+1] = 0;
		ans[r][gridSize+1] = 0;
	}

	for (int i = 0; i < numModel; i++) {
		char t[2];
		int r, c;
		scanf("%s%d%d", t, &r, &c);
		original[r][c] = t[0];
	}

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			ans[r][c] = original[r][c];
		}
	}
}

bool rowCheck[MAX], colCheck[MAX], ldiagCheck[MAX*2], rdiagCheck[MAX*2];

void solve() {
	memset(rowCheck, 0, sizeof(rowCheck));
	memset(colCheck, 0, sizeof(colCheck));
	memset(ldiagCheck, 0, sizeof(ldiagCheck));
	memset(rdiagCheck, 0, sizeof(rdiagCheck));

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;
			if (ans[r][c] != '.') {
				if (ans[r][c] != '+') {
					rowCheck[rowNum] = 1;
					colCheck[colNum] = 1;
				}
				if (ans[r][c] != 'x') {
					ldiagCheck[ldiagNum] = 1;
					rdiagCheck[rdiagNum] = 1;
				}
			}
		}
	}

	BipartiteMatcher xy(gridSize), diag(gridSize*2-1);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;

			if (!rowCheck[rowNum] && !colCheck[colNum]) {
				xy.addConnection(rowNum, colNum);
			}
			if (!ldiagCheck[ldiagNum] && !rdiagCheck[rdiagNum]) {
				diag.addConnection(ldiagNum, rdiagNum);
			}
		}
	}

	for (auto p: xy.match()) {
		int rowNum = p.first;
		int colNum = p.second;

		int r = rowNum+1;
		int c = colNum+1;

		if (ans[r][c] == '.') ans[r][c] = 'x';
		else if (ans[r][c] == '+') ans[r][c] = 'o';
	}

	for (auto p: diag.match()) {
		int ldiagNum = p.first;
		int rdiagNum = p.second;

		int r = (ldiagNum+rdiagNum-gridSize+3)/2;
		int c = (ldiagNum-rdiagNum+gridSize+1)/2;
		
		if (ans[r][c] == '.') ans[r][c] = '+';
		else if (ans[r][c] == 'x') ans[r][c] = 'o';
	}

	int score = 0;
	int changed = 0;
	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				changed++;
			}
			score += ans[r][c] != '.';
			score += ans[r][c] == 'o';
		}
	}

	printf("%d %d\n", score, changed);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				printf("%c %d %d\n", ans[r][c], r, c);
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		input();

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

QwazLab

GCJ 2017 Quals 후기

들어가며

풀이

Problem A. Oversized Pancake Flipper

Problem B. Tidy Numbers

Problem C. Bathroom Stalls

Problem D. Fashion Show

댓글 남기기응답 취소

들어가며

풀이

Problem A. Oversized Pancake Flipper

Problem B. Tidy Numbers

Problem C. Bathroom Stalls

Problem D. Fashion Show

이 글 공유하기:

댓글 남기기응답 취소