팀 연습 시작!
2021년 6월 이후에 열릴 ICPC World Final 2021에서 좋은 성과를 얻기 위해, 오늘부터 PS 연습을 하기로 팀원과 약속하였다.
사실 우리 팀이 나가는 대회가 WF 2020인지 WF 2021인지 헷갈린다. WF 2020은 2021년 6월 19일 ~ 24일에 개최된다고 하니, 남은 이 긴 기간동안 팀 연습을 확실하게 많이 하면 좋겠다. (그런데, 군대는 언제 가지..?)
오늘은 총 다섯 문제로 이루어진 problemset을 풀었다. 목표 시간은 3시간.
Morse Code
모스 부호가 입력으로 주어지면, 각 부호를 알파벳으로 치환하는 문제.
길이 26의 string array를 열심히 타이핑한 후, 5분만에 맞았다.
Computational Geometry
정수 $N$가 주어지면, 꼭짓점의 개수가 $N$고 넓이가 $N$인 단순직교다각형을 출력하는 문제.
자명하게, $N$은 4 이상의 짝수여야 한다. 우상단으로 지그재그 올라가는 계단 형태의 다각형을 생각하면, 4이상의 짝수 $N$에 대하여 항상 답이 존재함을 알 수 있다.
이 접근까지는 쉽게 왔는데, 꼭짓점의 좌표를 구하는 과정에서 조금 막혔다. 평소 코딩 연습을 안 한 잘못이라고 생각한다. 대충 짜고 제출하니 맞았다. 30분 AC.
세빈이의 코드를 읽었는데, 아주 간결했다. 쉬운 문제에서는 세빈이의 코딩 스타일을 따라하기로 다짐했다.
Computational Biology
길이 $N$의 문자열 $S$가 주어지면, $S$의 Cyclic fragment이면서 길이가 $K$인 문자열의 Cyclic occurrence의 최댓값을 구하는 문제.
세 시간 안에 풀지는 못했다. Cyclic 조건을 모두 무시하면, 문자열 $S$에 대하여 Sliding을 시도하면서, 모든 길이 $K$의 부분문자열의 Hash를 계산하면 쉽게 풀 수 있다. 이 접근을 Cyclic 조건이 있는 문제에 적용을 하자니, 어떤 부분문자열이 $S$의 Cyclic fragment인지 효율적으로 판별하는 방법을 알아내야 하는데, 찾지 못했다. Cyclic fragment 조건을 naive하게 확인하면 $O(NK)$가 된다고 생각하였고, Suffix array 등의 아이디어를 고민하다가 포기하였다.
치킨을 먹고 업솔빙을 하면서 다시 풀어보니, Cyclic fragment 조건을 naive하게 확인해도 $O(N \lg N)$라는 사실을 깨달았다. 단지, 한 번 계산한 문자열은 다시 계산하지 않는다는 아이디어를 적용하면 된다.
$O(N^2)$번의 문자열 비교를 해야 하기 때문에, $10^9$-scale의 소수 두 개를 이용하여 hash를 구현하였다. 시간 복잡도는 $O(N \lg N)$이며, unordered map/set을 사용하면 $O(N)$이다.
“한 번 계산한 문자열은 다시 계산하지 않는다” 아이디어와, 문제 조건에서 “A cyclic fragment is a word such that ALL its cyclic rotations are subwords”을 올바르게 구현하는데 사소한 실수가 있어서 두 번 틀렸다. 업솔빙을 할 때에도 침착할 필요가 있다.
세빈이의 코드를 읽었고, 풀이는 완벽하게 동일하다고 생각한다. 근데, 소스 코드의 길이가 나의 절반인 점은 정말 놀라웠다.
dotorya는 Suffix array를 이용해서 풀었다. 뭔가 이분 탐색을 열심히 하며, 시간 복잡도는 동일하게 $O(N \lg N)$가 나온다. 풀이 이해는 잘 안 된다. 한 번 생각해보기로 했다.
Cheese, If You Please
Linear Programming 기초 문제.
이론으로만 알고 있는 LP를, 실제 문제로 만나게 되어서 기뻤다.
KAIST 더불어민규당 팀노트의 Dantzig’s simplex algorithm 구현을 가져와서 풀었다. 행렬의 행과 열을 헷갈려서 시간 지체가 조금 있었다. 60분 AC.
우리 팀만의 팀노트를 만들어야 하는데… 언젠가 날 잡고 해야 겠다.
Colorful Doors
일렬로 $N$쌍의 포탈을 배치한 다음, 항상 오른쪽으로 달리는 사람이 왼쪽 끝에서 시작하여 오른쪽 끝으로 빠져나간다. 이 사람이 방문한 모든 지점이 주어질 때, 이러한 방문 조건을 만족하는 포탈 배치를 구하는 문제.
동일한 유형의 문제가 옛날 IOI에 있었기에, 사이클을 가지고 논다는 접근까지는 아주 빠르게 했다.
$2N$개의 지점 각각에 두 개의 in/out 정점을 둔 후, $4N$개의 간선을 어떻게 배치해야 하는가? 라는 문제로 바꾸면 상당히 직관적으로 문제를 풀 수 있다.
먼저, 입력이 전부 ‘1’인 경우, $N$가 짝수면 풀리고 홀수면 답이 존재하지 않는다. 사실, 홀수일 때 답이 없다는 것을 증명하지는 못했는데, 공식 풀이를 보니 대충 되는 것 같다.
모든 Path의 길이의 합이 짝수여야만 답이 존재할 수 있다.
단일 Path는 두 개의 포탈을 이용하여 항상 그 길이를 4씩 줄여나갈 수 있다. 이를 이용하여, 모든 Path의 길이를 3 이하로 만든다.
두 개의 Path는 하나의 포탈을 이용하여, 각각의 길이를 1씩 줄일 수 있다. 따라서, 길이가 가장 긴 두 개의 Path를 잡고, 하나의 포탈을 이용하여 각각의 길이를 줄이는 과정을 계속 반복함으로써 문제를 해결할 수 있고, 이렇게 구현을 했더니 틀렸다.
생각을 좀 해보니, 길이 3인 Path와 길이 1인 Path는 (2, 0)으로 reduct되는데, 이러면 답을 찾을 수 없게 된다. (3, 1)인 case에 대해 예외 처리를 해줬고, 그래도 틀렸다.
더 생각을 해보니, (4, 2)가 있는데, length 4-reduction을 하면, (2, 0)가 되어 답을 찾을 수 없다. length 4-reduction을 길이가 4 이하가 될 때까지만 반복하는 것으로 수정했다.
몇 개의 잔실수가 있었고, 전부 해결하니 맞았다.
공식 풀이를 보니, 나보다 훨씬 간결하게 정해를 작성할 수 있는 것으로 보인다. 매번 느끼지만, 나는 풀이를 여과하는 작업을 안 한다. 이를 매번 생각하면서 연습을 해야겠다.