안녕하세요!

PHP 제로데이가 하루아침에 두 개나 나왔습니다. 무서운 시대입니다.

PHP는 이제는 제가 그렇게 잘 다룰 수 있는 물건이 아닙니다. 예전 사이트들의 배포 방법을 바꿔야겠다고 결심하고 어제 하루 동안 클로드를 열심히 시켜서 마이그레이션했습니다.

어제까지는 워드프레스 블로그였습니다만, 이제는 Tiptap 에디터를 기반으로 자체 제작한 블로그가 되었습니다. 스태틱 사이트는 아니지만 어떠신가요? 괜찮은 것 같나요?

좀 더 많은 커스터마이즈를 할 수 있을 것 같아서 기분이 좋습니다. 글을 자주 써야 의미가 있는 것이겠지만요….

바쁘다고 이 문제 예제에 짧은 글도 남기지 못했으나, 마지막의 마지막에서야 소회해 봅니다.

2017년 10월 BOJ를 만나고 이렇게 재밌는 게 있다는 걸 처음 알고 수능 공부도 반쯤 제치고 문제풀이를 시작했습니다.

운 좋게도 문제풀이를 좋아하는 사람들이 많은 학교에 들어갈 수 있었고, 함께 열정을 쏟아부을 수 있는 팀원들과 만나서 즐거운 하루하루를 보낼 수 있었습니다.

제가 좋아하는 문제풀이를 다른 사람들도 좋아했으면 하는 마음이 생겼고, 운 좋게도 기여할 수 있는 부분이 많았습니다. 많은 대회를 열고 많은 문제를 냈습니다. 더 나아가 다른 분들이 대회를 열고 문제를 내시는 것도 도와드릴 수 있었습니다.

문제풀이를 재밌게 할 수 있는 사이트도 만들었고 많은 분들께서 다녀가셨습니다. 참 행복했던 기억뿐입니다.

무한히 겹쳐져 있던 세계선들 중 이곳으로 저를 인도해 준 BOJ에게 무한한 감사와 경의를 드립니다.

2017. 10. 7 – 2026. 4. 28

솔브드의 폐업으로 인해 가장 안타까운 점 중 하나는 솔브드 굿즈 샵이 더 이상 열리지 않는다는 점이었는데요, 저로서도 이제 프로그래밍 대회 관련 굿즈는 정말로 대회에 나가야만 구할 수 있겠다 싶었습니다.

정확히는 올해 초 마이 메이플스토리 랩스를 통해 ‘넥슨 에센셜’이라는 곳의 존재를 알기 전까지였습니다. 어렴풋이 NYPC도 이곳에서 굿즈 샵을 열 수 있지 않을까 하는 생각이 들었는데, 현실화되었습니다.

다만 9월 28일에 마감된다는 아주 아쉬운 사실이 있습니다. 글러먹은 마음가짐일지도 모르겠고 이런 생각 때문에 여태 얼마를 썼는지 모르겠지만, 결국 판매할 때 사둬야 한다고 생각합니다. 그래서 리뷰를 해 보려고 합니다. 모든 굿즈는 회사로부터 받았습니다만 딱히 별도의 고료를 받고 작성하는 글은 아닙니다. 혹시 몰라서 언급하지만 월급은 받았습니다.

카드 스티커

교통카드로 쓰던 우리은행 체크카드가 있었는데요, 카드가 으레 그렇듯이 디자인이 다소 아쉬웠습니다. 아쉬운 대로 그냥 쓰고 있다가 이번에 카드 스티커를 붙여 해결했습니다. 심플하고 프로그래머스럽습니다. 훨씬 낫네요.

이 스티커가 정확하게 붙이기에는 다소 어려움이 있는데요, 두 장이 들어 있어서 혹시라도 실수하면 한 번의 기회가 더 있습니다. 저도 붙이면서 약간의 오차가 있기는 했는데 굳이 남은 한 장을 쓰지는 않았고, 다른 카드가 생기면 거기에 붙이기로 했습니다.

LED 키캡 키링 — 1구, 2구

피젯 토이입니다. 키보드에서 떼온 것처럼 생겼는데 누른다고 뭔가 입력이 되진 않고요, 키링입니다. 그렇게 막 용도나 의미가 있는 물건은 아니지만 한 번쯤 갖고 놀아 보면 이게 손의 심심함을 잘 해결해 줄 수 있다는 사실을 깨닫게 될 겁니다. 비슷한 걸 갖고 계신 분은 아실 거예요. 그런데 이게 다른 피젯 토이와 구별되는 장점이 뭐가 있느냐 하면, 청축이고 불이 들어온다는 것입니다.

찰칵찰칵 소리가 듣기 좋지 않나요? 특히 2구는 번갈아가면서 누를 수도 있어서 만족감이 두 배입니다. 다만 키 누르는 소리가 시끄럽게 들릴 수도 있으니 상황에 따라 주의해야겠습니다.

포인트 키캡

OEM 프로필 맨 윗 줄에 끼울 수 있는 키캡입니다. 마침 제 키보드도 OEM 프로필 키캡이라 잘 호환이 됩니다. Esc 키에 포인트를 줘 봤습니다.

키캡 호환성

위에서 소개한 LED 키캡 키링하고도 서로 호환이 잘 되기 때문에, 포인트 키캡을 LED 키캡 키링에다 꽂고 LED 키캡 키링에 있던 키캡을 적당한 키보드에 옮겨올 수도 있습니다. 그래서 윗쪽 줄 키보드의 Esc도 교체해봤습니다.

멀티 클리너

보통은 안경닦이로 쓰일 것 같습니다. 저는 안경을 쓰지 않는 대신에 노트북 액정을 닦는 데 씁니다. 오랜만에 깔끔한 액정을 보니 마음이 좋습니다. 맥북 프로 14인치 키보드 사이즈와도 딱 맞아서 키보드 덮개로도 쓸 수 있습니다.

무엇보다도 프로그래밍 대회 스티커로 도배가 되어 있는 제 노트북과 잘 어울리는 클리너라서 더 마음에 들게 되었습니다.

