제 3회 삼성전자 프로그래밍 경진대회(SCPC) 1차 예선 후기

대학생이 된 올해 SCPC에 처음으로 참가하게 되었다. 후기를 좀 늦게나마 써본다,, (내일이 2차 예선..)

작년에 비해 난이도가 상승한 것 같다. 만점자가 <= 6명...

1. 괄호

스택을 이용해 괄호를 매칭시키면서 답을 갱신한다. 닫는 괄호가 매칭이 안되면 스택을 초기화하고 다시 매칭을 시작한다.

()()()처럼 올바른 괄호가 여러 개 이어져 있는 경우를 체크하지 못해 한 번 실수했던 문제다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<cstdio> #include<iostream> using namespace std; char s[1000010], st[1000010]; int T, top, idx[1000010], l[1000010]; bool match(char a, char b) {     if(a == '(' && b == ')') return 1;     if(a == '[' && b == ']') return 1;     if(a == '{' && b == '}') return 1;     return 0; } int main() {     setbuf(stdout, NULL);     scanf("%d",&T);     for(int test = 1; test <= T; ++test) {         scanf("%s",s);         int res = 0;         top = l[0] = 0;         for(int i = 0; s[i]; ++i) {             if(s[i] == '(' || s[i] == '[' || s[i] == '{') {                 st[top] = s[i];                 idx[top] = i;                 l[++top] = 0;             } else {                 if(!top || !match(st[top - 1], s[i])) top = l[0] = 0;                 else {                     l[top - 1] += i - idx[top - 1] + 1;                     top--;                     res = max(res, l[top]);                 }             }         }         printf("Case #%d\n%d\n", test, res);     }     return 0; }

2. 주식거래

값이 증가하는 구간의 개수를 세면 된다. 여기서 증가하는 구간 [l, r]은 a[l - 1] > a[l], a[r] > a[r + 1], a[l] < a[r], a[i] <= a[i + 1] ( l <= i < r ) 을 만족함을 의미한다. (편의상 a[0] = INF, a[n + 1] = -INF 라고 하자.)

각 구간에서 제일 쌀 때 사고 제일 비쌀 때 판다고 생각하면 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<cstdio> #include<iostream> using namespace std; int T,n,a[200010],b[200010]; int main() {     setbuf(stdout, NULL);     scanf("%d", &T);     for(int test = 1; test <= T; ++test) {         scanf("%d", &n);         int res = 0, mn = a[0] = 2e9;         a[n+1] = 0;         for(int i=1;i<=n+1;i++) {             if(i <= n) scanf("%d", a+i);             if(a[i-1] > a[i]) {                 if(mn < a[i-1]) res += 2;                 mn = a[i];             }         }         printf("Case #%d\n%d\n", test, res);     }     return 0; }

3. 전광판

처음에 문제를 이해하는데 시간이 좀 걸렸다. 우선 각 전구가 2개의 스위치와 연결된다는 점에서 2-SAT으로 풀릴 것 같았다.

그러나 도무지 2-CNF 식이 생각나지 않았다. 고작 1차 예선 3번 문제가 2-SAT일까 싶어 다른 풀이를 생각해봤다.

결론적으로 DFS / BFS로 풀린다는 걸 깨달았다. 스위치 하나의 상태를 고정하면 그와 연결된 전구의 다른 스위치들의 모든 상태가 결정되기 때문에 스위치들을 독립된 그룹으로 묶을 수 있다. (Disjoint Set을 구현해도 된다.)

제출했더니 시간초과가 났다. 어이없게도 setbuf(NULL); 때문이었다. 부분점수를 받으려면 setbuf를 써야한다는데 일단 출력 속도가 매우 느려진다. 없애니까 만점을 받을 수 있었다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

