ICPC Seoul Regional 2023 미러

근황

올해 하반기에는 많은 일이 있었습니다.

• 8월에 석사학위를 취득했습니다. 제 석사논문을 모종의 이유로 arxiv에 올라왔으니 관심 있으신 분은 찾아보시길...
• 박사는 가지 않을 것 같습니다. 길게 쓰진 않겠지만, 가장 큰 이유로는 아카데미아 연구가 저랑 잘 안 맞는 것 같다는 점이 있었습니다.
• 같은 달에 퓨리오사AI에 취업해서 석사전문연 병역의무를 수행하고 있습니다.
• 비슷한 시기에 개인적인 이유로 스트레스를 받았습니다. 외부 요인이 있긴 했으나, 뭔가 "내가 PS 커뮤니티에 악영향을 주고 있는 것 같다"같은 두려움이 생겨서 solvedac 디코 스탭도 그만두고, 단계별로 풀어보기도 그만두고, 검수하던 서버도 다 나가고 solvedac 서버 자체도 나갔다 들어오기를 계속 반복했습니다. 이것도 길게 쓰진 않겠습니다.
• 뜬금없는 버튜버 얘기입니다만, 나나시 무메이가 오시(최애)가 된 지 1년 좀 넘었는데 10월에는 진심 오시가 되었음을 깨달았습니다. 그리고 이때쯤에 무메이의 신곡 mumei가 출시됐습니다. 갓곡입니다 꼭 들어주세요
• 이번주에 solvedac 마스터를 찍었습니다. 2022년 8월에 루비1이 된 지 15개월 만의 일입니다. topology님 블로그, LGV 보조정리, 그리고 보로노이 다이어그램에게 큰 감사를 보냅니다.
• 어제 결국 슈퍼챗을 보내고 말았습니다. 아니 물론 디코 프사부터 그거긴 하지만 그냥 있으면 좋은 정도로 생각해서 공식 굿즈도 산 적이 없는데... 저도 제가 이렇게 될 줄 몰랐습니다... 아이돌에게 빠진다는 게 이런 느낌인가 봐요......
• 다행히도 위 두 항목 덕분에 개인적인 스트레스 문제는 해결됐습니다.

미러 대회

작년의 ICPC Seoul Regional 2022 미러에 이어서 올해에도 ICPC 서울 미러에 참가했습니다. 이번에는 dohoon님과 cozyyg님과 팀을 맺었습니다. 온라인 미러니까 3인3컴을 쓰기로 했습니다.

시작

제가 맨 터음에 3k+2번째 문제들을 보기로 했습니다. C를 봤지만 아주 어려운 문제일 것 같다는 감이 들어서 패스했습니다.

F를 봤습니다. 아래 그림처럼 y = x 직선 위에 c를 잡아서 가능한 한 많은 점을 덮는 문제로 볼 수 있습니다. 그러면 대충 O(N^2K) dp가 나오는데, 일단 식을 세우기도 쉽지 않을 것 같아서 일단 넘어갔습니다.

I와 L을 봤습니다. 둘 다 뭔가 할만해 보이지만 바로 떠오르는 건 없었습니다.

20분 I solve (jh)

CFIL을 다 읽고 한 10분쯤에 스코어보드를 봤더니 I가 풀려있었습니다.

• 우선 마지막 도시에는 최대 허용치 만큼을 다 보내야 합니다. 많이 보낸다고 손해를 볼 일이 없기 때문입니다. 하지만 중간 도시에 최대 허용치 만큼을 보내면 다음 도시에도 많이 보내야 하고, 그러면 다음 supply process에서 보낼 수 있는 양이 줄어서 손해를 볼 수도 있습니다.
• 그래서 마지막 도시를 본 다음에는 뒤에서 두 번째 도시를 봐야 될 것 같습니다. 이미 마지막 도시를 해결했기 때문에, 여기에는 보낼 수 있는 가능한 한 많은 양, 즉 min(현재 도시의 최대 허용치, 마지막 도시에 보낸 양)을 보내면 됩니다. 이렇게 보내고도 최소 요건이 만족되지 않았다면, 바로 다음 supply process에서는 이 도시가 "마지막 도시"이기 때문에 가능한 한 많이 보내면 됩니다.
• 이걸 계속 반복해서 첫 번째 도시까지 처리하고, (최소 요건이 만족되지 않은 횟수) + 1을 출력하면 됩니다.

