2023 ICPC Seoul Regional 본선 후기

안녕하세요. 리유나입니다.

11월 24일부터 25일까지 2023 ACM-ICPC 한국 리저널 겸 제 23회 전국 대학생 프로그래밍 경시대회를 치르고 왔습니다!

작년과 마찬가지로 MunSongSong Eggdrop(문송송 계란탁)으로 참여했고, 교내 2등, 전체 4등(외침 제외시 3등)으로 마무리했습니다. 아쉬운 점도 없지는 않지만 유종의 미를 거둔 것 같아 기쁩니다!

스코어보드 중계방송 기준 최종 스코어보드는 다음과 같습니다.

(혹시 대회 TMI는 됐고 문제 풀이만 궁금하신 분이 계신다면 스크롤을 7. 문제별 풀이 정리까지 내려주시면 됩니다! ㅎㅎ)

 

아래는 대회 이전부터 끝나고 난 뒤까지의 타임라인입니다.

0. 팀 구성

작년에 이야기한대로 문송송 그대로 가는 것으로 확정했습니다. 중간에 한번 SongC가 팀을 옮기는 제안을 받아서 잠깐 고민이 있긴 했지만, 봄 즈음에 결국 이 팀 그대로 가는 것으로 확정이 됐습니다. 이번에야말로 월파를 노리자고 다들 다짐했습니다.

 

작년부터 이어온 팀이라 그런지 좋은 점으로는, 팀워크가 꽤나 잘 맞고 서로가 서로의 성향을 잘 파악하고 있는 점이었습니다. 팀연습을 그렇게 많이 한 편은 아니지만 할 때마다 그런 점이 꽤나 느껴져서 발전을 많이 하고 있구나. 이번에는 좀 더 좋아지겠구나. 하는 생각을 솔직히 했던 것이 사실입니다 ㅋㅋ

 

팀원들을 소개하자면 다음과 같습니다.

 

mhy908: 문송송의 문. 구현량이 많고 복잡한 문제나 기하 문제 등에 큰 강점을 가지고 있고, 다른 분야들 실력도 물론 출중합니다.

SongC: 문송송의 송. 전반적으로 다 잘하며, 이상한 자료구조나 특이한 아이디어,(그들만의)웰노운 같은 것들을 잘 알고 있습니다. 여러 방면으로 경험이 많아서 어떤 문제를 봐도 대강 방향을 잡을 수 있는 능력을 가졌습니다.

Eunha: 문송송의 송. 이자 접니다. 수학, 특히 조합론이나 확률론쪽 문제에 강한 편입니다. 정수론 기하도 밀 수는 있지만 기하는 mhy에 비해 구현력이 모자랍니다. 두뇌 피지컬이 괜찮은 편이라 constructive 문제나 여타 성질 파악이 필요한 문제에서 중요한 관찰을 할 수 있습니다. 다만 전반적인 PS 능력은 나머지 둘에 비해서 밀리는 편입니다. 게다가 이 사람, 주 사용 언어가 Python입니다.

그 외의 특징이라면 학교를 아주 오래 다녀서(?)팀 대회 경력은 나머지 둘에 비해 많은 편이라 키보드 시간 분배, 문제 분배, 멘탈 관리 등을 맡았습니다.

 

잘만 조합하면 황밸이 될만한 팀원이고, 실제로 많은 팀연습을 거쳐가면서 각자의 장단점을 서로가 적절히 파악하고 전략적으로 문제풀이를 진행할 수 있었습니다.

 

1. 팀 연습

이번에는 팀연습을 boj보다는 codeforces 위주로 했는데, boj에 문제가 올라와 있지 않은 정말 신박하고 이상한 리저널들을 풀 수 있었기 때문이 컸습니다.(사실 boj에 올라온 정도면 팀원 중 누군가는 꼭 한문제씩은 풀었기도 하더라고요.) 그 절정에 있었던 게 광저우 리저널이었는데, 모두가 멘붕하고 경악을 금치 못했던, 도대체 중국엔 어떤 사람들이 살고 있냐 같은 이야기가 절로 나오던 셋이었습니다()

 

