ls-al.me hello, world!

SCPC 2017 R1

올해도 찾아온 대회. 작년에 비해 전체적인 난이도가 상승했다고 느꼈다. 대회가 끝나고 문제가 닫혀버린 바람에 기억에 의지해서 작성해 본다.

100: 괄호

세 가지 종류의 괄호로 이루어진 문자열이 주어질 때 올바른 괄호인 부분분자열의 최대 길이를 구해야 한다.

첫 문제인데다가 자주 보는 소재여서 간단한 문제로 생각했는데 그렇지만은 않았다. 해답에 있어 중요한 아이디어는 앞에서부터 보면서 특정 부분문자열이 올바른 괄호가 아니게 되는 순간 무조건 지금까지의 스택을 비우고 새로 시작해야 한다는 부분이다. 문자열의 길이가 최대 이기 때문에 재귀함수를 사용할 수 없는데, 스택을 직접 구현하는 쪽이 오히려 편리하다.

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

using namespace std;

const int N = 1000000 + 10;

int tc;

int dyn[N];

char str[N];

int main() {
  scanf("%d", &tc);
  for(int t = 1; t <= tc; t++) {
    scanf("%s", str);
    stack<int> stk;
    int n = strlen(str);
    for (int i = 0; i < n; i++) {
      dyn[i] = 0;
      if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
        stk.push(i);
      } else {
        if (!stk.empty()) {
          int p = stk.top();
          stk.pop();
          if ((str[p] == '(' && str[i] == ')') ||
              (str[p] == '{' && str[i] == '}') ||
              (str[p] == '[' && str[i] == ']')) {
            dyn[p] = i - p + 1;
          } else {
            for (; !stk.empty(); stk.pop());
          }
        }
      }
    }
    int res = dyn[n] = 0;
    for (int i = n - 1; 0 <= i; i--) {
      dyn[i] = max(dyn[i], dyn[i] + dyn[i + dyn[i]]);
      res = max(res, dyn[i]);
    }
    printf("Case #%d\n", t);
    printf("%d\n", res);
  }
  return 0;
}

100: 주식거래

매일의 주가가 주어질 때, 최적보다 나쁘지 않은 거래를 하면서 사고팔 수 있는 최대 횟수를 구해야 한다.

첫 문제보다 쉬웠다. 더 이상 싸지지 않을때까지 기다렸다가 사고, 더 이상 비싸지지 않을때까지 기다렸다 팔면 문제의 모든 조건을 만족한다.

#include <stdio.h>

const int N = 200000 + 10;

int tc;

int num[N];

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &num[i]);
    }
    int c = 0;
    for (int i = 0; ; ) {
      if (i == n) {
        break;
      }
      for (; i + 1 < n && num[i + 1] <= num[i]; i++);
      c++, i++;
      if (i == n) {
        break;
      }
      for (; i + 1 < n && num[i + 1] >= num[i]; i++);
      c++, i++;
    }
    int res = c ^ (c & 1);
    printf("Case #%d\n", t);
    printf("%d\n", res);
  }
  return 0;
}

150: 전광판

격자에 배치되어 있는 전구가 각각 행과 열의 스위치와 연결되어 있을 때, 모든 전구를 켤 수 있는 스위치의 조합을 묻는 문제이다.

모든 전구가 정확히 두 개의 스위치에 연결되어 있고, 모든 전구를 켤 수 있는 스위치의 조합을 찾아야 하므로 전형적인 2-SAT 문제로 보인다. 그러나 잘 생각해 보면 2-SAT보다 훨씬 쉬운 경우라는 것을 알 수 있는데, 한 전구에 연결된 두 스위치 모두는 하나의 상태로 다른 하나의 상태를 확정할 수 있기 때문이다. 2-SAT 문제로서 그린 그래프에서 SCC간의 간선이 존재하지 않는 경우이다.

굳이 2-SAT을 해결할 필요 없이 Union-Find 만으로 해결 가능하다. 2-SAT으로도 같은 시간복잡도에 풀리기 때문에 점수에 영향은 없지만, 문제를 좀 더 분석함으로서 구현에 필요한 시간을 크게 절약할 수 있다는 점에서 좋은 문제였다고 생각한다.

#include <stdio.h>
#include <set>

using namespace std;

const int N = 100 + 10;
const int K = 4 * N * N;

int tc;
int n, m, k, l;

int com[K];

int row_node(int i, int j, bool t) {
  int p = 4 * (i * m + j);
  return t ? p : p + 1;
}

int col_node(int j, int i, bool t) {
  int p = 4 * (i * m + j);
  return t ? p + 2 : p + 3;
}

int find(int now) {
  if (com[now] == -1) {
    return now;
  }
  return com[now] = find(com[now]);
}