대략적인 풀이를 12분에 알아내고, 짜는 동안 풀이를 구체화하면서 20분에 맞았습니다.

23분 D solve (co)

14분에 dohoon님이 big int를 써야 할 것 같다고 하셔서 cozyyg님이 짜러 가셨습니다.

22분에 dohoon님이 J를 짜기로 했고, 23분에 cozyyg님의 D가 정답을 받았습니다.

47분 G solve (jh)

F와 L을 다시 봤으나 그럴싸한 진전은 없었고, 31분에 스코어보드를 보니 G와 H가 풀려있었습니다. H를 봤으나 처음 든 생각은 "이게 지금 풀 수 있는 문제라고?"였습니다.

G는 보자마자 각 수가 어떤 카드들에 들어있는지 기록하고, 이를 map에 담아서 친구의 질문과 매칭되는 수를 찾으면 될 것 같아서 짜기로 했습니다. 이걸 그냥 기록해도 key의 크기 합이 NK라서 잘 되는데, NM으로 생각했던 건지 해싱을 써야 될 것 같았습니다. 각 카드마다 랜덤 64비트 해시 값을 만들고, 카드의 집합을 해시 값의 xor로 표현하면 됩니다. 하지만 맞았으니 상관없습니다.

다시 H로 돌아와서 여러 가지 메모를 하기 시작했습니다.

64분 B solve (co)

28분쯤에 B 관련 메모를 하셨던 cozyyg님이 37분에 풀이를 완성하셨고, 64분에 맞으셨습니다.

74분 H solve (jh)

• "가능한 모든 순열에 대해 (가능한 모든 부분 수열에 대해 무슨 값의 최댓값)의 최댓값"을 구해야 되는데, 사실 최댓값을 한 겹 벗길 수 있습니다. 모든 순열에 대해 저걸 따로 구한다고 생각하지 말고, 모든 (순열, 부분 수열) 조합에 대해 저 값을 최대화하면 됩니다.
• 그러면 문제를 다음과 같이 변형할 수 있습니다. "열을 잘 섞은 다음, 각 행에 대해 증가 부분 수열을 잘 선택해서 원소 합을 최대화하세요."
• 열을 아무렇게나 섞을 수 있으니, 열이 그냥 낭비되는 일은 피할 수 있을 것 같이 생겼습니다. 구체적으로, '모든 열에 대해 두 수 중 하나는 꼭 선택되어야 한다'라는 조건을 넣어도 최적해가 달라지지 않습니다. 그렇지 않은 최적해가 있다면, 낭비된 열을 하나 골라 중간에 잘 끼워넣을 수 있기 때문입니다.
• 그뿐만이 아니라, '한 열의 두 수 중 하나만 선택한다면, 꼭 더 큰 수를 선택해야 한다'라는 조건도 넣을 수 있습니다. 이유는 위와 같습니다.
• 그래서 문제를 또 다음과 같이 변형할 수 있습니다. "x에 대해 정렬된 (x, y) 순서쌍이 있습니다. 순서쌍을 제외하는 데에는 각자 페널티가 있습니다. 순서쌍을 잘 제외해서 나머지가 y에 대해서도 정렬되도록 하고, 이때 페널티를 최소화하세요."
• 사실 이 변형 문제에서 x가 하는 일이 없기 때문에, 다시 변형합시다. "수열이 있습니다. 수를 제외하는 데에는 각자 페널티가 있습니다. 수를 잘 제외해서 나머지가 증가수열이 되도록 하고, 이때 페널티를 최소화하세요."
• O(N^2) DP로 풀 수 있습니다.

