#Practice SCPC 2017 1차 예선 후기 및 풀이

5문제중 4문제를 해결해서 800점 만점에 550점을 흭득하였다.

5번문제는 읽고 어렵다고 생각해서 깊이 고민하지는 않았지만 만점자 수가 보여주듯이 어려운 문제로 보인다.

생각을 잘못한 상태로 코딩하는 습관때문에 1번에서 4번, 2번에서 1번 틀린코드를 제출하였다. 조금 더 신중하게 코딩에 들어가는 연습을 해야겠다. 코드는 정말 못짰다. 5번풀이는 없다.

1. 괄호

길이 n짜리 (,{,[,],},)으로 구성된 문자열이 입력으로 주어졌을때 가능한 모든 부 문자열중 가장 긴 올바른 괄호 문자열의 길이를 찾는 문제이다. (1<=n<=1,000,000)

Sol : 

스택을 이용해서 문제를 해결했다.

만약 어떤 시점에서 현재 매칭되지 않은 여는 괄호(스택의 맨위에 있는 괄호)와 짝이 맞지않는 닫는 괄호가 나온다면 그 앞에 있는 모든 문자열들은 무시할 수 있다는 성질을 활용해서 문제를 해결했다. (짝이 맞지않는 닫는 괄호를 누구와 매칭해야하나 생각하면 된다.)

어떤 닫는 괄호가 짝이 맞을때 그 길이를 답에 갱신해주면 문제를 해결할 수 있다.

Code : 

#include<stdio.h>
#include<vector>

using namespace std;

vector<char>ST;
vector<int>STW;

char S[1212121];
char J[256];
int main() {
	int t, tc;
	int i;
	int st;
	J['{'] = '}';
	J['['] = ']';
	J['('] = ')';
	scanf("%d", &t);
	for (tc = 0; tc < t; tc++) {
		scanf("%s", S);
		int ans = 0;

		ST.clear();
		STW.clear();
		STW.push_back(-1);
		for (i = 0; S[i]; i++) {
			if (S[i] == '(' || S[i] == '{' || S[i] == '[') {
				ST.push_back(S[i]);
				STW.push_back(i);
			}
			else {
				if (ST.empty() || J[ST.back()] != S[i]) {
					ST.clear();
					STW.clear();
					STW.push_back(i);
				}
				else {
					if (ans < i - STW[STW.size() - 2])
						ans = i - STW[STW.size() - 2];
					STW.pop_back();
					ST.pop_back();
				}
			}
		}
		printf("Case #%d\n%d\n", tc + 1, ans);
	}
	return 0;
}

2. 주식거래

n개의 숫자를 입력받아서 다음 조건을 만족시키는 가장 긴 부분 수열 X(연속할 필요 없음)의 길이를 출력하는 문제이다.

1. X[i*2]    < X[i*2+1]

2. X[i*2+1] > X[i*2+2]

Sol : 

D[i] = i번째 숫자를 홀수번째에 놓을 때 최대길이

F[i] = i번째 숫자를 짝수번째에 놓을 때 최대길이

로 놓으면 다음과 같은 점화식이 성립한다.

D[i] = max(F[j])+1 (j<i , A[j] < A[i])

F[i] = max(D[j])+1 (j<i,  A[j] > A[i])

이 처리를 단순 반복문이 아닌 max 인덱스 트리를 이용해서 해주면 문제를 해결할 수 있다.

Code :

#include<stdio.h>
#include<algorithm>

using namespace std;

struct xy {
	int x, y;
};

int a[212121];
xy b[212121];
int Ra[212121];
int Rb[212121];

bool sort_x_s(xy a, xy b) {
	if (a.x == b.x)return a.y > b.y;
	return a.x < b.x;
}
bool sort_x_b(xy a, xy b) {
	if (a.x == b.x)return a.y > b.y;
	return a.x > b.x;
}
int tn;
int tree[2][818181];

void insert_g(bool flag,int w, int g) {
	int i;
	for (i = tn + w; i > 0; i /= 2) {
		if (tree[flag][i] < g)tree[flag][i] = g;
	}
}

int search_g(int flag,int ss, int ee) {
	int s = ss + tn;
	int e = ee + tn;
	int res = 0;
	while (s <= e) {
		if (s % 2 == 1) {
			if (res < tree[flag][s])res = tree[flag][s];
			s++;
		}
		if (e % 2 == 0) {
			if (res < tree[flag][e])res = tree[flag][e];
			e--;
		}
		s /= 2;
		e /= 2;
	}
	return res;
}

int D[212121];
int F[212121];

