Codeforces Round #459 (Div. 2)

A. Eleven

  주어진 길이에 대해 피보나치 수가 넘어가지 않을 때까지 'O'로 바꿔주기만 하면 된다.

#include <cstdio>
#include <cstring>
int main() {
	int N,a=1,b=1,t;
	char name[1001] = {};
	scanf("%d", &N);
	memset(name, 'o', N);
	name[0] = 'O';
	while (a + b <= N) {
		name[a + b - 1] = 'O';
		t = b;
		b = a + b;
		a = t;
	}
	printf("%s", name);
	return 0;
}

B. Radio Station

  map 등의 hashing 자료구조를 활용하여 해결할 수 있다. 문자열 통째로 key로 두던가 아니면 필자처럼 숫자로 변경해서 해싱을 진행해도 좋다.

#include <cstdio>
#include <map>
using namespace std;
using ll = long long;
int main() {
	map<ll, char*> pool;
	ll ip;
	int n, m, a, b, c, d;
	char *tmp,name[11];
	scanf("%d%d\n", &n, &m);
	while (n--) {
		ip = 0;
		tmp = new char[11]{};
		scanf("%s %d.%d.%d.%d\n", tmp, &a, &b, &c, &d);
		ip |= a; ip <<= 8;
		ip |= b; ip <<= 8;
		ip |= c; ip <<= 8;
		ip |= d;
		pool[ip] = tmp;
	}
	while (m--) {
		scanf("%s %d.%d.%d.%d;\n", name, &a, &b, &c, &d);
		ip = 0;
		ip |= a; ip <<= 8;
		ip |= b; ip <<= 8;
		ip |= c; ip <<= 8;
		ip |= d;
		printf("%s %d.%d.%d.%d; #%s\n", name, a, b, c, d, pool[ip]);
	}
	return 0;
}

C. The Monster

  두 가지 포인트에 집중한다.

1. 구간 (l,r)은 최대 길이 5000에 대해서 5000*(5001)/2 개의 조합이 나올 수 있다.

2. 구간 (l,r)에 대해 l을 고정한 것에 대해 l<r<L(문자열 s의 길이) 에 대해 (l,r)을 계산할 때 (l,r-1)을 이용할 수 있다(optimal substructure)

  1.에 의해 O(N^2) 솔루션이 가능하고, 2.에 의해 이중 for문 안에서 이전에 있던 위치값을 이용할 수 있음을 알 수 있다.

  +) 대부분 이런식으로 푼 것 같다. 구간에 대해 올바른 순서가 존재할 수 있는지만을 판단한다.

  1. left, right 구간을 줄 변수를 둔다. 구간 (i,j)에 대해 가상 left, right를 각각 l,r로 둔다. i부터 j까지 correct bracket sequence를 만족하면 l = 0이 된다. 반면 r이 음수일 경우 ')'로 시작하는 것이기에 이 때는 i로 시작하는 올바른 순서가 존재할 수 없다. r의 역할은 ?의 개수 및 (의 개수를 말한다. l의 역할은 현재 (인지와 ?가 (인지를 말한다.

  2. 가상 구간에 대해 문자에 따라 처리해준다.

2-1. (일 경우 : l++, r++

2-2. )일 경우 : l--, r--

2-3. ?일 경우 : l--, r++

자세한 내용은 에디토리얼에 나와 있다.

  

#include <cstdio>
#include <cstring>
int main() {
	char board[5001];
	int i, j,L,ans = 0,l,r;
	scanf("%s", board);
	L = strlen(board);
	for (i = 0; i < L; i++) {
		l = r = 0;
		for (j = i; j < L; j++) {
			if (board[j] == '(') l++, r++;
			else if (board[j] == ')') l--, r--;
			else l--, r++;
			if (r < 0) break;
			if (l < 0) l = 1;
			if (l == 0) ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

D. MADMAX

  제목처럼 서로 각 턴에 대해 많은 정점을 방문하면 이길 수 있게 되어 있다.

  또한 각 턴마다 상대방이 지난 간선 보다 ASCII Code 상 크거나 같은 값을 지닌 간선만 지나갈 수 있다. 본문에 쓰여있듯 경우의 수가 매우 많기 때문에 브루트 포스로 처리하기엔 너무 오래 걸린다. 또한 A(Max)와 B(Lucas)의 상태도를 나타면 100x100의 경우가 있으며 이전상태에 대해 소문자 알파벳의 총 수 26 가지가 존재하게 된다. 추가적으로 처음 게임을 시작할 때는 어떤 간선을 갈 수 있도록 설정해야하므로 1을 추가해준다. 따라서 명백하게 부분문제가 겹치는 것을 알 수 있으므로 dynamic programming을 진행한다.

cache[이전 알파벳][현재 A의 정점 위치][현재 B의 정점 위치]

시간 복잡도 : O(N^2)

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> adj;
int cache[27][100][100], board[100][100]; // NONE : 0, 'a' : 1
bool dfs(int bef, int vn, int rn) {
	int& ret = cache[bef][vn][rn];
	if (ret == -1) {
		ret = 0;
		for (int v : adj[rn])
			if (bef <= board[rn][v])
				if(!dfs(board[rn][v], v, vn)) ret = 1;
	}
	return ret;
}
int main() {
	memset(cache, -1, sizeof(cache));
	char ch;
	int n, m,u,v,A,B,i,j;
	scanf("%d%d", &n, &m);
	adj.resize(n);
	while (m--) {
		scanf("%d%d %c\n", &u, &v, &ch);
		u--, v--;
		adj[u].push_back(v);
		board[u][v] = ch - 'a' + 1;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			printf("%c", dfs(0, j, i) ? 'A' : 'B');
		puts("");
	}
	return 0;
}

E. Pollywog