#include<cstdio> #include<iostream> #include<queue> #include<vector> using namespace std; int T,n,m; int a[101][101], R[101][101], C[101][101]; int vr[2][101][101], vc[2][101][101]; int inresR[101][101], inresC[101][101]; vector<int> ri[101][101], ci[101][101]; bool is_possible(int x, int y, int r, int c, int trial) {     queue<pair<int,int> > q;     for(int j : ri[y][R[y][x]]) q.push({j,y});     for(int i : ci[x][C[y][x]]) q.push({x,i});     vr[trial][y][R[y][x]] = r;     vc[trial][x][C[y][x]] = c;     bool ret = 1;     while(!q.empty()) {         int nx = q.front().first;         int ny = q.front().second; q.pop();         int& stateR = vr[trial][ny][R[ny][nx]];         int& stateC = vc[trial][nx][C[ny][nx]];         if(stateR && stateC) {             if((a[ny][nx] + stateR + stateC) % 2 == 0) {                 ret = 0;                 break;             }         } else if(stateR) {             int afterState = 1 + (a[ny][nx] + stateR) % 2;             stateC = afterState;             for(int i : ci[nx][C[ny][nx]]) q.push({nx,i});         } else if(stateC) {             int afterState = 1 + (a[ny][nx] + stateC) % 2;             stateR = afterState;             for(int j : ri[ny][R[ny][nx]]) q.push({j,ny});         }     }     return ret; } int main() {     scanf("%d", &T);     for(int test = 1; test <= T; ++test) {         scanf("%d%d", &n, &m);         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {             ri[i][j-1].clear(), ci[j][i-1].clear();             for(int k=0;k<2;k++)                 vr[k][i][j-1] = vc[k][j][i-1] = 0;             inresR[i][j-1] = inresC[j][i-1] = 0;         }         for(int i=1;i<=n;i++)             for(int j=1;j<=m;j++) {                 scanf("%d%d%d", &a[i][j], &R[i][j], &C[i][j]);                 ri[i][R[i][j]].push_back(j);                 ci[j][C[i][j]].push_back(i);             }         bool flag = 1;         for(int i=1;i<=n;i++) {             for(int j=1;j<=m;j++) {                 if(vr[0][i][R[i][j]] || vc[0][j][C[i][j]] || vr[1][i][R[i][j]] || vc[1][j][C[i][j]]) continue;                 if(a[i][j] == 1) {                     if(is_possible(j, i, 2, 2, 0));                     else if(is_possible(j, i, 1, 1, 1));                     else {                         flag = 0;                         break;                     }                 } else {                     if(is_possible(j, i, 2, 1, 0));                     else if(is_possible(j, i, 1, 2, 1));                     else {                         flag = 0;                         break;                     }                 }             }             if(!flag) break;         }         printf("Case #%d\n", test);         if(!flag) puts("Impossible");         else {             for(int i=1;i<=n;i++) {                 for(int j=1;j<=m;j++) {                     if(vr[0][i][R[i][j]] == 1 || vr[1][i][R[i][j]] == 1)                         if(!inresR[i][R[i][j]]) {                             printf("R%02d%02d ", i - 1, R[i][j]);                             inresR[i][R[i][j]] = 1;                         }                     if(vc[0][j][C[i][j]] == 1 || vc[1][j][C[i][j]] == 1)                         if(!inresC[j][C[i][j]]) {                             printf("C%02d%02d ", j - 1, C[i][j]);                             inresC[j][C[i][j]] = 1;                         }                 }             }             puts("");         }     }     return 0; }

4. Monotone