int main() {
	int t, tc;
	scanf("%d", &t);
	for (tc = 0; tc < t; tc++) {
		int n;
		int i, j;
		scanf("%d", &n);
		for (tn = 1; tn < n + 1; tn *= 2);
		for (i = 0; i < tn * 2; i++) {
			tree[0][i] = 0;
			tree[1][i] = 0;
		}

		for (i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			b[i].x = a[i];
			b[i].y = i;
		}
		sort(b + 1, b + n + 1, sort_x_s);
		for (i = 1; i <= n; i++) {
			Ra[b[i].y] = i;
		}
		sort(b + 1, b + n + 1, sort_x_b);
		for (i = 1; i <= n; i++) {
			Rb[b[i].y] = i;
		}
		int ans = 0;
		for (i = 1; i <= n; i++) {
			int k = search_g(1, 1, Ra[i] - 1);
			if (k != 0) {
				D[i] = k + 1;
				insert_g(0, Rb[i], D[i]);
			}
			F[i] = search_g(0, 1, Rb[i] - 1) + 1;
			insert_g(1, Ra[i], F[i]);
			if (ans < D[i])ans = D[i];
		}
		printf("Case #%d\n%d\n",tc+1, ans);
		for (i = 1; i <= n; i++) {
			D[i] = 0;
			F[i] = 0;
		}
	}
	return 0;
}

3. 전광판

N*M크기의 전광판이 입력으로 주어지고, 각 전구는 정확히 2개의 스위치와 연결되어있을때, 모든 N*M개의 전구를 킬 수 있는 조합을 찾는 문제이다.

2-SAT을 이용하는 문제인데 138명이나 풀어서 놀랐다.

Sol : 

각 스위치에 대해 그 스위치를 누른경우 1, 누르지 않은경우를 0이라 하자.

스위치 a,b와 연결이 되어 있는 전구에 대해서 생각해보자.

1) 전구가 꺼져있는 경우

a와 b가 둘다 0이거나 둘다 1이어야 한다.

(a&b)|(~a&~b) = (a|~b)&(~a|b)로 표현 할 수  있다.

2) 전구가 켜져있는 경우

a와 b중 하나만 1이어야 한다.

(a&~b)|(~a&b) = (a|b)&(~a|~b)로 표현할 수 있다.

그럼 이제 모든 전구에 대해서 명제가 생기는데 그럼 본 문제는 모든 명제를 다 AND연산한 함수를 참으로 만드는 스위치의 상태를 묻는 문제로 바뀐다.

그리고 이는 2-SAT형태이다.

2-SAT문제를 해결해서 가능한지 불가능한지 판별하고, 가능한 경우 임의의 한 상태를 출력해주면 된다.

임의의 한 상태를 구하는 방법(역추적)은 p->q일때 ~p이면 전체 명제에 영향을 끼치지 않는다는 성질을 이용해서 해결해주면 된다.

Code:

#include<stdio.h>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;

map<int, int>RM;
map<int, int>CM;
int n;
int nm[30000];
vector<int>edge[101313];
vector<int>redge[101313];

bool is_gone[121212];

vector<int>end_list;

void dfs(int w) {
	int i;
	is_gone[w] = 1;
	for (i = 0; i < edge[w].size(); i ++) {
		if (is_gone[edge[w][i]])continue;
		dfs(edge[w][i]);
	}
	end_list.push_back(w);
}

bool is_gone_scc[121212];
int scc_num[121212];
int scc_cnt;
void dfs_scc(int w) {
	int i;
	is_gone_scc[w] = 1;
	scc_num[w] = scc_cnt;
	for (i = 0; i < redge[w].size(); i++) {
		if (is_gone_scc[redge[w][i]])continue;
		dfs_scc(redge[w][i]);
	}
}

void SCC() {
	int i;
	for (i = 0; i < n * 2; i++) {
		is_gone[i] = 0;
		is_gone_scc[i] = 0;
		scc_num[i] = 0;
	}
	scc_cnt = 1;
	end_list.clear();
	for (i = 0; i < n*2; i++) {
		if (is_gone[i])continue;
		dfs(i);
	}
	while(!end_list.empty()){
		int now = end_list.back();
		end_list.pop_back();
		if (is_gone_scc[now])continue;
		dfs_scc(now);
		scc_cnt++;
	}
}

void make_edge(int a, int b) {
	edge[a].push_back(b);
	redge[b].push_back(a);
}

struct xy {
	int x, y;
};
xy T[121212];
int res[121212];
bool sort_x(xy a, xy b) {
	if (a.x == b.x)return a.y < b.y;
	return a.x > b.x;
}