스티커 세트

그렇지만 노트북이 이미 스티커로 도배가 되어 있어서 굿즈 샵 스티커를 붙일 공간이 나오지는 않았습니다. 시간이 있었더라면 맥북 커버를 하나 더 사서 거기에 붙여 봤을 텐데요, 저는 이미 공간이 없으니 아직 노트북 커버가 허전하신 분들께 추천드려 봅니다.

하지만 꼭 노트북에만 붙여야 된다는 법은 없기 마련입니다. 저는 사원증 뒷면에다 붙여버렸습니다. 업무상 numpy를 쓰지는 않지만, 이걸 본 동료가 피곤해 보이는 저를 보면 커피를 사줄지도요…

사무실에 있는 필드 머신에다 ‘build succeeded’를 붙일까도 고민해 봤는데, 회사 장비에 스티커를 붙이면 안 될 것 같아서 보류 중입니다.

맥세이프 카드 홀더

아이폰에는 이런 문명이 있군요? 저는 2021년에 지금 일하는 곳의 옆옆 건물에서 일하고 있을 때 샀던 갤럭시 폰을 아직도 쓰고 있어서, 다른 분의 폰을 빌려 찍어봤습니다.

카드를 꽂아서 쓸 수 있는 것 같습니다. 사진의 아이폰보다는 조금 얇습니다. 저도 아이폰이었다면 numpy곤 두 배 이벤트를 즐길 수 있었을 텐데 아쉽습니다.

장패드

그리고 이 모든 사진들을 찍은 배경이 되어 준 장패드입니다. 제 책상에 뭐가 많아서 아까는 잘 보이지 않았지만, 일반적인 셋업에서는 이렇게 되겠습니다.

놀랍게도 이 장패드에는 특별한 효능이 있다고 합니다.

근데 고급져 보이는 건 맞는 말인 것 같습니다. 검정색 배경에 심볼이 배치된 디자인이 흰색 책상 위에서 꽤 괜찮은 포인트가 되면서도, 일 할 때는 집중을 깨지 않습니다. 이 장패드를 깔고 NYPC를 치면 정말로 높은 점수를 받을 수 있을지도요. (이를 입증할 수 있는 근거는 없습니다)

의류 — 후드집업, 후드 바람막이, 반팔티

의류도 받기는 했는데 제가 어떻게 사진을 찍어도 앞뒷면이 한 번에 보이는 공식 사진보다 좋은 사진을 찍을 수가 없었습니다.

이 사진이 저의 한계였습니다. 죄송합니다…

프로그래밍 대회에서 상의란 참가 인증과도 비슷한 의미를 갖는 동시에 입을 거 찾기 귀찮은 개발자들의 한 줄기 빛과도 같습니다. 안타까운 점은 보통 재질이나 디자인이 구리다는 점입니다. 예산 문제도 있고, 기업 대회가 아니고서야 전담 디자이너도 잘 없고 하니까요. (특히 ICPC가 유감스러운 디자인을 자주 들고 옵니다)

NYPC의 상의 디자인은 (다른 대회 옷들과 비교해 봤을 때) 항상 탑 티어였습니다. 이 옷들도 그렇습니다. 잘 생각해 보세요.

• 먹다가 뭘 흘려도 옷에 안 묻는 검정색

• 앞면 로고가 미니멀해서 예쁨, 구구절절 뭐가 없음. 아는 사람은 알고, 모르는 사람이 봐도 무슨 뉴욕 어쩌구 갔다 오셨어요? 하고 대화 주제 하나 뚝딱임

• 뒷면 픽셀스러운 중괄호는 누가 봐도 심플함. 개발자가 보면 개발자인지 알 수 있을 것 같은데 개발자 옷만 이렇게 예쁘게 파는 곳 잘 없음. 이런거 보면 저 같으면 어디서 사셨냐고 물어봤습니다. 마지막으로 이런 거 물어본 사례는 vivastudio 대신 visualstudio를 인쇄한 티셔츠를 봤을 때였는데, 아쉽게도 어떤 학과의 과티였다고 합니다.

• 누구나 살 수 있기 때문에 막 어디 본선 나가야만 얻는 티셔츠와 다르게 이걸 입어도 기만자가 되지 않을 수 있음

후드집업은 기모여서 따뜻합니다. 그런데 저는 오버핏인 걸 간과해서 아무래도 너무 큰 사이즈를 받게 된 것 같습니다. 사이즈를 잘 보고 구매하세요. 나머지 옷들은 사이즈가 괜찮았습니다.

옷이 좀 많이 컸습니다.

ICPC 같은 곳은 대회 티셔츠를 안 입으면 대회장에 입장 불가하기 때문에 일부러 참가자들에게 옷을 크게 만들어서 줍니다. 그런 곳은 다른 사이즈의 여별을 주지는 않습니다.

이건 대회 티셔츠 같으면서도 대회 티셔츠가 아니라서 (9월 28일까지는) 다시 사면 그만이기 때문에 다행입니다. 다시 사는 건 제 돈으로 샀습니다.

NYPC 굿즈들은 여기에서 구매하실 수 있습니다. 9월 28일까지입니다. 프로그래밍을 컨셉으로 한 굿즈 잘 나오지 않는데 관심 있으시다면 이번 주에 하나 장만해 보시는 걸 추천드립니다! 무엇보다도 저로서도 이게 나중에 언제 재판될지 모르겠기 때문입니다!

2024년 회고

올해는 블로그에 글을 많이 쓰지 못했습니다. 아쉬운 일입니다. 그만큼 바쁘게 살았다는 뜻도 될 것 같습니다. 여전히 저는 GPT를 사용하지 않고 수제 포스트를 작성하고 있으므로 많은 양해를 부탁드립니다…

여러 게임들에서 모닥불은 흥미로운 장치입니다. 모닥불 밖은 수많은 난관과 적들로 바글바글하지만, 모닥불에서만큼은 안심하고 쉬어갈 수 있고, 앞으로 어떻게 하면 좋을지 고민하면서 재정비할 수 있는, 하지만 언젠가 떠나야 한다는 것을 알고 있는, 그런 곳입니다.

