Educational Codeforces Round 103 (Rated for Div. 2) 후기

Educational Codeforces Round 103 (Rated for Div. 2)

---

A. K-divisible sum

\(n\ge k\)일 때는 \(1\) 또는 \(2\)만으로 \(k\)로 나누어 떨어지는 합을 만들 수 있다.
\(n<k\)일 때는 원소의 합이 \(k\)가 되야하므로 최댓값은 \(\lceil \frac{k}{n} \rceil\)가 된다.

 

B. Inflation

일단 더할거면 전부 \(p_0\)에 더한다고 생각하면 된다.
지금까지의 총합이 \(S\)라고 했을 때, \(\frac{p_i}{S+t}\le k\%\)를 만족시키는 \(t\)를 구해야 하고, 식을 정리해보면 \(t\ge \frac{p_i}{k\%}-S\)가 된다.
그래서 \(p_i\)를 순서대로 확인해보면서 \(\text{max}(0,\lceil \frac{p_i}{k\%}\rceil -S)\)만큼 더해가면 된다.

 

C. Longest Simple Cycle

항상 \(1\)번 점과 \(c_i\)번 점에서 앞 체인과 연결된다는 점 덕분에 편해진다. 그리고 \(a_i\)와 \(b_i\)가 다르면, 둘의 대소관계는 사이클의 길이와 전혀 상관이 없다.
신경써야되는 부분은 \(a_i=b_i\)인 경우이다. 이 경우에는 앞쪽 체인으로는 더 이상 사이클을 이을 수 없다.
그렇지 않다면, 앞쪽 체인으로 더 잇는 경우와 이번 체인에서 사이클을 만드는 경우(\(a_i\)부터 \(b_i\) 사이를 사이클에 포함시키는 경우)로 나누어 큰 쪽을 고르면 된다.

 

D. Journey

\(i\)번 마을에서 \(j\)번 마을까지 갈 수 있다면, \(j\)번 마을에서 \(i\)번 마을까지 돌아올 수 있다. (이동방향과 도로방향이 모두 반대가 되기 때문)
그러면 한 번의 여행에서 방문할 수 있는 마을의 수는 그냥 갈 수 있는 마을의 수와 같다.
그리고 어떤 마을까지 도착하려면 그 사이의 도로가 \(LRLR\cdots\) 형식으로 번갈아가면서 나와야되므로 이런 형식인 길이를 양쪽에 prefix sum으로 구해두면 각 마을별로 도달할 수 있는 마을의 수를 알 수 있다.

 

E. Pattern Matching

일단 패턴과 문자열을 짝지은 뒤에, 패턴을 재배열하고 순서대로 각 문자열과 매칭시켜보는데 가장 처음 매칭된 패턴이 짝지었던 패턴이 되도록 하라는 문제이다.
제한때문에 패턴과 문자열의 매칭 여부를 다 비교할 수는 없지만 길이가 매우 짧으므로 어떤 문자열과 매칭되는 패턴이 있는지는 쉽게 찾을 수 있다. 또한 그렇게 매칭되는 패턴의 수도 꽤 작다는 점을 아는 것이 중요하다.

이렇게 매칭되는 패턴들(짝지었던 패턴 제외)은 항상 짝지었던 패턴 뒤에 나와야한다.
이를 그래프에서 간선을 추가한다고 생각해보면, 그래프에 사이클이 없는 경우만 가능한 경우이다. 그리고 순서 역시 그래프를 탐색하면서 정할 수 있다.

 

---

E번이 내가 생각한 난이도보다는 많이 안 풀린것 같다. 또 F는 대회 중에는 풀리지도 않았고, G도 꽤 어려운 것 같아서 내 등수가 많이 올라간 것 같다.

그리고 요즘 코포에서 레이팅이 2100 이상인데 Div. 2가 반영되거나 2100 미만인데 Div. 2가 반영이 안 되거나 하는 오류가 자꾸 생긴다... 저번에 버그로 182점이 떨어져서 다시 올리는 중이다.