작년 이맘 때 올린 후기글을 보면 당시 팀의 단점으로는 이런 것들이 지적되고 있었는데, 어떻게 개선되었는지를 보면 다음과 같습니다.

 

-다들 풀이는 바로바로 나오는데, 문제를 짜다가 안될 때 계속 붙잡고 있는 경우가 허다하다.

->누군가가 말린다 싶으면 다른 사람이 바로 키보드를 뺏고, 아예 머리 식히게 다른 문제를 풀게 시키는 등의 시스템(?)이 팀 내에 갖추어졌습니다. 또한, 빠른 의사소통을 위해서 대회 중에는 반말을 사용하는 것으로 정했습니다.

 

-한 문제에서 멘탈이 말리기 시작하면 바로 스노우볼이 굴러간다.

->누가 그런다 싶으면 바로 프린트하고 키보드에서 손 떼게 시켰습니다. 또한 키보드를 잡을 때 '짜는 데 몇분이 걸린다'라는 선언을 하고 잡게 하고, 그 시간을 너무 지난다 싶으면 쫓아내는 등 여러 팀 내의 룰을 만들었고, 상당히 효과적이었다고 생각합니다.

 

-서로 사용하는 환경이 너무 다르고, 심지어 한 명(=저)은 주 사용 언어조차 다르다.

->SongC가 억지로라도 이번에는 codeblock을 대회 중에 사용했고, 어차피 저는 모국어는 못 고치지만(?)대신에 C++ 코드를 보면 바로 이해할 수 있을 정도의 독해력은 갖추어 대회 내내 다른 사람들이 짜는 코드를 옆에서 검수하고 잘못 짜고 있지는 않은지 확인하는 역할을 맡을 수 있었습니다.

 

-결론적으로, 팀웍이 망했다.

->결론적으로, 많은 부분에서 개선이 있었습니다.

 

팀연습을 하면서 PS 외적으로도 협력이나 팀워크 등에 대해서 이런저런 것들을 굉장히 많이 배우게 되는 기분이었습니다. 이정도면 나중에 이력서에 한줄 적어도 되지 않나 싶을 정도로요(?)

2. 인터넷 예선

인터넷 예선 스코어보드는 다음과 같았습니다.

가만 보니 지금 순위랑은 정말 완전 다르네요. 이것도 나름 신기합니다 ㅋㅋ

 

예선은 학교에서 치뤘습니다. 작년 예선처럼 초반에 무시무시하게 질주하다가 후반에 조금 말려서 떨어졌지만, 그래도 4등이라는 나쁘지 않은 성적을 거두었습니다. 작년에도 예선 순위랑 본선 순위가 같았는데, 결국 올해도 마찬가지가 되었네요!

3. 본선 전날

고양까지 가는 게 너무 힘들었습니다. NIA 높으신 분들도 후기 찾아보신다고 들었는데, 부탁드립니다. 대전 리저널 해줬으면 좋겠습니다. 아니면 하다못해 세종대라도 괜찮습니다.

 

정말 의외였던 점이라면, 이때 환경 설정 및 연습 세션에서 나오는 작년 문제 중 하나가 당시 1솔브밖에 되지 못했던  Castle Design이 나왔다는 것입니다. 보통은 그 전 해 문제 중 쉬운 편인 세문제가 나왔는데, 실제로 당시 연습 세션에서도 이 문제를 푼 팀은 한 팀뿐이었습니다.

4. 본선 당일

본선 당일 타임라인을 정리해보면, 다음과 같은 식으로 대회가 진행되었습니다.

 

(시작) 약간 헷갈리는데, 아마도 mhy가 앞부분, SongC가 중간, 제가 뒷부분을 봤습니다. 당장 풀 문제는 안 보였고, I는 쉬워보였고 J는 제가 풀 문제 같이 보였습니다.

 