이제 먹고 사는 문제를 생각해야 될 때가 되었습니다. 그 전에 고민하는 시간을 가져 보려고 합니다.

졸업

결국 졸업을 하네요. 사실 큰 감흥은 없는 것 같습니다. 대학 생활은 참 길었습니다. 2018년에 입학했으니 7년을 다녔던 셈이 됩니다. 학교에 들어오기 위해서 수험생활을 했던 글을 돌아보는데, 그때의 나와 지금의 나는 참 다른 생각을 하고 있구나 같은 생각이 들었습니다.

지금 와서 말하는 거긴 하지만, 사실 18수능 당시에 앞자리 수험생의 수학 30번 답안을 봤습니다. 보려고 해서 본 건 아니고, 문제를 풀다 앞을 봤는데 OMR에 마킹되어 있는 수가 또렷이 보였습니다.

’21’.

하지만 그걸 보고도 제가 마킹한 답은 ’42’였습니다. 그 수험생이 설마 정답을 냈을 거라고 생각하지 않았던 것도 있고, ‘베낀다’는 행위부터가 마음을 불편하게 하기에 충분했기 때문입니다. 만약 눈 딱 감고 베꼈으면 학교가 달라졌겠다 싶습니다 . 흔히들 서강대생들은 소위 ‘연고대’에 떨어져서 오기 때문에 특유의 내재된 자격지심이 있다고들 하는데, 입학 당시에 ‘그때 30번을 베꼈으면!’이라던가, ”간판’을 낮추고 다른 학교를 갈 걸!’ 같은 생각을 안 했다면 거짓말일 테니, 그렇게 틀린 말은 아닌 것 같습니다.

지금은 전혀 그렇게 생각하지 않습니다. 2018년의 ACM-ICPC Team이 없었으면 제가 문제해결을 이렇게까지 좋아하는 사람이 됐을 리가 없습니다. 그리고 그러다가 맡게 된 학회장이라는 역할은, 극히 내향적이고 남들 앞에 잘 나서지 못하던 제 성격을 180° 바꿔놓았습니다(그렇다고 아직 ‘외향적’이라고 할 수는 없을 것 같네요). 가장 중요하게는, 제가 서강대를 가지 않았다면 솔브드도 없었을 거라는 건 틀림없습니다. 물론 자료구조 성적을 별 시덥잖은 이유로 B+ 주는 등 마음에 안 드는 점들도 있기야 하지만 이곳에서의 학교생활은 지금의 저를 만든 중요한 조각이 되었습니다.

더구나 집안 형편이 어려운 와중에 4년간 학비를 전액 지원받아 다니면서 정말로 하고 싶은 일들에 열정을 쏟을 수 있었던 점은 정말로 학교에 감사한 점입니다. 다만 학교가 제게 해 준 것에 비해 제가 그렇게 학교를 열심히 다녔느냐 하면… 처음에는 공부를 좀 열심히 했던 것 같은데 나이를 먹을수록 그렇지 않게 된 것 같고, 수업 안 듣고 문제 풀거나 개발을 했습니다. 죄송합니다. 얼마나 학교의 위상을 올렸을지는 모르겠지만 대회 나가서 상 많이 타 왔으니 용서해주세요…

조교

올해는 CSE4152 문제해결프로그래밍 과목의 학부조교를 했습니다.

위에다 학교 찬양을 마구 해 뒀지만 사실 학교 들어와서는 커리큘럼에 사소한 불만들이 좀 있었습니다. 커리큘럼이 컴퓨터과학을 제대로 배우는 데는 문제가 없긴 했는데요, 몇몇 과목에 아쉬운 부분이 있었습니다. 예를 들어 컴퓨터공학설계및실험I에서는 PHP 프로그래밍과 MFC 어플리케이션 개발을 실습했는데, 회사를 다녀오니 많은 과목들이 최신화되어 있어서 놀랐습니다. 그리고 그 놀람 중 하나는 알고리즘 문제해결 과목의 신설이었습니다.

이주호 교수님의 의지로 신설된 PS 과목은 과제와 시험이 전부 문제해결입니다. 학생들이 엘리스에 코드를 제출하면 실시간 자동 채점을 받습니다. 저는 이번에 과제 데이터를 준비하고 시험 문제를 출제하는 조교 역할을 맡았습니다. 기술적으로는 엘리스 플랫폼 상에서 BOJ의 ‘스페셜 저지’와 ‘인터랙티브’에 해당하는 것들을 구현해야 했던 점이 제일 어려웠지만 제가 나름 재사용 가능하도록 만들어 놨으니 졸업하더라도 이후 조교분께서 아마 활용해서 문제를 만드실 수 있지 않을까 싶습니다. 별개로 엘리스는 문제 수정 시 모든 데이터를 다운받아서 브라우저 메모리에 저장하도록 되어 있어서 큰 데이터를 준비하기 부담스럽고, ‘부분문제’를 만들더라도 한 태스크에서 메모리 초과 시 전체가 0점이 되는 등의 불편함이 있습니다. 부디 외고쳐졌으면 좋겠습니다.

이외에는 문제해결 과목이 생겼다는 데에 큰 의미가 있다고 생각하고, 앞으로도 학생들이 알고리즘 문제해결에 재미를 붙일 수 있는 좋은 계기로 지속적으로 작용할 수 있으면 좋겠습니다. KAIST 등 다른 학교에 문제해결 수업이 있는 게 부러웠는데 이제 남부럽지 않은 학교가 되었네요.

중간고사/기말고사 문제들이 궁금하시다면 BOJ에서 풀어보실 수 있습니다.

솔브드

올해 초에 온사이트 프로그래밍 대회인 그랜드 아레나 파티를 개최할 수 있었습니다!