int main() {
	int t, tc;
	scanf("%d", &t);
	for (tc = 0; tc < t; tc++) {
		printf("Case #%d\n", tc + 1);
		int r, c;
		int i, j;

		RM.clear();
		CM.clear();
		scanf("%d%d", &r, &c);
		n = 0;

		for (i = 0; i < r; i++) {
			for (j = 0; j < c; j++) {
				int a, b, c;
				scanf("%d%d%d", &a, &b, &c);
				if (RM.find(i * 100 + b) == RM.end()) {
					RM[i * 100 + b] = n;
					nm[n] = 10000 + i * 100 + b;
					n++;
				}
				if (CM.find(j * 100 + c) == CM.end()) {
					CM[j * 100 + c] = n;
					nm[n] = 20000 + j * 100 + c;
					n++;
				}
				if (a == 1) { // s |   e & ~s | ~e
					int s = RM[i * 100 + b];
					int e = CM[j * 100 + c];
					make_edge(s * 2 + 1, e * 2 + 1);
					make_edge(e * 2, s * 2);
					make_edge(s * 2 , e * 2);
					make_edge(e * 2 + 1, s * 2 + 1);
				}
				else {
					int s = RM[i * 100 + b];
					int e = CM[j * 100 + c];
					make_edge(s * 2 + 1, e * 2);
					make_edge(e * 2 + 1, s * 2);
					make_edge(s * 2, e * 2 + 1);
					make_edge(e * 2, s * 2 + 1);
				}
			}
		}
		SCC();
		for (i = 0; i < n * 2; i++) {
			edge[i].clear();
			redge[i].clear();
		}
		bool flag=1;
		for (i = 0; i < n; i++) {
			if (scc_num[i*2] == scc_num[i * 2 + 1])
				flag = 0;
		}
		if (!flag) {
			printf("Impossible\n");
			continue;
		}
		for (i = 0; i < 2 * n; i++) {
			T[i].x = scc_num[i];
			T[i].y = i;
		}
		for (i = 0; i < n; i++) {
			res[i] = -1;
		}
		sort(T, T + 2 * n, sort_x);
		for (i = 0; i < 2 * n; i++) {
			if (res[T[i].y/2] == -1) {
				res[T[i].y / 2] = !(T[i].y%2);
			}
		}
		for (i = 0; i < n; i++) {
			if (res[i] == 1) {
				if (nm[i] / 10000 == 1) {
					printf("R%04d ", nm[i] % 10000);
				}
				else {
					printf("C%04d ", nm[i] % 10000);
				}
			}
		}
		printf("\n");
	}
	return 0;
}

4. Monotone

단순 다각형을 구성하는 N개의 점이 반시계방향순서로 입력으로 주어졌을때, 이 단순 다각형이 단조 다각형인지를 묻는 문제이다.(1<=N<=50,000)

Sol : 

반시계방향으로 점을 따라가다가 ccw의 값이 0보다 작을때 가운데 점을 기준으로 각도를 만든다.

모든 나온 각도들의 교집합이 공집합이라면 NO

공집합이 아니라면 YES를 출력하면 된다.

Code : 

#include<stdio.h>
#include<vector>

using namespace std;

struct xy {
	int x, y;
};

xy a[51515];
int ccw(xy a, xy b, xy c) {
	long long g = (long long)a.x*b.y + (long long)b.x*c.y + (long long)c.x*a.y - (long long)a.y*b.x - (long long)b.y*c.x - (long long)c.y*a.x;
	if (g > 0)return 1;
	if (g < 0)return -1;
	return 0;
	
}

struct v {
	xy a, b;
};

vector<v>V;

int main() {
	int t, tc;
	int i, j;
	v now;
	scanf("%d", &t);
	for (tc = 0; tc < t; tc++) {
		printf("Case #%d\n", tc + 1);
		int n;
		scanf("%d", &n);
		for (i = 0; i < n; i++) {
			scanf("%d%d", &a[i].x, &a[i].y);
		}
		a[n] = a[0];
		a[n + 1] = a[1];
		V.clear();
		for (i = 0; i < n; i++) {
			if (ccw(a[i], a[i + 1], a[i + 2])==-1) {
				v temp;
				temp.a.x = a[i].x - a[i + 1].x;
				temp.a.y = a[i].y - a[i + 1].y;
				temp.b.x = a[i + 2].x - a[i + 1].x;
				temp.b.y = a[i + 2].y - a[i + 1].y;
				V.push_back(temp);
			}
		}
		if (V.size() == 0) {
			printf("YES\n");
			continue;
		}
		now = V[0];
		xy ori = { 0,0 };
		bool flag = 1;
		for (i = 1; i < V.size(); i++) {
			if (ccw(ori, now.a, V[i].a) == 1)
				now.a = V[i].a;
			if (ccw(ori, now.b, V[i].b) == -1)
				now.b = V[i].b;
			if (ccw(ori, now.a, now.b) == -1) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	return 0;
}