총평
문제들은 다음 링크에서 확인할 수 있다.
https://codeforces.com/contest/1476
전체적으로 A~E는 무난한 문제들이었고, F,G의 경우 매우 어려운 문제 인 것 같다.
나의 경우, A~E 는 문제 없이 풀었고, F 솔브가 없는 것을 보고 바로 G로 왔으나, G도 풀지 못했다.
하지만 다행히 A~E를 준수하게 풀어서, rated 중 23위로 max rating을 경신할 수 있었다.
풀이를 정말 간략하게 남긴다.
A
n과 k가 주어진다. 그럼 양의 정수인 n개의 원소들의 총합이 k의 배수가 되는 것이 가능한지 묻는 문제이다. 적절한 case-work를 하면 된다. O(1)에 각 문제를 해결할 수 있다. 이번 라운드에서 나온 대부분의 핵이 A tl 핵이었던 것 같다.
B
문제를 처음 봤을 때는 생각이 잘 나지 않을 수 있는데, 잘 생각을 해보면 결국 제일 처음 수만 늘려도 손해가 없다는 것을 알 수 있다. 이분 탐색을 돌려주면 된다. 사람들이 처음에 B에서 많이 막혔던 것 같다.
C
특수한 형태의 그래프가 주어질 때, 단순 사이클의 최대 길이를 구하는 문제, dp를 잘 하면 된다. 지금 보고 있는 구간에서 사이클을 이어 나갈지, 여기에서 끝낼지를 보면 된다. 단, 어떤 구간에 대해 끝점이 같다면 예외처리를 해주어야 한다. 그렇게 하지 않으면 단순 사이클이 아닐 수 있다.
D
잘 생각해보면 어떤 도시에서 왼쪽, 오른쪽 도로의 방향이 처음과 같다면 한쪽으로만 갈 수 있다. 또, 한번 이동할 때마다 도로의 방향이 뒤집어지기 때문에, 한번 갔던 정점은 다시 방문이 가능하다. 이런 점을 생각하면, 각 도시에 대해 왼쪽으로 최대한 갔을 때 방문 가능한 도시 수, 오른쪽으로 최대한 갔을 때 방문 가능한 도시 수, 그리고 자기 자신을 합한 것이 답이 됨을 알 수 있다. 왼쪽, 오른쪽으로 최대한 갔을 때 방문 가능한 도시 수는 dp를 통해 구할 수 있다.
E
n개의 패턴, m개의 문자열이 주어진다. 패턴과 문자열의 길이는 k로 고정이다. 이때, 문자열들에 대해서 해당 문자열과 매칭이 가능한 패턴들에 대해 특정 패턴이 제일 먼저 나올 수 있게 순서를 조정할 수 있는지를 묻는 문제이다. 제한을 보지 않는 다면 문제를 푸는데 어려움을 겪을 수 있다. 하지만 제한에 k가 4이하로 주어진다고 돼있으므로, 여기서 실마리를 얻을 수 있다. 한 문자열에 대해 매칭 가능한 패턴의 수는 2^k이므로, 그냥 문자열들에 대해서 매칭 가능한 패턴을 전부 보면 된다. 이때, 그런 패턴이 없으면 NO를 출력한다. 만약에 모두 존재는 한다면, 문자열에 대해 매칭 가능한 패턴들의 순서를 정할 수 있다. 이를 바탕으로 그래프를 구성해준 다음, 위상정렬 했을 때 위상정렬이 제대로 된다면 YES, 실패한다면 NO이다.