하지만 안타깝게도 이후에 아레나가 더 열리지는 않고 있습니다. 아레나는 레이팅을 매기는 대회이기 때문에 솔브드에서 모든 아레나를 검수해 왔는데, 검수를 수없이 해온 저로서도 아레나 일정에 맞춘 대회 검수는 제 생각보다 훨씬 많은 리소스를 필요로 했고, 급기야 몇몇 대회에서 실제로 문제가 발생하기도 했습니다. 그렇다고 검수를 다른 분께 맡기자면 검수비를 들여야 하는데, 아무리 봐도 수고에 비해 합당한 검수비를 드릴 수 없을 것 같아서, 이걸 해결할 방법을 찾지 못하는 한 당분간 열리지 않을 것 같습니다. 너무 아쉽습니다.

그런가 하면, 솔브드를 전세계 경쟁 프로그래밍 커뮤니티에 소개하는 영광스러운 일도 있었습니다. ICPC 아스타나 월드 파이널 일정 중 하나로 경쟁 프로그래밍 관련 여러 도구 및 방법론을 소개하는 CLI 심포지움이 있는데, 대회 측에서 솔브드를 소개해줬으면 좋겠다고 발표자로 초청해 주셔서 카자흐스탄에 다녀왔습니다. 발표는 영어로 30분간 진행했습니다.

하필이면 제가 마지막 순서고 제 앞에는 코드포스의 KAN님과 앳코더의 maroonrk님이 발표하셔서 정말로 많은 긴장을 했습니다. 청중께서는 주로 ICPC 리저널 콘테스트 디렉터(RCD) 혹은 월드 파이널 스탭이었는데, 다행히도 걱정했던 것과는 달리 반응이 꽤나 좋았다고 합니다. 인정받은 만큼 앞으로도 알고리즘 문제해결 커뮤니티에 의미 있는 기여를 할 수 있으면 좋겠습니다.

이외에 올해의 솔브드는 대부분 보이지 않는 곳에서 일했습니다. 가령, 관리 콘솔을 새로 만들었습니다. 관리 콘솔은 제가 주로 처리하는 민원(?)들을 좀 더 빠르고 편리하게 처리할 수 있게 해 줘서, 다른 일들에 집중할 수 있었습니다. 가령 프로필 뱃지를 등록하려면

일러스트레이터에서 작업 → 포토샵에서 $512\times 512$로 리사이징 → TinyPNG로 용량 최적화 → S3에 게시 → URL 나오면 그제서야 솔브드 DB에 등록

을 해야 했는데, 이제는 리사이징, 최적화, 업로드, DB 등록을 한 화면에서 다 해 줍니다.

그리고 사이트 도움말 페이지도 만들었습니다. 이건 좀 늦은 감이 있는 것 같지만 항상 better late than never입니다.

말고도, 신기능 랜덤 마라톤, 프로필 배경 상점, 그리고 문제 오류 제보가 업데이트되었습니다. 길라잡이도 작업에 착수해서 이제 글을 작성하고 있는 단계입니다.

솔브드는 2022년 12월에 회사로 바뀌어서 업력 2년을 맞았습니다. 솔브드의 비전은 그때도 지금도 이렇습니다.

• BOJ에는 정말 많은 문제들이 아카이브되어 있습니다. 이를 잘 체계화해서 알고리즘 문제해결 학습자 및 향유자를 위한 최대의 아카이브 및 커뮤니티로 자리매김하고 싶습니다.

• 알고리즘 문제해결은 사고력과 구현력을 키우는 데에 많은 도움을 주고, 무엇보다도 재밌습니다. 솔브드는 이 분야의 저변을 확대하고, 또한 대중화하고 싶습니다. 특히 코딩 테스트를 준비하던 학습자가 문제해결 자체에도 재미를 붙일 수 있게 하고 싶습니다.

• 한국에는 많은 알고리즘 문제해결 동아리들이 있고, 많은 고등학교/대학교 대회, 심지어 개인 주최 대회까지 꾸준히 많이 열리고 있습니다. 이런 생태계가 최대한 지속 가능하도록 돕고 싶습니다.

이런 것들을 제대로 하기 위해서는 많은 시간이 필요합니다. 솔브드에 쏟을 시간을 확보하려면 다른 일에 쏟을 시간을 줄여야 합니다. 결국 솔브드가 재정적으로 자생 가능해야 한다는 뜻입니다.

2024년 말 기준으로 솔브드는 재정적으로 자생이 가능하기는 합니다만, 저는 재정적으로 자생이 안 됩니다. 뭔가 다른 일을 해서 먹고살아야 합니다. 엎친 데 덮친 격으로 올해 여름에 솔브드 굿즈 샵과 관련해서 결제대행사가 대금을 3개월 늦게 정산하게 된 큰 사고가 있었고, 결제대금을 정산받지 못했기에 굿즈를 (주문해주신 분들께 받은 돈이 아닌) 사비로 발주해야 했던 일이 있었습니다. 큰 규모의 유동성을 잃어서 하반기에는 정말 많이 고생했습니다.

솔브드의 사업화는 학교를 다니는 동안 ‘이걸 평생 할 수 있을까?’를 테스트하기 위한 일종의 실험이었습니다. 실험이 실패했다고 생각하지는 않으나 실험 여건과 기간은 꽤 부족했던 것 같습니다. 여전히 문제해결의 효용과 즐거움을 믿기 때문에 인생이 힘들어진다고 사이트를 닫을 일은 없지만, 제가 의미있다고 생각하는 일을 계속하기 위해서 인생을 갖다가 다이나믹 프로그래밍을 돌리면 이 방향이 제일 옳을 것 같다고 생각해서, 아래와 같이 결정했습니다.

재(?)입사

내년 1월 6일부로 넥슨코리아에서 일하는 것으로 되었습니다. 알고리즘 하고 싶다는 이야기를 하다가 갑자기 게임회사가 나오는 게 좀 의아할 수 있지만 나름의 이유가 있습니다.

첫째로, 제가 가게 될 부서는 오는 1월에 신설되는 다소 실험적인 조직 ‘알고리즘연구팀’입니다. 이곳에서는 사내 코드의 최적화 업무를 할 예정이지만, 주 업무는 놀랍게도 알고리즘 대회 준비입니다.

