코드포스 #335 div. 1

3개월만에 코드포스를 쳤다. 시험기간이라 요 며칠 사이에 백준에서 쉬운 문제들 몇 개 깔짝대고 있었는데, 마침 코드포스가 아침 8시라 시간이 괜찮아서 오랜만에 쳤다. 원래는 잠을 좀 자고 7시쯤 일어나서 씻고 칠 예정이었는데 3시간 반 넘게 누워 있었는데 잠에 들지 못해서 그냥 일어나서 문제 풀면서 손을 풀면서 아침을 맞았다. 잠을 못 잔 덕분에 대회 때 잠기운이 약간 있긴 했지만 다행히 크게 방해되지는 않았다.

대회 시작 즈음에는 ABC 풀면 레드 갈 줄 알았는데, 예상한대로 풀었지만 여기저기 실수하는 바람에 감점을 받아 레이팅 변화는 거의 없을 것 같다. 이번에도 그냥저냥 실력만큼 본 것 같은데, 예전에 실력대로만 보면 되는 시험들에서 망한 경험이 너무 많아서 이런 사소한 사실에도 만족감을 느끼고 있다. 최종 순위는 127위.

A

문제를 대충 읽다가 틀렸다. 기차를 뽑아서 맨 앞이나 맨 뒤에만 넣을 수 있는데, 뽑아서 아무데나 넣을 수 있을 때 최소 정렬횟수를 구하는 게 잘 알려진 문제라 왜 이런 유명한 걸 냈냐고 투덜대면서 풀었다가 Hack 당했다. 저렇게 짜도 pretest 통과하게 해 놓은데서 출제진의 악랄함을 느낄 수 있다. 내가 착각한 문제와 풀이가 크게 다르지 않고, 번호가 연속하는 LIS 중 가장 긴 것을 찾으면 된다.

#include <cstdio>

const int MAX = 100020;

int n, len[MAX];

int main() {
    scanf("%d", &n);

    int maxLen = 1;
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        if (len[t-1] != 0) {
            len[t] = len[t-1]+1;
            if (maxLen < len[t])
                maxLen = len[t];
        }  else len[t] = 1;
    }

    printf("%d\n", n - maxLen);

    return 0;
}

B

ABC 중 가장 마음에 드는 문제였다. 트리의 간선 길이와 그 간선이 최소신장트리에 포함되는지 여부가 주어지면 그래프를 알아서 잘 구성하면 되는 문제다. 크루스칼 알고리즘으로 MST를 찾을 때, 간선을 길이 순으로 정렬했을 때 특정 간선이 포함되지 않는 경우는 이전의 간선들과 사이클을 이룰 때라는 사실을 적절히 이용하면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 100020;

struct Edge {
    int id, len;
    bool used;

    Edge() {}
    Edge(int id, int len, bool used) : id(id), len(len), used(used) {}
};

bool compareLen(const Edge &f, const Edge &s) {
    if (f.len == s.len) return f.used > s.used;
    return f.len < s.len;
}

int n, m;
Edge edge[MAX];

void input() {
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++) {
        int len, used;
        scanf("%d%d", &len, &used);
        edge[i] = Edge(i, len, used);
    }

    sort(edge, edge+m, compareLen);
}

int from[MAX], to[MAX];

bool solve() {
    int last = 1, now = 3, remain = 1;
    for (int i = 0; i < m; i++) {
        Edge &cur = edge[i];
        if (cur.used) {
            from[cur.id] = last;
            to[cur.id] = last+1;
            last++;
        } else {
            if (last < now) return 0;
            from[cur.id] = now;
            to[cur.id] = remain;
            remain--;
            if (remain == 0) {
                now++;
                remain = now-2;
            }
        }
    }
    return 1;
}

void print() {
    for (int i = 0; i < m; i++)
        printf("%d %d\n", from[i], to[i]);
}

int main() {
    input();

    if (solve()) print();
    else puts("-1");

    return 0;
}

C

2015 구글 코드잼 R2 B Kiddie Pool과 굉장히 유사한 문제였다. 코드잼 칠 때는 시간 내에 풀이를 못 떠올렸는데 이번 라운드에서는 풀이 찾는건 금방 성공했다. 하지만 코딩에서 잔실수를 너무 많이 해서 3번이나 WA를 받고 통과할 수 있었다. 말도 안 되는 코드를 짜서 냈는데 pretest에서 걸려서 다행이었다.

문제는 전혀 기하처럼 생기지 않았지만 2차원 벡터로 생각해서 컨벡스헐을 구한 뒤 교차점을 통해 값을 계산하는 문제다. 선분 교차지점 구하는 코드는 안 졸렸으면 금방 유도했을텐데 졸려서 계산하기 싫은 마음에 그냥 StackOverflow에서 가져다 붙였다.

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair < ll, ll > pll;

#define x first
#define y second

const int MAX = 100020;

int n, targetExp, targetMoney;
pll target, point[MAX];

void input() {
    scanf("%d%d%d", &n, &targetExp, &targetMoney);
    target = pll(targetExp, targetMoney);

    for (int i = 0; i < n; i++) {
        int exp, money;
        scanf("%d%d", &exp, &money);
        point[i] = pll(exp, money);
    }
}

ll ccw(pll a, pll b, pll c) {
    return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}

pll origin = pll(0, 0);
bool compare(const pll &f, const pll &s) {
    return ccw(origin, f, s) > 0;
}

pll stack[MAX];
int top;

void solve() {
    sort(point, point + n, compare);

    stack[top++] = point[0];
    for (int i = 1; i < n; i++) {
        if (top && ccw(origin, stack[top-1], point[i]) == 0) {
            if (stack[top-1].x <= point[i].x) {
                top--;
                while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
                stack[top++] = point[i];
            }
        } else {
            while (top >= 2 && ccw(stack[top-2], stack[top-1], point[i]) <= 0) top--;
            stack[top++] = point[i];
        }
    }

    int start = 0, end = top-1;
    while (start != top-1 && stack[start].x <= stack[start+1].x) start++;
    while (end != start && stack[end].y <= stack[end-1].y) end--;

    if (start == end || ccw(origin, stack[start], target) <= 0 || ccw(origin, stack[end], target) >= 0) {
        printf("%.10lf\n", max((double)target.y / stack[end].y, (double)target.x / stack[start].x));
    } else {
        for (int i = start; i < end; i++) {
            double p0_x = 0, p0_y = 0, p1_x = target.x, p1_y = target.y,
                p2_x = stack[i].x, p2_y = stack[i].y, p3_x = stack[i+1].x, p3_y = stack[i+1].y;

            double s1_x, s1_y, s2_x, s2_y;
            s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
            s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

            double s, t;
            s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
            t = (s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

            if (s >= 0 && s <= 1) {
                printf("%.10lf\n", target.x / (p0_x + (t * s1_x)));
                break;
            }
        }
    }
}

int main() {
    input();

    solve();

    return 0;
}