void link(int s, int t) {
  int su = find(s), tu = find(t);
  if (su != tu) {
    com[tu] = su;
  }
}

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    scanf("%d %d", &n, &m);
    k = 4 * n * m;
    for (int i = 0; i < k; i++) {
      com[i] = -1;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int st, ri, ci;
        scanf("%d %d %d", &st, &ri, &ci);
        if (st == 0) {
          link(row_node(i, ri, false), col_node(j, ci, true));
          link(row_node(i, ri, true), col_node(j, ci, false));
        } else {
          link(row_node(i, ri, false), col_node(j, ci, false));
          link(row_node(i, ri, true), col_node(j, ci, true));
        }
      }
    }
    printf("Case #%d\n", t);
    bool skip = false;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int rtu = find(row_node(i, j, true)), rfu = find(row_node(i, j, false));
        int ctu = find(col_node(j, i, true)), cfu = find(col_node(j, i, false));
        if (rtu == rfu || ctu == cfu) {
          skip = true;
        }
      }
    }
    if (skip) {
      printf("Impossible\n");
      continue;
    }
    set<int> chosen;
    for (int j = 0; j < m; j++) {
      for (int i = 0; i < n; i++) {
        int ctu = find(col_node(j, i, true)), cfu = find(col_node(j, i, false));
        if (chosen.find(ctu) != chosen.end() || chosen.find(cfu) == chosen.end()) {
          chosen.insert(ctu);
        } else {
          printf("C%02d%02d ", j, i);
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        int rtu = find(row_node(i, j, true)), rfu = find(row_node(i, j, false));
        if (chosen.find(rtu) != chosen.end() || chosen.find(rfu) == chosen.end()) {
          chosen.insert(rtu);
        } else {
          printf("R%02d%02d ", i, j);
        }
      }
    }
    printf("\n");
  }
  return 0;
}

200: Monotone

기하 문제이다. 주어진 다각형이 모든 직선이 해당 다각형을 한 번만 만나는 기울기를 갖는가를 묻고 있다.

점수에 비해 풀이는 어렵지 않다. 주어진 다각형의 모든 꼭짓점이 볼록하다면 모든 기울기의 직선이 주어진 조건을 만족하며, 오목한 꼭짓점은 두 선분의 기울기가 이루는 범위를 주어진 조건을 만족하지 못 하게 만든다. 따라서 모든 오목한 꼭짓점을 이루는 두 선분의 기울기의 범위를 구간에서 지워나가면 된다.

다만 많은 기하 문제들이 그러하듯이 실수 오차때문에 골머리를 앓았다. “실수 오차 이상의 기울기 범위가 존재한다”는 조건을 간과한 상태로 여러 차례 시도해 틀렸고 결국 범위를 지워나가는 범위를 넓혀 잡음으로서 해결 할 수 있었다.

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

const int N = 50000 + 10;
const double P = M_PI;
const double E = 1e-14;

int tc;

pair<long long, long long> pt[N];

bool mark[N];

bool right(int p, int q, int r) {
  long long s = 0;
  s += pt[p].first * pt[q].second + pt[q].first * pt[r].second + pt[r].first * pt[p].second;
  s -= pt[p].second * pt[q].first + pt[q].second * pt[r].first + pt[r].second * pt[p].first;
  return s < 0;
}

int main() {
  scanf("%d", &tc);
  for (int t = 1; t <= tc; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      scanf("%lld %lld", &pt[i].first, &pt[i].second);
    }
    priority_queue<pair<double, double>, vector<pair<double, double> >, greater<pair<double, double> > > que;
    for (int i = 0; i < n; i++) {
      int j = (i + 1) % n, k = (i + 2) % n;
      mark[j] = right(i, j, k);
    }
    for (int i = 0; i < n; i++) {
      int j = (i + 1) % n, k = (i + 2) % n;
      if (mark[j]) {
        double sa = atan2(pt[k].second - pt[j].second, pt[k].first - pt[j].first);
        double ta = atan2(pt[j].second - pt[i].second, pt[j].first - pt[i].first);
        ta += E;
        while (ta < 0.0) {
          ta += P;
        }
        while (P < ta) {
          ta -= P;
        }
        sa -= E;
        while (sa < 0.0) {
          sa += P;
        }
        while (P < sa) {
          sa -= P;
        }
        if (sa < ta) {
          que.push(make_pair(sa, ta));
        } else {
          que.push(make_pair(sa, P + E));
          que.push(make_pair(-E, ta));
        }
      }
    }
    double r = 0.0;
    for (; !que.empty(); que.pop()) {
      if (r < que.top().first) {
        break;
      } else {
        r = max(r, que.top().second);
      }
    }
    printf("Case #%d\n", t);
    if (!que.empty() || r < P) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }
  return 0;
}

250: Covernent

개의 단말 노드를 가진 트리가 주어지고, 이 중에서 조건을 만족하는 개의 노드를 적절히 골라 해당 노드들이 이루는 부분트리의 간선의 가중치의 합을 최대화해야 한다.

문제 조건이 전형적인 Mincost-Maxflow 스타일이었지만 이를 그래프로 나타낼 적절한 방법을 찾지 못했다. 대회가 끝난 후 주어진 트리를 그대로 이용할 수 있다는 이야기를 들었지만 아직 명확한 풀이가 떠오르지 않는다.