두 번째로, 저는 넥슨의 사회공헌 사업인 넥슨청소년프로그래밍챌린지(NYPC)의 방향이 제가 솔브드를 만들면서 생각했던 비전과 많은 부분 일치한다고 생각하여, 엔진스튜디오를 퇴사하고도 계속 NYPC 사외에서 문제를 출제하고 자문을 해 왔습니다.

코딩 교육으로 한정하지 않더라도 넥슨의 사회공언 사업에는 진정성이 있다고 생각합니다. 자원과 관심과 의지가 있는 환경에서 제가 의미있다고 생각하는 일을 하는 것만큼 보람찬 것은 없을 겁니다. 물론 이제 회사로서의 솔브드는 정리해야겠지만, 솔브드가 지금 하고 있는 일들도 충분히 의미가 있기 때문에 솔브드가 사라지는 일은 없겠습니다. 개인이 취미로 (하지만 진지하게) 운영하는 사이트였을 때로 돌아갈 뿐입니다.

대회

알고리즘 대회를 진지하게 준비하기 시작한 이후 만들었던 버킷 리스트가 있습니다. 여러 번 이야기했던 것 같은데, ICPC 월드 파이널 진출, 코드 잼 라운드 3 진출, 그리고 SCPC(삼성전자 대학생 프로그래밍 대회) 수상이었습니다. 그중 월드 파이널은 2021년에, 코드 잼 라운드 3은 2022년에 이뤘습니다.

버킷 리스트의 마지막에 있었던 SCPC가 가장 쉬워야 할 터인데, 4번이나 본선에 진출할 동안 여태 상을 못 타다가 마지막 기회인 올해 드디어 수상에 성공했습니다.

그런데 졸업학기라서 그런지 소프트웨어멤버십 가입은 안 시켜 주더라고요. 아쉽습니다.

올해에는 ICPC 슈퍼리저널이 신설되었습니다. 그래서 2023-2024 시즌의 첫 슈퍼리저널인 2월 하노이 대회에 참가할 수 있었습니다. 대략 16등까지가 월드 파이널에 진출하는데, 37위로 그렇게 좋은 성적은 아니었습니다. 어려운 평면 그래프 문제를 평면 그래프의 특성을 사용하는 부분 빼고 풀어냈는데, 제대로 하나 배워가는 계기가 되었습니다.

2024-2025 시즌 ICPC 리저널은 서울과 요코하마를 나갈 계획이었는데, 요코하마가 장소 문제로 저희를 등록거부하면서 아쉽게도 서울에만 나가게 되었습니다. 5년만의 수상을 하고 내년 2월 싱가포르에서 열리는 슈퍼리저널 대회로 진출하게 되었습니다. 학교 순위에서 1위를 못 한 건 처음인데, 아쉽기도 하지만 제가 너무 오래 해먹은 것도 맞기 때문에 이제 갈 때가 된 것 같습니다.

돌아보니 관광으로 방문한 지역보다 ICPC에 나가기 위해 방문한 지역이 더 많아진 것 같습니다. 태국, 러시아, 인도네시아, 카자흐스탄, 싱가포르가 있네요.

이외에 UCPC는 팀 ‘개척단 훈련소’로 나가서 4등을 하고 왔는데, B번을 고민하던 기억 말고는 없습니다. 즐겜모드로 나갔으나 저 외의 팀원들이 코드포스 최고 레이팅이 무려 2957과 3042였기 때문에…

취미

shiftpsh.com 사이트를 리뉴얼했습니다. 예전 버전은 shiftpsh.com/2021애서 보실 수 있습니다. 디자인을 훨씬 깔끔하게 만들면서도 더 많은 내용을 넣을 수 있도록 했습니다. 한별이 갤러리도 만들었어요!

2021년도 사이트까지는 제가 2017년에 만들어 뒀던 개인 AWS EC2에다가 FTP 접속해서 pull 받고 빌드 돌리고 그랬는데, 지금은 static generation을 하고 S3에서 호스팅합니다. 소스 코드가 GitHub에 올라와 있습니다. 내년에는 영어 지원을 해 보고 싶네요.

1월에는 작탁을 사서 친구들과 심심할 때마다 마작을 칠 수 있게 되었습니다. 그전에도 마작패는 있었는데, 자동으로 패를 섞는 것의 장점을 실감하게 될 뿐이었습니다.

작탁이 있으니 아카도라와 점봉 같은 걸 추가 구매해서 커스텀 룰도 할 수 있습니다. 가령 5삭/5통 전부 적도라에다가 시로폿치도 있는 3인 마작 같은 걸 할 수 있습니다.

올해로 오락실에 다닌 지 10년째가 됩니다. 10년 중 3년은 유비트를 열심히 했고, 3년은 사볼을 열심히 했고, 최근 4년은 마이마이를 하고 있습니다. DX+ 버전부터 열심히 하기 시작했던 셈이네요. 작년은 레이팅 15545로 마감했는데, 올해는 갑자기 16000을 달성했습니다.

또 예전에 유비트 성과 관리 앱 ‘유비트북’을 만들었던 경험을 살려 마이마이 성과 관리 사이트를 만들기도 했습니다. 제가 필요로 했던 기능들을 잔뜩 넣었더니 참 쓰기 좋은 사이트가 나왔습니다.

츄니즘도 무지개를 달성해서 쌍무지개가 되었습니다. 마이마이 쪽 무지개는 슈퍼 무지개인 것 같기는 한데요.

사볼에 대한 열정은 여전하지 않지만 애정은 여전합니다. 니아·노아 생일 카페의 디자인을 맡았습니다.

여행

2월에는 ICPC를 위해 베트남 하노이에 다녀왔습니다.

베트남이면 동남아시아 국가인데 북쪽이라 그런지 기온이 16도쯤을 유지하고 있어서 꽤나 쾌적했습니다. 롯데호텔에 묵었는데, 1층에 롯데리아와 롯데마크, 그리고 인생네컷이 있어서 잠실인가 싶었습니다.

하노이 탑은 못 봤지만 대신 탑 오브 하노이라는 바를 갔다 왔습니다.