(7분) I 퍼솔이 나오길래 I가 쉽다는 결론을 내고 SongC가 I를 짜기 시작했습니다.

 

(23분 경) mhy가 D를 짜고 SongC가 I를 짜서 차례차례 정답을 받았습니다. 저는 J 풀이를 생각했고 이대로 짜면 퍼솔이다! 하고 생각했지만 틀렸습니다.(1차 멘붕)

 

(37분) J 퍼솔을 뺏겼습니다(ㅠㅠ) mhy는 C를 짜기 시작했지만 제출했더니 틀렸고, 이후 이어지는 칠전팔기의 시작이 되었습니다.

 

(45분) SongC가 G를 풀었습니다.

 

(68분) SongC가 H를 풀었습니다.

 

(??분) 이쯤에서 mhy의 C 맞왜틀, 저의 J 맞왜틀 행진이 계속되었습니다. J는 한자릿수인 경우 예외 케이스 핸들링을 조금 이상하게 했던 걸 깨달아서 고쳤지만, 그럼에도 틀려서 속상했습니다. C는 파도파도 계속 반례가 나오는 끔찍한 문제였습니다.

 

(147분) SongC가 F를 풀었습니다.

 

(??분) B가 생각보다 풀리길래 저랑 mhy가 잠깐 일을 스톱하고 머리 비울 겸 B 코드 해석에 들어갔습니다. B가 Python-like pseudocode였기 때문에 해석은 제가 맡아서 풀이를 냈고, 구현 중에 세그를 써야하기 때문에 이쪽 구현은 mhy에게 맡기기 위해 풀이를 설명했습니다. 또한, 제가 컴퓨터가 빈 틈을 타서 J 검증 코드를 만들었는데 101, 102와 같은 중간에 0이 들어간 숫자들에서 문제가 생기는 것을 확인, 바로 어디를 고칠지 찾았습니다. J를 고치고 B를 짜기로 했습니다.

 

(176분) 제가 J를 풀었습니다.

 

(190분) 제가 해석을, mhy가 세그로 "빈 칸 중 n번째에 채우는 코드"를 만들어서 수열 복구를 성공했고, B를 풀었습니다.

 

이때쯤 스코어보드가 닫혔습니다.

 

(210분?) SongC가 K를 제출하고 한번에 맞았습니다. 아마도 퍼솔이었던 걸로 기억합니다. SongC가 대회 당시 퍼포먼스가 엄청났습니다.

 

(240분 경) SongC는 E의 풀이를 아호코라식으로 하면 된다고 했고, 이걸 짜기 시작했습니다. 한편 mhy가 코드를 싹 다 엎고 새로 짜기 시작했습니다. 저는 L의 풀이를 냈지만 짜기에는 이미 늦은 상태였습니다.

 

(280분 경) E가 아호코라식으로 풀리지 않고, 해싱을 잘 해야 한다는 사실을 깨닫고 시간 부족에 절망했습니다. mhy는 싹 갈아엎은 코드를 제출했는데, 드디어 C가 정답이 나왔습니다! 패널티는 엄청 쌓였지만 그래도 행복했습니다.

 

(300분 경) 대회가 종료되었습니다.

5. 대회 후

대회가 끝나고 다른 팀들에게 물어보니 아무래도 다들 뭔가 꼬였나 봅니다. 상위권 팀들에게는 J나 C 같은 문제들이 발목을 잡는 셋이 아니었나 생각합니다. 주최진이 C같은 기하 문제에서 많이들 헤멨는데 앞으로 기하를 더 많이 내는 게 어떨까(?!??)하는 충격적 발언을 해버렸습니다.

 

예상 순위는 작년처럼 한 7등 정도였는데, 이처럼 우리 위로 올라갈거라 생각한 팀들이 예상과는 달리 미끄러지는 곳들이 많아서 결국 예선과 같은 전체 4등, 교내 2등으로 마무리해서 은상을 받았습니다!

 

