CERC 2017 를 돌았다. 역시 RC는 구데기….기도 한데 어려웠다. 어려운 문제만 골라서 내긴 했다만, 전체적으로 확실히 어려웠다. 채점은 백준OJ에서 했다. 답은 오피셜 PPT가 있다.

오전 셋

Assignment Algorithm

그냥 구현 문제다. 영문 문제를 정확하게 C++로 번역하면 된다. 예제가 나오면 맞는것.

Gambling Guide

기대값을 최소화하는 문제다. 필시 각 정점의 최소 기대값이 존재하긴 할 것이니, 한 정점에서 티켓을 뽑았을 때 자신보다 기대값이 낮으면 가고, 크면 가지 않을 것이다.

이를 바탕으로 각 정점당 간선 개수, 나보다 기대값이 작은 정점으로 가는 간선 수, 나보다 기대값이 작은 이웃들의 기대값 합을 가지고 있으면 계산할 수 있다. 그러니 다익스트라를 돌려주면 된다.

Can’t Stop Playing

어디선가 봤던 문제. 얘만 CERC 2014다.

DP를 상태를 [현재 위치, 내가 오른쪽에 놓은 것의 합] 으로 정의하면 N^2에 할 수 있다.

오후 셋

Buffalo Barricades

스위핑으로 각 버펄로가 속한 구역을 찾고, 기둥을 다시 뽑아가면서 버펄로를 합해주면 된다. 스위핑할때는 위에서 아래로으로 훑으면서, 각 버펄로에서 오른쪽으로 뻗었을 때 닿는 기둥에게 귀속기켜주면 그 버퍼로가 속한 구역을 알 수 있다. 고 한다. 잘 모르겠다.

Embedding Enumeration

더러운 DP문제다.

N^2 DP로 정점 v를 루트로 하는 서브트리가, 위줄과 아래줄의 범위 차이가 d인 경우에 채우는 가지수를 셀 수 있다.

그리고 경우를 더 나눠서, 높이가 1인 구간에 대해서는 쉽게(..) 계산할 수 있으므로 DP를 O(N)으로 바꿀 수 있다.

고 한다. 잘 모르겠는데 앞으로도 알고싶지 않다.

Intrinsic Interval

분할정복하면 O((N+Q)logN)에 된다. 선분을 확장하는걸 선형에 할 수 있으면 가능하다.

Kitchen Knobs

인접한 원소의 차를 저장하고, 거기서 두 점을 임의로 골라서 mod 7의 합이 보존되는 임의이 두 값을 더해줄 수 있다. 따라서 1-6, 2-5, 3-4끼리 묶고 나머지 3쌍으로 DP를 해주면 된다고 한다.

ICPC는 역시… 싶은 생각이 든다. 딱히 하고싶지 않다는 느낌이 강하게 든다.

나중에는 CF AtCoder CSA같은거만 하면서 취미로 하지 않으려나?

CERC 2017중에서 Justified Jungle이란 문함제가 풀려있다. 신기함