하노이에서 돌아올 때 다낭에서 환승했는데, 마치 한국에 온 것 같았습니다. 세상에 어떤 국제공항이 한국으로 가는 비행기편만 필터해서 보여주는 곳이 있을까요? 정말 신기한 곳이었습니다.

5월에는 일본 후쿠오카에 다녀왔습니다. 순전히 온게키를 하러 가기 위한 여행이었습니다. 그래서 온게키는 재미있었느냐 하면 너무 재미가 있어서 20만원쯤 쓰고 왔던 것 같습니다…

리듬게임에 20만원을 쓸 수 있는 이유는 당연하게도 카드 가챠 시스템이 있어서입니다. 마이마이에 20만원 쓰려면 한 세월 걸리지만 온게키는 10분정도면 할 수 있습니다.

9월에는 ICPC 월드 파이널 발표자로 초청받아서 예정에 없던 카자흐스탄 여행을 떠났습니다. 보통 가는 알마티가 아니라 아스타나였는데, 건물이 큼직큼직한데도 광활해서 놀랐던 기억이 있습니다.

숙소와 비행기 값은 ICPC 재단에서 내 주셨습니다. 감사합니다.

‘ICPC Staff’가 새겨진 티셔츠도 받았습니다. 엄청난 레어템인데 한 번 세탁했더니 글자가 갈라져서 무서워서 못 입고 있습니다. 대신 참가자들에게는 티셔츠를 세 벌씩이나 주기 때문에 같이 간 카이스트 팀 티셔츠 뺏어서 입고 다닙니다.

여기에 마작 세트를 들고 갔더니 마작에 대한 깊은 이해가 있는 일본 참가자들과 국제교류를 이룰 수 있었습니다.

월드 파이널에서도 어김없이 그사건이 일어납니다.

타바스코보다 큰 한별이도 있습니다.

시국

시위도 나갔습니다. 아니 집 앞 바에서 할 거 하고 있는데 갑자기 지인이 와서 계엄령이 났다고 하길래 취한 줄 알았습니다. 지금도 황당합니다. 어쩌다 이런 말도 안 되는 일들이 일어난 걸까요…

탄핵 정국은 현재진행형입니다. 정치는 나의 삶과 지극히 관련이 있다는 걸 한 번 더 체감하게 되는 계기가 되고 있습니다. 대선이 머지않아 있을 것 같은 느낌인데, 이번 일은 잊지 않고 앞으로 계속해서 잘 뽑아야겠습니다.

모닥불을 나서며

올해도 참 힘든 해였습니다. 그렇지만 꽤 멋지고 보람있게 보낸 것 같습니다.

솔브드의 결제대행사 사고는 불가항력적이었고, 이로 인해서 올해 하기로 마음먹었던 것들을 다 하지 못했던 건 아쉬운 일입니다. 회사로 돌아가기로 결정한 건 이런 일의 결과 중 하나지만, 오히려 먹고살 걱정이 해소되면 하고 싶은 일들을 하는 데에 더 집중할 수 있지 않을까 하는 기대도 있습니다.

당장 다음 주부터 회사에 출근하기는 하지만 아직 정비해야 할 것들은 많이 남아 있습니다. 이사를 어디로 가야 할지, 솔브드를 어떻게 정리해야 할지 같은 자잘한 것들도 있지만, 무엇보다 재작년과 작년을 정말 힘들게 보냈는데 잠시 휴식이 필요하겠습니다. 이번 연말은 별 하는 일 없이 요란하지 않게 보내고 있습니다. 새해에도 그렇게 좀 쉬다가, 1월 여행을 다녀오고 나서 본격적으로 모닥불을 나서서 현생을 견디러 나가고자 합니다.

회사를 가게 된다면 프론트엔드 엔지니어를 하러 가게 될 줄 알았는데 그렇지 않게 되었습니다. 하긴 ICPC 월드 파이널에서 발표를 할 줄 알았느냐고 한다면 그것도 모르는 일이었을 터입니다. 삶은 정말 모르는 일의 연속이다 싶습니다. 내년에는 어떤 일들이 저를 기다리고 있을지 기대가 됩니다.

올 한 해도 감사했습니다. 새해 복 많이 받으세요!

적당히 쉬엄쉬엄 풀어서 난이도에 비해 남은 시간이 다소 적습니다. 올해는 2번까지 풀지 않으면 Round 2를 가기 좀 힘들지 않을까 싶을 정도로 1, 2, 3번이 쉬웠습니다.

개인적인 난이도는 1 < 2 < 3 < 5 < 4번이었습니다.

1차 1번 – A보다 B가 좋아

길이 $N \le 300\,000$의 A와 B로만 이루어진 문자열이 있습니다. 이 문자열에서 길이 $2$ 이상의 어느 부분 문자열을 골라도 A의 개수보다 B의 개수가 크거나 같도록 하고 싶습니다. 원하는 위치에 B를 추가할 수 있다고 할 때 최소 몇 개를 추가해야 할까요?

작은 경우부터 생각해 봅시다.

길이 $2$인 부분 문자열은 AA인 경우만 피하면 됩니다.

길이 $3$인 부분 문자열은 AAA, AAB, ABA, BAA가 있는데, AA라는 부분 문자열을 어떻게 다 없앴다고 가정하면, ABA만 피하면 됩니다.

AA와 ABA를 어떻게 다 없앴다고 가정하면, 길이 $4$인 부분 문자열은 무조건 A의 개수보다 B의 개수가 크거나 같음을 알 수 있습니다.

이 성질이 길이 $5$ 이상에서도 성립하는지 알아봅시다. 귀납법을 사용할 수 있습니다.

• 길이 $K$의 문자열이 A로 끝나는 경우, AA와 ABA 패턴이 존재하지 않으므로, BBA로 끝나야 합니다. 따라서 이 경우 뒤에서 A와 B 한 글자씩 총 두 글자를 뗀 길이 $K-2$의 문자열에서 성질을 만족했다면, 길이 $K$의 문자열에서도 성질이 유지됩니다.