정말 여담이지만, 리유나는 세일러복을 좋아해 출제자로서는 드디어 '세일러복을 입고 ICPC 수상'이라는 꿈을 이루었기에 상당히 만족했습니다 ㅎㅎㅎ... 수상 사진 올라오면 추가로 올리겠습니다!

 

은상 수상은 정말로 기쁘고, 커리어 하이라고 할만하지만, 대회 외적으로는 사실 아쉬운 부분들도 상당히 많았습니다. 전체 우승을 같은 학교 팀인 Penguins가 차지했는데, 이번부터 적용되는 룰에 따르면 리저널 1등이 나온 학교는 1등이 월파 직행, 그 외는 교내 1, 2, 3등이 세미 파이널에 가는 식으로 되었다고 하더라고요. 그래서 Penguins가 1등을 했기 때문에 저희는 학교 2등임에도 불구하고 세미 파이널에조차 나갈 기회를 받지 못했습니다. 19년, 22년에 당시 룰이었다면 세미 파이널 진출이 가능했기에 더더욱 아쉬웠네요.

 

차라리 아예 희망이 없었다면 모를까, 세계대회 티켓을 눈앞에서 놓친 기분이라 스코어보드 개봉에서 타이완대학의 std_abs 팀이 끝내 E를 틀리고 2등으로 머무르는 순간 팀원 세명이 모두 절규를 했습니다. 세계대회 진출을 위해서는 같은 학교 친구들이 있는 팀이 우승하지 못하기만을 빌어야 하는 이 상황이 참 아이러니했습니다. 아무쪼록 멋진 퍼포먼스로 전체 우승을 차지한 Penguins팀, 진심으로 축하합니다!

 

어쨌건 한편으로는 아쉬웠고, 저와 mhy의 무관행진을 끝낼 절호의 기회는 놓쳤지만 그럼에도 만족스러운 높은 성과를 얻어서 뿌듯합니다! 대회에 참여하신, 그리고 운영에 참여하신 모든 분들 여러분 정말 수고 많으셨습니다!

6. 앞으로?

작년처럼 "오예 이팀 그대로다! 내년에도 잘부탁해!"인 상황은 아닙니다. 당초 저를 비롯한 모든 팀원들은 제가 이 대회를 끝으로 은퇴할 것이라 생각했고, 그래서 문송송에서 제가 비는 자리에 누구를 넣을지를 이미 결정해 둔 상태였습니다. 지금에 와서는 제가 미련이 너무 남아서 졸업을 미루고서라도 한번 더 참여할까 고민 중이긴 한데, 일단 기존 팀을 유지하는 것은 상당히 힘들어진 상태입니다.

작년 글을 보면 "내년에 성공하지 못하더라도 너무 낙담하지는 않으려고 합니다!"라고 적혀 있는데, 이게 사람 심리가 마음대로 되면 얼마나 좋을까요 ㅋㅋㅋ 막상 이런 상황이 오니까 너무나도 미련이 남습니다. 차라리 마지막을 그냥 아예 희망 없이 끝냈더라면 미련도 덜 남을텐데, 눈앞에서 티켓이 날아간 듯한 기분이라 너무나도 아쉬워서 이러다 PS 악귀가 되는 건 아닐까 걱정입니다. 무언가에 열심히 도전해서 점점 성적이 오르고 성과가 나와서 세계 대회까지 나가는 그런 로망이 있잖아요? 지금 은퇴를 한다면 충분히 높은 곳까지 왔지만 못내 아쉬움이 남을 듯합니다. 그런 의미에서 어쩌면 마음 속에서 PS가 단순한 문제풀이 이상으로 자리잡지 않았나 싶네요. 하지만 한편으로는 이렇게 물려서 결국 멘탈만 터지고 힘들어하는 경우들 또한 이쪽 판에서 많이 목격해왔기 때문에 제게 가장 좋은 선택이 무엇일지는 여전히 고민되는 상태입니다.

 

여하튼, 제가 계산해보니 놀랍게도 내년 icpc까지는 출전이 가능해서 선택지는 다음과 같이 네가지 정도가 있을 듯합니다.