를 58분쯤에 완성하고 짜기 시작했습니다. 최초 코드는 금방 나왔으나, 시간 제한이 0.5초 밖에 안 돼서 연산량을 반으로 줄이려고 했는데 뭔가 꼬여서 되돌렸습니다. 다행히 최초 풀이 그대로 통과했습니다.

K를 아무도 안 풀었으나, 일단 풀만한 문제인지 알아야 될 것 같아서 읽어봤습니다. cozyyg님이랑 "t에 있는 연속된 같은 문자들은 합칠 수 있다", "각 시작 위치에 대해 valid substring의 끝 위치는 [r, INF] 꼴이고 r은 증가", "KMP 비슷하게 될 것 같다" 정도의 얘기를 하다가 스코어보드를 보니 E와 F가 풀려 있었습니다.

E는 2년 전의 Stock Price Prediction과 유사한 문제입니다. 문제가 있다면 제가 저 문제를 안 풀었다는 것이었습니다. 그 문제의 풀이를 알고 있긴 했으나, F부터 보기로 했습니다.

이쯤에 dohoon님이 J를 디버깅하고 있다는 보고를 하셨고, cozyyg님이 같이 디버깅하러 가셨습니다.

171분 J AC (do+co)

수고하셨습니다 👏

172분 F AC (jh)

비용 함수를 잘못 생각했습니다.

이때 L이 풀려있길래 잠깐 봤으나, 진전이 없어서 다시 F로 갔습니다.

그래서 풀이를 정리하면 - 점의 x좌표 또는 y좌표만 c 값으로 사용하면 됩니다. 이런 값은 최대 2N개 있습니다. - c를 오름차순으로 사용한다고 합시다. - DP[i][j] = i개의 c를 사용했고, 마지막으로 쓴 c가 모든 c 값 중 j번째 값일 때, 덮을 수 있는 최대 점 개수 - 이제 DnC optimization을 사용하면 O(NKlogN)에 풀립니다.

비용 함수를 계산하는 건 간단하지 않았습니다. 2차원 구간합을 구하기는 좀 번거로워 보이는데, 그렇지 않으면 2만 x 2만 배열을 만들어야 합니다. 후자가 정해일 것으로 믿고 메모리 계산을 해봤는데 다행히도 2기가 제한 안에 들어갔습니다.

나머지는 순조롭게 진행됐고 172분에 AC를 받았습니다. 한 번 틀리고 봤더니, i > j일 때 C[i][j]를 0으로 뒀는데 그로 인해 답이 N보다도 커지는 경우가 발생했습니다. C[i][j]를 -무한으로 바꿔서 맞았습니다.

1시 좀 넘었으므로 밥을 먹으면서 E를 생각하러 갔습니다. 그러는 동안 dohoon님의 C 풀이를 들으려고 했으나, 잘 이해가 안 되어서 그냥 dohoon님이 직접 짜시기로 했습니다. cozyyg님이 K를 잡으러 가셨지만, 결국 풀이 완성은 못 하셨습니다.

E는 아무래도 Stock Price Prediction에 아호-코라식을 섞으면 될 것 같았습니다. Stock Price Prediction을 풀어본 적이 없다고 했는데, 심지어 아호-코라식도 안 써본 지 3년이 넘었습니다. 하지만 E 외에는 잡을 문제가 딱히 없었고 구현을 시도했으나, 매칭 과정을 잘못 생각한 건지 예제도 나오지 않았습니다. 시도는 했다는 의미로 1WA 제출을 넣었고, dohoon님도 C가 잘 안 되어서 마찬가지로 1WA 제출을 넣으셨습니다.

끝~~

후기

제가 풀었던 FGHI 중에는 H가 가장 마음에 들었습니다.