• 길이 $K$의 문자열이 B로 끝나는 경우, 길이 $K-1$의 문자열의 맨 뒤에 B를 하나 붙여 준다고 생각할 수 있습니다. 따라서 이 경우 길이 $K-1$의 문자열에서 성질을 만족했다면, 길이 $K$의 문자열에서도 성질이 유지됩니다.

따라서, A와 A 사이에 두 개 이상의 B가 있도록 추가해 주는 것으로 충분합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;
        string str;
        cin >> str;

        vector<int> idxs;
        for (int i = 0; i < n; i++) {
            if (str[i] == 'A') idxs.emplace_back(i);
        }

        int s = 0;
        for (int i = 0; i + 1 < idxs.size(); i++) {
            int d = idxs[i + 1] - idxs[i] - 1;
            s += max(0, 2 - d);
        }

        cout << "Case #" << _ << endl;
        cout << s << endl;
    }

    return 0;
}

1차 2번 – 배달

물건이 $N \le 300\,000$개 있습니다. $N$은 $4$의 배수입니다. 물건들에는 무게가 있습니다($1 \le \text{무게} \le 1\,500\,000$).

$4$개의 물건씩 골라 $N$개의 물건을 모두 배송할 예정입니다. 이 때, $4$개의 물건의 무게가 각각 $a \le b \le c \le d$라고 할 때,

원을 벌 수 있습니다. 모든 물건을 배달해서 벌 수 있는 최대 금액은 얼마일까요?

$a$, $b$, $c$, $d$의 대소가 이미 정해져 있으므로 절댓값 기호는 의미가 없습니다. 식을 정리합시다.

따라서 가장 무거운 하나와 가장 가벼운 하나만이 배송비에 관여한다는 사실을 알 수 있습니다.

가장 무거운 물건들의 합을 최대화하고, 가장 가벼운 물건들의 합을 최소화하는 방법은 가장 무거운 $N/4$개의 물건들을 $d$로 배정하고, 가장 가벼운 $N/4$개의 물건을 $a$로 배정하도록 하는 것입니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        int m = n / 4;
        ll s = 0;
        for (int i = 0; i < m; i++) s -= a[i];
        for (int i = 3 * m; i < n; i++) s += a[i];

        cout << "Case #" << _ << endl;
        cout << s * 2 << endl;
    }

    return 0;
}

1차 3번 – 보안망 점검

보안 장비 $N \le 300\,000$개가 있습니다. 이들은 총 $N+1$개의 라인으로 연결되어 있으며, 이 중 $N$개의 라인은 보안 장비 $N$개를 원형으로 연결하고 있으며, 나머지 $1$개의 라인은 원형으로 연결되어 있는 보안 장비들 중 두 개를 잇습니다. 이 때, 정확히 $2$개의 라인이 파괴되었을 때 망이 분리되는 경우의 수를 구해야 합니다.

다시 말하면, 보안 장비 그래프는 $3$개의 사이클로 되어 있으며, 가장 큰 사이클은 크기가 $N$입니다.

큰 사이클을 나누는 한 개의 간선은 degree가 $3$인 정점 두 개를 찾는 것으로 찾을 수 있습니다. 그 한 개의 간선을 기준으로 왼쪽과 오른쪽에 간선이 몇 개 있나 확인합니다. 각각 $l$개와 $r$개가 있다면, 그래프를 분할하는 경우의 수는

개임을 확인할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

ll solve() {
    int n;
    cin >> n;

    vector<vector<int>> graph(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 0; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
        deg[u]++, deg[v]++;
    }

    vector<int> deg3;

    for (int u = 1; u <= n; u++) {
        if (deg[u] == 3) {
            deg3.emplace_back(u);
        }
    }

    assert(deg3.size() == 2);

    int a = deg3[0], b = deg3[1];
    ll l1 = 0, l2 = 0;

    function<int(int, int)> dfs = [&](int u, int p) {
        if (u == b) return 0;
        for (int v: graph[u]) {
            if (v == p) continue;
            return dfs(v, u) + 1;
        }
    };

    bool skip_flag = false;
    for (int c: graph[a]) {
        if (c == b && !skip_flag) {
            skip_flag = true;
            continue;
        }
        if (l1) {
            l2 = 1 + dfs(c, a);
        } else {
            l1 = 1 + dfs(c, a);
        }
    }

    ll s = 0;
    s += (l1) * (l1 - 1) / 2;
    s += (l2) * (l2 - 1) / 2;

    return s;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {

        cout << "Case #" << _ << endl;
        cout << solve() << endl;
    }

    return 0;
}

1차 4번 – 딱 맞게

원소의 개수가 $5 \le N \le 100\,000$개인 두 중복 집합 $A$와 $B$가 있습니다.

여기에 일대일 대응 $F\left(A, B\right)$을 정의하여, 서로 대응하는 원소의 값의 차이의 절댓값들 중 가장 큰 값 $\max F\left(A, B\right)$를 계산할 수 있습니다. 이 값이 $1 \le L \le 10^9$보다 작으면서 가장 크게 되도록 해야 합니다. 이때 $\max F\left(A, B\right)$를 출력해야 합니다.

문제를 쉽게 써 봅시다. 배열 $A$와 $B$가 있어서, 이들의 순서를 잘 섞어서

을 $L$ 이하가 되게 하면서 최대화하라는 문제입니다.

$A$와 $B$를 각각 정렬하면 $\max F\left(A, B\right)$가 최소가 됩니다. 이 사실을 통해, $A$에서 적당한 한 개의 값 $a$와 $B$에서 적당한 한 개의 값 $b$를 골라 놓고, 나머지 원소들을 정렬해 놓는 방법을 사용할 수 있습니다. 이미 정렬된 $A$와 $B$에 대해서 $|A_i-B_i|$, $|A_{i+1}-B_i|$, $|A_i-B_{i+1}|$의 값들을 미리 계산하여 관리하고 있다면 적당한 $(a,b)$ 쌍에 대해 충분히 빠르게 계산할 수 있습니다.