1. 깔끔하게 미련 버리고 은퇴.

2. 여러 사유로 터지는 다른 팀들이 있기에, 교내 팀원들을 잘 모아서 적어도 세미 파이널 정도는 갈 수 있을 전력의 팀 꾸리기.

3. 애지중지하며 키운 후배들 두명이 전역하고 복학하기에, 걔네 둘을 데리고 나가기.

4. 억지로 문송송으로 한번 더 나가기(?)

 

어떤 선택을 하게 될지는 많은 고민을 거듭할 것이고, 제 삶에서 후회없을 좋은 선택을 하고 싶기 때문에 아무래도 쉬이 끝날 고민은 아닐 듯합니다만, 어떤 선택을 하건 그 선택에서 후회없는 결과를 낼 수 있도록 최선을 다하겠습니다!

 

마지막으로, 이 자리를 빌어 2년간 같이 호흡을 맞추며 달려 온 SongC, mhy908에게 깊은 감사의 말을 드리고 싶습니다. 이 멋진 두 후배들 덕분에 모자랐던 제가 많이 배우며 크게 성장할 수 있었습니다. PS 외적으로도 2년여간 같은 팀을 이루어 목표를 향해 같이 달려간 경험은 앞으로 인생에서 정말 소중한 경험이 될 것 같습니다.

저는 진심으로 제 인생에서 최고의 PS팀, 아니 모든 분야를 통틀어서 최고의 팀이 어디였냐고 물어본다면 주저없이 문송송 계란탁이었다고 말할 수 있습니다. 내년에 설렁 같은 팀을 이루지 못하더라도, 존경하는 두 후배들이 꼭 리저널 우승이라는 꿈을 이루고, 특히 mhy가 무관탈출을 할 수 있기를 마음 속 깊은 곳에서부터 진심으로 바라는 바입니다. 감사합니다.

 

7. 문제별 풀이 정리

A: Apricot Seeds

이상한 '수열과 쿼리' 문제. 특정 구간에서 몇번씩 버블소트를 하는 쿼리가 들어오고 그 결과를 출력하는 문제이다. 아무도 풀지 못한, 모두를 죽여버린 문제이다. 풀이를 얼핏 지나가면서 들었지만 내 실력이 모자란지 잘 기억이 나지 않는다.

 

B: Black Box

ICPC보다는 구데기 컵이 조금 더 어울리지 않았을까 싶은 문제. Python-like pseudocode가 와서, 이 코드의 역함수처럼 작동하는 함수를 만들면 된다. 대강 이야기하자면 슈도코드의 작동 방식은 우선 리스트가 주어졌을 때, 특정 규칙에 맞게 리스트에서 원소들을 뽑아내서 스택에 채우고, 그 스택에서 첫번째 항목과 다시 특정 규칙을 통해 나온 항목을 swap하면 된다.

 

swap하는 규칙은 리스트의 마지막 원소에 달려 있고, 마지막 원소는 swap으로 바뀌지 않음이 보장되어서 일단 그 규칙에 따라 다시 원소 두개를 바꿔 주면 된다. 이후에, 원래 리스트에서 무조건 맨 첫번째 원소가 스택에서도 맨 첫번째로 들어간다는 점에서 시작해서 규칙을 만족시키면서 들어가려면 어떤 자리에 뭐가 들어있어야 하는지를 역추적해서 찾으면 된다. 이 때, "n개의 칸들 중 비어있는 칸 중 몇 번째 자리"를 찾아야 하기 때문에, 세그먼트 트리를 통해서 위치들에 어떤 원소들이 들어왔는지를 업데이트하면서 구현해야 하는 것이 가장 구현 난이도를 올리는 부분이다.

 

근데 구현 난이도보다는 해석 난이도가 훨씬 높다. 망고 키위 애플 파파야 바나나 멜론 코코넛 라임... 코드를 읽고 있다보면 정신이 아득해진다.

 

C. Farm