오목한 지점의 각도 범위를 따져서 [0, pi) 범위를 모두 덮으면 NO, 아니면 YES를 출력한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<cmath> #define PI 3.14159265358979323846 using namespace std; typedef long long ll; int T,n; pair<int,int> p[50010]; vector<pair<double,double> > v; double a[50010]; ll cross(ll x1, ll y1, ll x2, ll y2) {     return x1 * y2 - x2 * y1; } int main() {     scanf("%d", &T);     for(int test = 1; test <= T; ++test) {         scanf("%d", &n);         for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);         for(int i=0;i<n;i++) {             int dx = p[(i+1)%n].first - p[i].first;             int dy = abs(p[(i+1)%n].second - p[i].second);             a[i] = atan2(dy, dx);         }         v.clear();         for(int i=0;i<n;i++) {             int i1 = i;             int i2 = (i + 1) % n;             int i3 = (i + 2) % n;             ll c = cross(p[i2].first - p[i1].first, p[i2].second - p[i1].second, p[i3].first - p[i2].first, p[i3].second - p[i2].second);             if(c < 0) v.push_back({a[i2], a[i1]});         }         sort(v.begin(), v.end());         double mx = 0;         for(int i=0;i<v.size();i++)             if(v[i].first > v[i].second)                 mx = max(mx, v[i].second);         bool flag = v.size() == 0;         for(int i=0;i<v.size();i++) {             if(mx < v[i].first) flag = 1;             if(v[i].first > v[i].second) mx = max(mx, v[i].second + 2 * PI);             else mx = max(mx, v[i].second);         }         printf("Case #%d\n%s\n", test, flag ? "YES" : "NO");     }     return 0; }

5. Covernent

나만 못 푸는 것 같아 자괴감이 들었던 문제.. ㅠ

우선 O(2^N logN) 풀이를 생각할 수 있었다. 몇 시간 동안 계속 고민해봤지만 그 이상의 진전은 없었다.

너무 졸린 탓에 그냥 O(2^N logN) 풀이로 부분 점수를 받고 잤다. MCMF로 풀린다는 후문이 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

#include<cstdio> #include<iostream> #include<vector> using namespace std; int n,m,T[2001][20],dep[2001],cost[2001],used[2001]; long long res; vector<pair<int,int> > adj[2001]; void prepare(int p, int u, int c) {     dep[u] = dep[p] + 1;     cost[u] = c;     T[u][0] = p;     for(int i = 1; i < 20; i++) T[u][i] = T[T[u][i-1]][i-1];     for(auto& v : adj[u]) if(v.first != p) prepare(u, v.first, v.second); } int lca(int a, int b) {     if(dep[a] < dep[b]) swap(a, b);     int k = dep[a] - dep[b];     for(int i = 0; k; i++, k >>= 1)         if(k & 1) a = T[a][i];     if(a == b) return a;     for(int i = 18; i >= 0; i--)         if(T[a][i+1] == T[b][i+1] && T[a][i] != T[b][i])             a = T[a][i], b = T[b][i];     return T[a][0]; } void solve(int pos, long long sum, int c) {     if(pos == n + 1) {         res = max(res, sum);         return;     }     for(int i = 0; i < 2; i++) {         int u = pos + i * n, nc = pos == 1 ? u : lca(c, u);         if(c) for(int v = c; v != nc; v = T[v][0]) {             used[v] = 1;             sum += cost[v];         }         while(u != nc && !used[u]) {             used[u] = 1;             sum += cost[u];             u = T[u][0];         }         solve(pos + 1, sum, nc);         if(c) for(int v = c; v != nc; v = T[v][0]) {             used[v] = 0;             sum -= cost[v];         }         for(int v = pos + i * n; v != u; v = T[v][0]) {             used[v] = 0;             sum -= cost[v];         }     } } int main() {     setbuf(stdout, NULL);     int _T;     scanf("%d", &_T);     for(int test = 1; test <= _T; ++test) {         scanf("%d%d", &n, &m);         for(int i = 1; i <= m; i++) {             adj[i].clear();             cost[i] = dep[i] = 0;             used[i] = 0;             for(int j = 0; j < 20; j++) T[i][j] = 0;         }         for(int i = 0,a,b,c; i < m - 1; i++) {             scanf("%d%d%d", &a, &b, &c);             adj[a].push_back({b,c});             adj[b].push_back({a,c});         }         prepare(0, m, 0);         res = 0;         solve(1, 0, 0);         printf("Case #%d\n%lld\n", test, res);     }     return 0; }