$|a-b| \le L$인 모든 쌍을 보는 것만으로 문제를 해결하는 데에는 충분합니다. 더 나아가서, $a$가 정해져 있을 때, $|a-b|$의 값이 $L$ 이하이면서 가장 크도록 하는 $b$를 적당히 잘 골라 주고, 이런 $(a,b)$ 쌍들만을 보는 것만으로 충분함을 보일 수 있습니다.

아래 코드의 복잡도는 $\mathcal{O}\left(N \log N\right)$입니다. 제 소스 코드는 세그먼트 트리와 이분 탐색을 쓰지만 단조성을 이용한 투 포인터 등의 방법으로 시간을 더 줄일 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

ll a[100010], b[100010];

ll p[400010], pa[400010], pb[400010];

void update(ll *tree, int x, int s, int e, int i, ll v) {
    if (s == e) {
        tree[x] = v;
        return;
    }
    int m = (s + e) / 2;
    if (i <= m) update(tree, x * 2, s, m, i, v);
    else update(tree, x * 2 + 1, m + 1, e, i, v);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll query(ll *tree, int x, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return tree[x];
    int m = (s + e) / 2;
    return max(query(tree, x * 2, s, m, l, r), query(tree, x * 2 + 1, m + 1, e, l, r));
}

void update_p(int i, ll v) {
    update(p, 1, 1, 100000, i, v);
}

void update_pa(int i, ll v) {
    update(pa, 1, 1, 100000, i, v);
}

void update_pb(int i, ll v) {
    update(pb, 1, 1, 100000, i, v);
}

ll query_p(int l, int r) {
    if (l > r) return 0;
    return query(p, 1, 1, 100000, l, r);
}

ll query_pa(int l, int r) {
    if (l > r) return 0;
    return query(pa, 1, 1, 100000, l, r);
}

ll query_pb(int l, int r) {
    if (l > r) return 0;
    return query(pb, 1, 1, 100000, l, r);
}

ll solve() {
    ll n, l;
    cin >> n >> l;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    for (int i = 1; i <= n; i++) update_p(i, abs(a[i] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pa(i, abs(a[i + 1] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pb(i, abs(a[i] - b[i + 1]));

    ll ans = -1;

    for (int ai = 1; ai <= n; ai++) {
        for (ll x: {a[ai] - l, a[ai] + l}) {
            int biv = lower_bound(b + 1, b + 1 + n, x) - b;
            for (int bi: {biv - 1, biv}) {
                if (bi < 1 || bi > n) continue;

                // move ai and bi to the end; calculate max abs diff of the rest
                ll mx = abs(a[ai] - b[bi]);
                mx = max(mx, query_p(0, min(ai, bi) - 1));
                if (ai > bi) {
                    mx = max(mx, query_pb(bi, ai - 1));
                } else {
                    mx = max(mx, query_pa(ai, bi - 1));
                }
                mx = max(mx, query_p(max(ai, bi) + 1, n));

                if (mx <= l) ans = max(ans, mx);
            }
        }
    }

    return ans;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        cout << solve() << endl;
    }

    return 0;
}

1차 5번 – 스퀘어

배열에서 $2$ 이상의 정수 $k$를 정해서, $k$개의 $k$를 $1$개의 $k^2$로 바꾸는 작업을 ‘스퀘어’라고 정의합시다. 예를 들어,

과 같이 스퀘어 연산을 수행할 수 있습니다.

크기 $N \le 50\,000$의 배열이 있습니다. 각 원소는 $1$ 이상 $10^9$ 이하입니다. $Q \le 50\,000$개의 쿼리를 처리해야 합니다.

• $l$ $r$: 배열 $a_l$, $a_{l+1}$, $\cdots$, $a_r$에서 가능한 ‘스퀘어’의 최대 횟수를 구하여 출력한다.

배열에서 $2$ 미만 및 $50\,000$ 초과인 원소들은 무시해도 된다는 사실과, ‘스퀘어’ 연산의 연쇄 반응은 최대 $4$번까지만 일어난다는 사실을 생각해 봅시다. 세그먼트 트리로는 어떻게 풀어야 될지 감이 잘 안 잡히지만, Mo’s는 사용하기 좋아 보입니다. 아래 코드의 시간 복잡도는 $\mathcal{O}\left(N + Q \log Q + Q \sqrt{N} \log \log N \right)$입니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int m = 240;
int a[50001], cnt[50001];
ll ans[50000];

struct query {
    int l, r, i;

    query() : l(0), r(0), i(0) {}

    query(int l, int r, int i) : l(l), r(r), i(i) {}

    bool operator<(const query &rhs) const {
        return pii(l / m, r) < pii(rhs.l / m, rhs.r);
    }
};

void init(ll &val) {
    for (int x = 2; x <= 50000; x++) {
        int t = x * x;
        if (2 <= t && t <= 50000) {
            cnt[t] += cnt[x] / x;
        }
        val += cnt[x] / x;
    }
}

void add(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]++;
        if (cnt[x] % x) return;
        val++;
        x *= x;
    }
}

void remove(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]--;
        if ((cnt[x] + 1) % x) return;
        val--;
        x *= x;
    }
}

// sqrt 50 000 < 224
// sqrt sqrt 50 000 < 15
// sqrt sqrt sqrt 50 000 < 4
// sqrt sqrt sqrt sqrt 50 000 < 2

void solve() {
    int n;
    cin >> n;

    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= n; i++) cin >> a[i];

    int q;
    cin >> q;

    vector<query> qry(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qry[i] = query(l, r, i);
    }
    sort(qry.begin(), qry.end());

    ll val = 0;
    int l = qry[0].l, r = qry[0].r;
    for (int i = l; i <= r; i++) {
        if (2 <= a[i] && a[i] <= 50000) cnt[a[i]]++;
    }
    init(val);
    ans[qry[0].i] = val;

    for (int i = 1; i < q; i++) {
        while (l < qry[i].l) remove(val, a[l++]);
        while (l > qry[i].l) add(val, a[--l]);
        while (r > qry[i].r) remove(val, a[r--]);
        while (r < qry[i].r) add(val, a[++r]);
        ans[qry[i].i] = val;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << '\n';
        solve();
    }

    return 0;
}