기하 문제고, 우리 팀은 정말로 고생을 했던 문제였다. 좌표압축을 잘 하고 쭉 점들을 스위핑하면서 확장될 수 있는 곳까지 최대로 확장하는 식으로 하면 별 문제는 없다고 했는데, 희한한 문제 조건 때문에 이상한 모양의 끊어진 다각형이 나올 수 있고, 그 경우 x축 위에 감염지가 발생하면 가로 일직선 모양의 rectangular area라는 기가 막힌 사태가 벌어질 수 있어서 이런 경우 예외 처리를 아주 잘 해야 했다. 심지어 이것 때문에 대회 중에 질의응답까지 했는데 yes라고 답이 돌아와서 꽤나 어이가 없었던 기억이 난다. 우리는 y=-1인 곳에서부터 다각형이 시작한다고 가정하고 푸는 방식으로 했다.

 

D. Fraction

가장 쉬운 문제 중 하나가 아니었을까 싶다. 괄호 문자열이 valid한지 확인하고, 규칙에 맞게 식을 만들어서 계산하면 된다. 우리는 규칙이 틀렸을 때 -1 출력을 까먹어서 아마 한번 틀렸던가 그랬을 것이다.

 

E. K-Lottery

적당히 트라이를 만들고, 아호코라식....을 하는 게 아니라(SongC가 대회 후에 이걸로도 잘 어떻게 하면 된다고는 했다)해싱으로 처리하고, 특정 상황에서 누적합을 전부 하나씩 빼주는 식으로 fail function을 관리해야 하는? 그런 문제라고 들었다. 문자열 쪽은 나도 약한 부분 중 하나라서, 풀이를 들었는데 잘 기억에 남지 않는다 ㅠ

 

F. Lucky Draws

앞부터 점을 찍는다고 가정할 때, D[i][j]를 i개를 찍음, 마지막은 j에 찍음 으로 정의하고 dp를 돌린다. 그렇게 하면 그냥 하면 O(kN^2)라는 시간이 나오는데, 함수가 monge한 성질을 가지기에 분할정복 최적화가 가능한 형태라고 한다. 이걸 하면 O(NklogN)이 되고, Nk가 50만이라 가능하다고 한다.

 

G. Magic Cards

예시가 된 카드의 원리는 이진수 그거...는 뭐 너무 유명하고, 포인트는 어차피 카드 100장 숫자 50만까지라서 1부터 50만까지 모든 숫자들에 대해서 TFTTF...하는 정보를 미리 저장해두면 된다. 비트 많이 안 쓴다. long long 2개, 혹은 파이썬이면 그냥 정수로 해도 문제 없었을 것으로 보임.

 

H. M.S.I.S.

뭔가 우리 팀 이름이랑 비슷해보이는 문제가 나왔다(??)

최적으로 구축했다면 모든 열에 대해서 위쪽이든 아래쪽이든 둘 중 하나는 사용된다는 것을 보일 수 있음. 이제 둘중에 하나 쓸 거 고르고 위치 맞게 끼우면 된다고 한다. 여기서 중요한 부분은 둘 다 쓰이는 것들을 어떻게 잘 고를지인데, 윗줄에 대해 정렬하고 D[i][j]=i번째까지 선택, 아랫줄에서 마지막으로 고른 건 j. 라는 식으로 하고 점화식을 잘 구축하면 n^2에 풀리고, n=10000이라서 아슬아슬하게 돈다고 한다.

 

I. Product Delivery

가장 쉬운 문제 중 하나. 그리디하게 접근해서 풀면 되는 것 같다. 맨 끝에서부터 최대한 되도록 상품 보내는 식으로 반복하면 될 거 같은데, 짜보지는 않아서... boj에 올라오면 바로 풀어 볼듯하다.

 

J. Special Numbers

처음 봤을 때는 10^20까지 된다는 조건 보고 뒷목잡고 넘어지면서 와 이걸 폴라드 로를 써야 하나?! 하면서 팀노트 뒤적거렸는데, 다시 생각해보니 자릿수의 곱이면 9까지의 숫자들에 대해서만 생각하면 되기 때문에 큰 수 인수분해를 해서 푸는 문제는 아니었다.

내 풀이는 다음과 같았는데, f(n, k, zero)를 "0부터 n까지의 숫자 중에서 k-special한 것의 개수, zero가 True이면 leading zero를 생각하고, False면 그렇지 않은 경우."라고 정의를 한다. 그리고 n의 첫자릿수를 미리 빼두고, 그것이 0일 때부터 n의 첫자리수가 될 때까지 for문을 돌리면서 재귀를 돌리는 식으로 했다. 예시를 들자면, 4940이라는 숫자가 12-special한지 보려면, 우선 0에서 999까지 중 12-special한 것의 개수를 세고, 그다음 1000에서 1999중에서 12-special의 개수를 세는데, 이 때는 f(999, 12, True)로 넣는다. 이는 0을 0이 아니라 000으로 보고, 1도 1이 아니라 001로 보고... 같은 느낌이고, 0을 곱하면 언제나 모든 수의 배수가 된다는 점을 잘 처리하기 위해서이다. 그 다음에는 2000에서 2999 까지 중에서 "6 special"의 수를 세어야 하는데, 천의 자리에 2가 들어간다는 가정 하에 나머지를 세는 것이기 때문이다. 이런 식으로 메모이제이션을 동반한 재귀를 돌리면 생각보다 돌아가는 숫자들은 대개 한정적이기 때문에 시간 안에 아주 여유롭게 돌아갔다.

처음에는 한자릿수의 경우에서 if k>n return 1 else 2라는 코드를 짰는데, 생각해보니 2 뿐 아니라 4, 6, 8등도 2-special이라서 이 점에서 틀렸다. 예제에는 하필 k=5, 15인 경우만 나와있어서 이 경우를 건드리지 못했다. 그 다음에는 n이 101과 같이 0이 자릿수에 들어가는 경우에서 에러가 생겼는데, 101이라는 숫자는 중간에 0이 들어가서 어떤 k에 대해서든 k-special이지만 재귀로 넣으면서 그냥 1에 대해서 체크하는 식으로 했고, 그렇게 카운트되지 못한 오류가 있었다. 이 두가지 오류를 고치는데 장장 세시간이 걸려서 돌이켜보니 조금 슬펐다.

 

K. Tandem Copy

SongC가 잡고 으헤헤헤(본인 언급에 따르면?)풀어버린 문자열 dp 문제. 정확한 풀이는 잘 모르고, 이런저런 이상한 케이스들을 처리하기 위해서 꽤나 고생을 해야 하는 문제로 보였다.

 

L. Walk Swapping

풀이는 도출했지만 시간이 없어 구현도 들어가지 못했던 문제. 이건 풀었어야 하는데...하는 아쉬움이 남는 것중 하나였다.

결국 왼쪽으로 갔다가 오른쪽으로 감<<을 하면 이전이랑 달라지는 게 하나도 없으므로, 쭉 왼쪽으로만 간다/쭉 오른쪽으로만 간다 라는 두가지 경우밖에 존재하지 않는다. 그렇다면 숫자 하나를 잡고 걔를 쭉 한칸씩 이동시키는 느낌이고, 한바퀴를 돌면 수열을 한칸씩 왼쪽/오른쪽으로 시프트시킨 것이다.

일단 가능한지를 보려면 수열 문자열을 적당히 해싱하고 모든 n에 대해서 n번째 수를 돌려서 저게 나올 수 있는지 없는지를 판단하는 식으로 보고, 그렇게 해서 가능하다면 가능한 경우들에 대해서 왼쪽 쭉/오른쪽 쭉 돌려서 나오는 시행 횟수 중 어느 것이 더 작은지, 그걸 쭉 보는 식으로 풀면 된다. 라는 결론이 나왔지만 풀지 못했다. 사실 그래서 검증도 못 해봤다. 이 풀이가 아닐 수도 있으니 boj에 올라오면 그대로 풀어볼 듯 하다.