cyan- 23학번, 유일한 "ps러"(= 문제가풀릴때도파민을느끼며 ps하다가과제레이트를한적있고 코드포스티어정병이라는개념을이해함), 코포계정생성9개월차, 레이팅 1400, 2주 전 serin이못풀었던 딥2 D 컨스를 풀고서주변의 기대를 한몸에받고있던상태(왜그랬지풀지말걸), azber라는 분이랑 무슨 사이인지는잘모르겟는데 밤에 디코로 영통하면서 그림판으로 문제풀이를 듣는다는 소문이있음...
놀랍게도 백준이 없어지기 전에 팀연습도 했다. 2번의 팀연습을 한 결과로 알게 된 건 골드를 다 풀고 내가 플레하위를 진짜 운좋게풀면 초고점이고 대충 머릿속으로 골드2 이하를 다 푸는 걸 목표로하자고 생각햇따. 그러나 정말 무서운 사실을 깨달았는데 팀연습 때 대학 대회 특성상 자주 등장하는 실버~골드하위의 게임이론과 컨스를 그 누구도 좋아하지않아서 결국 전부 다 내가 짬처리를 했고 같이 고민하도록 시켜보기도 했는데 결국엔 내가 풀었다(아무래도 코테에 잘 나오진 않긴 하죠). 개인적으로 스스로의 직관력이 쓰레기라고 생각하는데 그래도 내가 세 명 중에는 코드포스A,B를 가장많이풀어봤을것같긴해서어쩔수없다.... 또한 앞서 말했듯 내가 팀 내의 유일한 ps 경력자이기 때문에 웬만해서는 내가 버스를 운전해야 할 그림이었기 때문에 부담이 더 컸던 것 같다.
그래서 전날밤에 호달달 떨면서 최악의 시나리오를 상상한다.
lyj가 구현에서 절어서 디버깅하느라 한참을 헤맴, 그래서 내가 디버깅 도와주느라 다른문제들을 보지 못함,cyan이 긴장해서 뇌가굳어서 풀어야하는 쉬운컨스에서 아무런관찰도하지못하고 멘탈이터짐, 3시간쯤 지나서 드디어 fixed가 문제를 풀었는데 키보드를 뺏어오지 못해서 브론즈 두개 실버 하나 골드 한개 정도 풀고 끝나는 시나리오
근데곧알아보겠지만 정말이게거의 그대로 일어났다....
대회 전
대회가 시작하기에 앞서 각자 팀노트를 뽑아오기로 했다. 포스캣 동방 프린터의 사용 방법을 아는 사람이 나밖에없어서 보내주시면 뽑아주겠다고 했는데, fixed가 보내준 파일을 열어봤더니 다크모드로 되어 있어서 악플을 좀 달았다. 심지어 파이썬이야
이건 좀 아니잖아
각자 뽑은 팀노트는 '팀'노트라고 불러도되는지에 대해 깊생을 하다 보니 과방 안마의자에서 잠들었다. 그래서 헐레벌떡 제일 늦게 왔더니 친절하게 컴퓨터 앞 자리를 비워주셨길래 강제로 스타트를 끊게 되었다. 할 게 없어서 한컴타자연습을 하면서 긴장을 풀었다.
그리고 팀노트를 합쳐보니 25장 제한인데 26장이길래 잠시 소동이 있었는데, fixed가 표지를 버리면서 해결했다.
대회 중
대회를 망한 후에 정병이 와서 슼보 사진을 찍어두지 않았다. 따라서 대략적인 타임라인이다.
그리고 오픈콘 전에 슼보가 노출되어버려서 순서를 섞었다는데 이 후기는 오픈콘 전에 쓰여졌기 때문에 본대회 기준 번호임. 내가 주석으로 오픈콘 기준 번호도 적어뒀으니 참고바람
~0:10 A AC (+2)
일단 무지성으로 종이 더미를 반으로 갈라서 왼쪽에 있는 lyj에게 앞쪽 절반, 오른쪽에 있는 fixed에게 뒤쪽 절반을 던져주고 나는 템플릿을 짰다. 그리고 포스캣 사람들로 구성된 2퍼플 1블루팀, 1블루 1민트팀이 1,2등으로 유력한 상태여서 그 팀 위주로 보면 될 것이라 생각했다
lyj가 A번이 쉬워보인다고 던져주길래 봤더니 브론즈였고, 내가 풀었는데 너무 긴장해서 등호를 빼먹어서 틀린다. 그래서 어 뭐지...? 하고 lyj를 불러서 도와달라 해서 고쳤는데 또 틀려서 2WA를 받는 사건이 일어나버린다. (사실 여기서부터 말아먹었음을 직감했다) 다행히 고쳐서 맞았다.
이후 cyan은 C, D, lyj는 B? C? E? (사실 모르겠음), fixed는 I를 본다. 근데 I (=오와 열)는 개레전드로 어려운 문제였기 때문에 아무런 성과도 이루어지지 않았고 B (=Classical postech problem, cpppp 나오는 거) 우리 기준 어려운문제였다...
일단 C (=POSTECH Programming Colosseum, 오픈콘 H) 트리라는 단어를 읽고 격자 bfs인가...? 하고 머리가 복잡해져서 그냥 넘겼던 것 같고 (좀만더자세히읽을걸) D (=부분수열의 개수, 오픈콘 J) 이상한 DP로 풀어보려다가 개삽질을 했다. 사실 일반적인 상태의 나
관찰 1. N범위를 보고 O(N log N)까지 돌 테니까 일단 정렬ㄱ?
관찰 2. 그러면 이웃한 것들의 관계를 어쩌고 저쩌고
정도의 사고는 가능했겠으나 이미 A를 두 번 틀리고 정신이 나가버렸다. so very classic Div2 B material로 느껴지는데 이걸 왜 못했지... 1시간이 지나도록 아무 성과도 없는데 막 3솔한 팀들도 많아서 정병이 왔다.
~1:00 J AC (=포스텍 도수체조, 오픈콘 K)
그러다가 J가 풀리고 있는 것 같은데 너무 고능해서 잘 모르겠다고 (보통 팀원들이 컨스 나한테 던질 때 쓰는 템플런임) fixed가 던져줬고 예제에 있는
1 5
5 7
을 보고 역시 kwoncycle 선배님 이라고 생각했다.
보자마자 3분만에 J가 90% 정도 풀리는 관찰을 찾았다고 주장하며 캬역시나야 하면서 짜기 전에 팀원들에게 검증을 받으려고 했는데 설명하다 보니 내가 틀렸다는 걸 깨닫고 머쓱해졌다. 그래서 15?분 정도 더 관찰한 결과
관찰 1. 도미노를 만들 수만 있으면 무한복사가능
관찰 2. 대각선은 서로에게 닿을수없어...
생각 2-1. 이걸 어떻게 수식화하지? 택시거리가 홀수이면 닿을수있다
생각 2-2. 그러면 인덱스의 차이로 아하
로 풀이가 나왔고 구현도 내가 구체화했다. fixed랑 같이 화면을 보며 불안형 여친마냥 나 맞지? 이거 맞겠지?하며 검증하면서 짜서 AC.
~2:00
lyj가 옆에서 C(=오픈콘 H)는 달팽이 배열을 짜면 된다고 외쳤는데, 항상 2개인 경우만 되는지 확실하지 않아서 증명해야 할 것 같다면서 구현을 시작하지 못한 상태였다. 그러다가 일단 해 보겠다고 해서 키보드를 줘서 짜기 시작했는데 45분 넘게 못 짜고 헤맸다. 원래 멘탈이 터진 cyan에게 괜찮다는 말을 해주던 lyj가 멘탈이 완전히 터져버렸다. 그래서 내가 역으로 괜찮으니까 제발 멘탈 잡아달라고 하는 사태가 일어나버림
뭔가 이대로 뒀다가는 망할 것 같았고 C는 거의 모든 팀이 풀었기 때문에 내가 나서서 책임져야겠다고 생각했다. 나는 구현을 정말 정말 못하지만 그래도 고등학교 내신에서 달팽이 배열을 짜 본 적은 있었고, 다른 팀들도 다 풀었는데 내가 못할 게 뭐야? 라는 근거 없는 믿음이 있었다. 하지만 단순한 달팽이가 아니었고 따져야 할 조건들이 너무 많았다. 처음부터 lyj의 설명을 듣고 난 상태였어서 다른 모양을 떠올릴 생각조차 못했고 여기서 C를 다시 읽어보려는 시도라도 했더라면 좋았을 텐데 못해서 너무 아쉽다. 사실 모두가 풀었다는 말은 더 쉬운 풀이가 있다는 뜻이었을 거라는 오만한 생각이라도 했을걸....
대충 이 상황과 병렬적으로 fixed는 E(=포닉스의 학점은?, 오픈콘 D) 가 쉬운 것 같다면서 (실제로 거의 모든 팀이 풀었었음) 그냥 비교하면 되는 거 아님? 이라고 했는데 예제2가 왜 도는지 모르겠다고 나를 불렀다. 근데 일단 뭐가 수식이 너무 많고 지문도 너무 길고 비직관적이고 정말 읽기 싫게 생긴 문제였다. 예제를 읽고 설명시켜주는 데에는 성공했으나 뭘 하라는 건지 모르겠어서 멍을 좀 때렸다.
결국 E는 버리고, 내가 쉬지 않고 반례를 던지고 디버깅을 도와줘서 문제의 조건에 맞는 달팽이를 제대로 출력하는 데에 성공했다. 그런데도 WA를 받았다. 가능한 모든 상황에 대한 예제가 다 돌았고 이유를 전혀 알 수 없었다. lyj는 '답이 2개가 아닐 수 있나?'에 다시 빠져버렸고, fixed도 망했어요... 하면서 간헐적으로 멍을 때리기 시작했다.
그래도 lyj와 fixed가 힘을 합쳐서 E를 맞게 된다. 나는 지금도 문제 상황을 모르겠다.for, if, 부등호만으로 해결할 수 있는 브론즈라는데아직도 문제를 이해하지 못했다.진짜 저능해졌나??
이 쯤에서 내가 인터랙티브였던 H(=Classical Interactive Problem, 오픈콘 C)도 풀어보려고 시도했다. 사실 살면서 인터랙티브를 한 번도 풀어본 적은 없었지만, 예비소집 때 인터랙티브를 푸는 방법을 배웠고, (그냥 endl만 붙여주면 된다고 했다) 많이 어려워보이지 않아서 해 보려고 했다.
생각 1. 쿼리가 최대 2N개니까, N+N으로 구성해보자. 일단 차이 N개를 구하고...?
생각 2. 3개씩 해볼까? 그러면 대소관계를 알 수 있네?
근데 너무 저능했던 나머지 이것만으로 확정이 된다는 생각을 못 해서 빙글빙글 돌기만 했다.
~3:00 C AC (=오픈콘 H)
이제 뭘 풀지...? 하고 돔저지에 다시 들어가봤다. 근데 클릭을 잘못해서 C의 WA 결과를 눌렀는데 warning:무슨뭐가 초기화가 안됐을수있음 이라고 떴다. 알고 보니 로컬에서 돌릴 때는 어떤 변수가 쓰레기값으로 초기화가 되었는데 채점기에서는 0으로 초기화가 돼서 틀린 거였다. 그래서 C에서 AC를 받았다.
30분 남은 시점에서 F (=학교를 쌓아올리는 포닉스, 오픈콘 E)를 봤는데 대충 아주 간단한 투포인터 문제로 보였다. 그 전에 그 문제 자체를 왜 못 봤는지 모르겠다. 다른 사람이 들고 있던 건가....? 이미 충분히 많은 팀들이 풀었는데, 사실 나도 멘탈이 나가서 슼보를 보고 남들이 푼 걸 풀어야겠다는 생각 자체도 못했던 것 같다. 내가 키보드를 잡은 상태에서 다 같이 F를 보기로 했는데, fixed가 멘탈이 나가 있을 동안 lyj랑 내가 병렬적으로 짰던 것 같은데 결국 둘 다 풀이를 못 냈다. 근데 사실 나도 건물 높이 1을 쌓는 것을 width번의 작업을 해야하는 걸로 생각하고 막 누적합을 짜네 마네 하고 있었는데 그 누구도 틀렸다고 지적을 하지 못한 것을 보면 다 같이 멘탈이 나갔던 것 같다. 내가 5분 정도를 남기고 구현 방향이 잘못되었음을 깨닫고 나중에 풀었던 정해에 가까운 풀이 방향을 떠올렸는데 (포인터 방향을 거꾸로 해서 바이토닉하게 만드는 것) 시간 내에 구현을 구체화할 수 없을 것 같아 결국 키보드를 내려놓았다.
결과
특별상을 받아서 총 30만원을 받는 데 성공했다! 시작 전에 긴장 풀기용 농담으로 X염색체의 수가 가장 많은 팀으로 기준을 정하면 상을 받을 수 있다고 주장했었는데 이건 아니었고 개삽질한 후에 AC를 받았던 C가 특정 제출 시간에 가장 근접했다고 한다.
순위 자체는 12/14등을 했다. (12/13등이었나?) 당연히 3등상은 받을 거라고 많은 사람들이 말했어서 이 정도의 성적을 받을 줄은 몰랐고 솔직히 너무 부끄러워서 숨고 싶었다. 그래서 특별상을 받았을 때도 사실 그냥 막 포닉스 굿즈. 시프트업 굿즈. 이런 거 줄 줄 알고 정말 앞에 나가고 싶지 않았는데 옆에서 누군가가 상금 인당 10만원이라고 알려줘서 개놀라고 '혹시 수상소감도 말해야 하나요?'라고 말했음 어이엑스
대회 이후
대회가 끝나자마자 티스토리에 올릴 후기의 일부를 작성했다. 아래는 그 내용의 일부이다.
사실 내가 읽은 모든 문제들은 실제로 내가 풀이에 아주 근접했고 충분히 풀었어야 하는 난이도였는데 하나도 못 풀었다는 생각에 많은 자괴감이 들었다.
일단 대충 은퇴선언을 박고 양꼬치를 먹으러 갔다. 1,2등 팀이 우리 테이블에 앉았는데, B번이 어쩌네 L번이 정해가 뭐냬 하는 동안 나는 멍 때리면서 소주를 들이켰고 주량에 근접한 양을 마셨다. 이 때 후배들에게 빙홍차 소주 칵테일을 말아주고 '살면서 자기가 먹어본 소주 화합물 중 가장 소주 맛이 안 난다' 라는 극찬을 들었음 칵테일 동아리 3년 경력이 괜히 있는 게 아님
그러고 나서는 잔뜩 취해서 그 날 저녁에 있던 Div.2 코드포스를 친다는 후배들한테 나도 할까 같은 헛소리를 조금 했는데 내가 맛이 좀 많이 가 보였는지 괜히 레이팅 떨구지 말고 들어가시라는 소리를 들었다... (꼬장 부리는 선배라 미안해)
근데 방에 가기 싫어서 과방ㄱㄱ을했다 돔저지가 아직 닫혀 있지 않은 상태였기 때문에 제출이 가능했다. 일단 구현하다 말았던 F번(학교를 쌓아올리는 포닉스)을 짰다. 그 다음은 D번(부분수열의 개수)을 들여다봤는데, 슬슬 술이 깨면서 숙취에 대가리가 깨질 것 같았는데 난 이것도 못 할만큼 멍청하지 않아! 하고 눈이 감길 때마다 스스로의 대가리를 풀스윙으로 때렸고 과방에 모르는 사람도 있었는데 진짜 미친줄알았을거다 20분도 지나지 않아 정렬한 후 upper_bound로 2배 이하인 첫 번째 지점을 찾는 아이디어를 떠올려서 구현까지 마쳤다. 다음은 인터랙티브 H번도 봤는데, 이것도 차분하게 생각해보면 대소관계가 결정되면 수열이 결정된다는 걸 알 수 있었다. 사실 그 때 a, n+1-a가 둘 다 된다는 조건을 읽지 않았거나 이걸 어떻게 쓸지 몰랐던 것 같다.
이 때 정말 여러 가지 감정이 교차했는데, 아니 걍 만취에 가까운 상태에서 사실상 D, F, H를 혼자서 다 푼 건데 불과 몇 시간 전이었던 대회 때 맨정신으로 이걸 떠올리지 못했다는 게 어이가 없었고 동시에 '나는 대회를 망친 것 뿐이지 ps 자체를 개못하는 건 아니구나' 라는 안도감도 들었음 아직 접을 때는 아니구나... 그래 아무리 민트를 뽀록으로 찍었대도 이 정도는 아니야
여튼 그래서 접겠다는 주장을 철회하고 달콤한 잠에 들었다💤
팀원 회식
처음으로 돌아가 보자. PPC를 나간 것은 동아리 부원들과의 친목 목적이 가장 컸고 (여담이지만 PPC 작년 2등, 올해 1등을 한 chansolpark7이 팀이 없다고 같이 나가자는 제안을 받았었는데 이미 팀이 있어서 거절했다.) 실제로도 내가 친해지고 싶던 사람들과 편해진 것 같아서 기분이 좋았다. 그래서 특별상도 받았겠다 마지막으로 회식을 했다!
웰노운 연어 맛집
lyj: 백준 부활하면 연락ㄱㄱ 코테 준비할 때 필요함
fixed: 역시 ps는 재미없다. 가서 선배님들 문제 푸는 거 구경하는 게 멋있었다.
또 나만 ps에 진심이었지
하지만 재밌었죠 <3
마무리
역시 온사이트 대회는 정말 재밌는 것 같다. 코드포스라는 티어가 걸려 있고 시간 내에 문제를 풀어야 하는 환경을 경험해봤기 때문에, 대회도 마찬가지일 것이라고 생각했는데 팀 대회라 그런지, 제일 큰 대회여서 그런지, 부담감이 차원이 다르다...
마지막으로 우리 팀원 미소녀(fixed)와 운영진 미소녀(kyungdain)의 사진을 첨부하며 마무리한다. 이번에 정말 백준 섭종도 그렇고 여러모로 운영진 입장에서 진행하기 어려웠을텐데 대회가 성공적으로 끝나서 다행인 것 같고 정말 수고 많았다고 해 주고 싶다.
잠이 안 오는 새벽 세 시 반이다. 정수론 과제 소문제 하나에 1시간 반을 매달렸지만 결국 반쯤 이해한 채로 gpt의 풀이를 베껴서 내고, 인간관계에 대한 깊생도 들고, 해석학 시험은 얼마 남지 않았고, 최근 교내 ps대회도 말아먹고서 생각이 많아진 그런 날이라고 할까.
침대에서 뒹굴거리며 핸드폰을 들여다봤고, 2020년부터 사용했던 내 트위터 계정을 구경하며 나름의 추억팔이를 하다 '학교에서 수행평가로 나왔던 확통 문제인데 어떻게 푸는지 잘 모르겠다'는 내 질문글을 보게 되었다. 필자는 인과영 확통 내신에서 B-(석차로 따지면 9등급제 기준 8등급 정도)를 받았다. 중학교 2학년 때 잠시 중등 KMO를 준비할 때도 조합론 문제는 단 한 개도 맞추지 못했다. 조합론은 근사(not approximation yes cool)하고 재밌지만 묘하게 재능을 타며, 아쉽게도 나에게는 그 재능이 없다.
당시 설컴을 다니고 경곽 같은 데 다니던 멋진 트친 분들이 답장을 해 주신 걸 구경하는데 꽤나 흥미로웠다. 근데 읽다가 되게 많이 나오는 DP 문제 아님? 이라는 생각이 들었다. 그래서 풀어봤는데 이게 맞네?
일단 문제가 대칭적이기 때문에 첫 번째를 1로 고정하고 나중에 4를 곱할 것이다. i번째에 고른 수가 처음에 고정한 수와..
A[i]: 같은 경우 (ex. 1)
B[i]: 반대인 경우 (ex. -1)
C[i]: 상관없는 경우 (ex. i, -i)
그러면 점화식을 세울 수 있는데
A[i+1] = A[i]+C[i]
B[i+1] = B[i]+C[i]
C[i+1] = 2*A[i]+2*B[i]+C[i]
초깃값은 A[0]=1, B[0]=C[0]=0이다.
마지막도 반대이면 안 된다. 따라서 4*(A[n-1]+C[n-1])이 답이 된다.
여기에 식을 구하고 싶다면 A[i]+B[i]+C[i]=3^i (임의의 순간에 길이 i+1의 sequence를 만드는 방법은 직전 꺼를 제외한 나머지 3개이고 시작은 3^0=1이다)을 이용해서 식정리를 해주면 된다. 점화식을 풀면 길이 n에 대해 3^n+(-1)^n+2 라는 closed form을 얻을 수 있다. 악필이라 ㅈㅅ
고등학생 때의 내가 못 풀어서 결국 풀이를 외워버렸던 확통 문제를, 대학생이 되어 알고리즘 문제풀이를 시작하고 DP 문제로 바꿔서 풀어냈다는 점에서 스스로의 발전이 뿌듯하게 느껴졌다. ps가 절대적인 발상력을 높여주는 건 아니지만 가능한 발상의 폭을 넓혀주긴 하는 것 같다. 대학교 와서 뭘 했지? 라는 생각을 아주 많이 했지만, 사실은 나도 모르게 조금씩 성장했을지도 모른다. (ㅈㅅ 제가 씹덕이라 성장, 결실 같은 키워드에 환장함)
+ LLM에게 풀이의 유효성을 검증받았더니 4-state graph에서 길이 n의 walk를 계산하는 문제로 환원할 수 있다고 해서 신기했다. 뭔진 잘 모르겠지만 만약 알고리즘에 대한 내 관심이 계속된다면 그래프의 성질도 공부해보면 재밌을 것 같다. (뭐든 쉽게 질리는 성격 탓에 그럴진 모르겠긴 함)
+ 백준에 동일한 문제가 있을까? 하고 검색해보려고 했는데 아 백준이 없어졌구나... 라는 걸 깨달았다.주변인들에게 물어봤더니 실버~골드하위 DP이고 식까지 구하는 건 골드 상위~플레 하위라는데 그럼 난 실버랑 골드를 풀고 신나서 블로그 글을 쓴 거구나(!) 좀 부끄러워졌을지도?
오늘은 제 인생 첫 PS 대회입니다. 기대 반 걱정 반 (기대 10% 걱정 90%)로 포항행 기차에 몸을 싣었습니다.
이하 잡설이 많습니다. 또한 POSTECH 참가자들끼리 뒷풀이를 진행하며 음주 상태로 작성되고 있으며 퇴고를 거치지 않았기 때문에 문장 coherence가 부족할 수 있는데 틀린 내용이 있으면 알려주세요.
시작도 전부터 2가지 정도의 억까를 겪어버립니다!
1. 서울-포항 기차 없음 이슈로 8시 기차를 타야 해서 7시 반에 일어났습니다. 보통 3시 정도에 규칙적으로 자는 사람으로서, 7시 반 기상으로 인해 다소 피폐해져서 커피 두 잔과 박카스 한 잔을 도핑합니다.
2. 충전기를 본가에 놓고 왔습니다. UDPC를 치다 말고 컴퓨터가 꺼지면 어떡하지 같은 근들갑에 잠시 정신이 사로잡혔지만 에이 설마 3시간은 버티겠지 같은 생각으로 마음을 가다잡았습니다.
이건Div3코포다이건Div3코포다이건Div3코포다이건Div3코포다이건Div3코포다괜찮다긴장하지말자제발긴장ㄴㄴ 문제를 풀어 봅시다.
A (대회 장소 정하기)
(0:45 AC)
UDPC는 난이도순이라는 말을 분명하게 들었습니다. 나름 0917ba가 홍보할 때도 뉴비 친화적인 대회라는 이야기를 했었습니다. 그러니 아마 A번은 대충 브론즈 사칙연산이겠죠? 모든 재앙의 시작
음 뭔가 생각보단 케이스가 많을 지도 모르겠습니다. 대충 선을 일직선으로 편 후에 구간에 따라 나누면 될 것 같고, 위치에 따라 나눠서 하면 될 듯 합니다. 그러니까 min(거리, N-거리) 이런 쌍을 잔뜩 만들어서 케이스워크를 하면 될 것 같습니다. 문제는 그것을 어떻게 하느냐입니다. 이것은 능지를 요구하는 정신 나간 케웍 문제이며 저는 능지가 없습니다. 막 모든 케이스를 다 나눠서 하면 될 것 같은데 실수하면 끝장 아님? 내가 첫 ps 대회에서 0솔을 하면 어떡하지? 여기서부터 멘탈이 갈리기 시작합니다.
그나마 다행히도 멘탈이 덜 갈리게 된 점은, 15분이 경과했는데 아직까지 A를 푼 사람이 한 명(인가 두 명인가)밖에 없었습니다. 이 문제는 아무래도 A번 난이도가 아닌 것 같습니다. B로 넘어가 봅시다.
B (포닉스와 달구 2)
(+1 1:25 AC)
그래서 B를 읽기 시작합니다. 흐으음... B도 무슨 게임이론 construction처럼 생긴 문제입니다. 진짜 죽일까(not 출제진 yes 문제)? 그래도 A 같은 케이스워크를 하다가 이미 예제가 안 나오는 상태였던지라 이거라도 풀어야겠다는 생각이 들었습니다. 이걸 못 풀면 진짜 0솔을 할지도 모릅니다.
직관적으로 0...0 과 같이 대칭인 0의 쌍이 있으면 선공이 비대칭을 만들 수 있고, 1...0과 같이 비대칭이고 한 쪽을 채울 수 있는 게 있다면 이건 후공 입장에서 언젠가 해결해야 하는 숙제입니다. 그러나 원래 일퀘라는 건 하루에 하나만 할 수 있는 것이기에, 후공도 마찬가지로 이 숙제를 하나만 할 수 있습니다.
따라서 선공이 1...0 쌍을 항상 2개 이상으로 유지하면 무조건 이기..나? 이렇게 생각하고 코드를 짜봤는데 엥? 예제가 안 돌아요. 당연히 이렇게 간단할 리가 없습니다. 대충 이런 관찰을 몇 개 더 하면 풀리겠죠?
대칭이라는 건 홀짝성에 따라 가운데가 있을 수 있습니다. 가운데가 아직 채워져 있지 않은 경우는 뭔가 여분의 수?가 하나 생깁니다.
선공이 여기에다가 두면, 아무 일도 일어나지 않지만 후공이 복구할 0...0 쌍을 안 만드는? 효과가 있습니다. 근데 후공의 턴이 오지 않으면 승리한다고 합니다. 그 말은 1...0 쌍 <2 인 경우를 분리해서 생각해줘야한다는 건데, 1 이하인 경우 무조건 후공이 이긴다고 대충 생각하고 제출을 눌렀는데 WA.
안 되곘습니다. 저는 이런 고능한 게임이론 문제를 풀기에는 너무 저능합니다.
차라리 A는 가능한 모든 경우를 해 보면 될 것도 같으니 A로 다시 돌아가 봅시다. {시계, 반시계}, {ans, N-ans}를 나눠서 모든 경우의 min()해버리면 되지 않을까 같은 생각으로 케웍을 했고 다행히 예제가 돌아서(?) AC!
(주석: A번의 경우 나중에 뒷풀이에서 Equinox 군의 이야기를 들어보니까, n<=100이기 때문에 그냥 스트레스를 짜도 O(n^4)인데 간당간당하게 1초 안에 돈다고 합니다. 역시 ps 짬바가 있으면 이러한 발상도 가능한 듯)
휴! 이젠 B를 좀 풀어야겠습니다.
하루에 숙제를 두 개 이상 못한다는 이론을 일단 붙잡아보기로 했습니다. 이걸 좀 더 세분화하면 되지 않을까요?
근데 사실 두 개 이상이 아니라 세 개 이상일지도 모릅니다. 왜냐하면 [가운데를 채우기]라는 스트릭프리즈가 있기 때문이죠.
1...0 쌍이 3개 이상이면 절대 안 됩니다.
1...0 쌍이 없는 경우는 0...0 쌍이 있고 가운데가 비어 있으면 됩니다.
1...0 쌍이 한 개인 경우, 0...0 쌍이 없으면 후공 차례가 안 와서 선공이 이기게 됩니다. 0...0 쌍이 있으면 후공이 채우면 됩니다.
1..0 쌍이 두 개인 경우, 0...0 쌍이 없으면 후공이 대칭으로 항상 만들 수 있습니다. 대신 가운데가 비어 있으면 가운데를 채워서 턴을 벌 수가 있으므로 이 경우는 제외합니다.
직접 예제를 몇 개 만들어봤을 때 다 되는 것 같길래 믿음의 도약으로 제출을 눌렀고 AC를 받았습니다. 이 케이스워크를 하기에 너무 저능해서 좀 오래 걸렸습니다.
어케했지? 케웍이나 construction은 풀 때마다 내가 빼먹은 끔찍한 케이스가 있지 않을까 같은 불안감을 떨칠 수가 없는 것 같는데 이거 어떻게 해결하나요
C (U-DeeP-See)
(1:35 AC)
제 닉네임이 드디어 슼보에 보이기 시작합니다. 이 때부터 좆됐다는 생각이 좀 사라지면서 긴장이 풀리기 시작합니다.
C번도 construction입니다. 저는 ad-hoc, construction, greedy에 약하고 DP, graph에 강한데 (물론 골드 중하위의 문제 따위를 풀며 제가 이딴 소리를 하는 것도 좀 웃기긴 합니다.) 아직까지는 제가 못하는 것만 한가득입니다.
(주석: PS를 처음 시작한(?) 시점에서 반 년 정도 지났는데, 골드 이하의 문제를 보면 대략적인 태그가 예측 가능합니다. 고슈분들의 블로그를 보면 '이건 애드혹이니까 qwer에게 던지고 이건 자료구조 비빔밥 같으니까 asdf에게 던졌습니다' 같은 말들이 있어서 저도 태그를 안 상태에서 팀원에게 문제를 던지고 싶다는 생각을 자주 하는데, 문제는 저에겐 던질 팀원이 없으며 제가 풀 능력도 없으니 큰 의미는 없습니다.)
2d grid sum (있는 말인가?)는 근본적으로 convolution 이라는 생각이 들었습니다. 참고로 이 토픽은 2023 UDPC 셋을 돌 때도 나온 적 있는 토픽인데, 당시 ijkxyz의 늪에 빠져서 구현에 실패하고 나중에 업솔빙을 했었습니다.
다행히 UDPC는 인터넷 검색이 가능합니다! 바로 convolution 공식이라고 구글에 검색했는데 합성곱 컨볼루션이 먼저 뜹니다. 아니 CNN 컨볼루션 말하는 건데; 그리고 Google AI Search가 그 밑에 뜹니다. 이러다가는 생성형 AI 사용으로 실격을 당해버리면 슬플 것 같습니다.
아니 생각해보니까output kernel 공식은 이게 뭐 검색할 정도의 것도 아닌데 왜 검색했지?
빠르게 창을 닫았습니다.
홀수일 때는
-1
-1 +4 -1
-1
이런 격자를 만들면 되겠지? 그렇다면 짝수일 때는 일반화가 가능할까요?
아니 근데 그냥 각 n_output마다
-1 -1 -1 -1
1 1 1 1
이런 걸 하면 합은 보존되는 것 아님? 제출을 하고 빠르게 AC를 받습니다. 뭐지 나 construction 잘하나?
D (카드 섞기 게임)
(+1 1:59 AC)
a[i]를 s[a[i]]로 매핑하는 operation을 k번 했을 때 사전순으로 최소가 되는 문자열을 짜면 됩니다. 아니 난이도 순이라며 이게 A보다 쉬운 것 같은 건 기분 탓임? 제가 수학을 잘 못해서 이게 수학적으로 용어가 맞는진 모르겠는데, f^m(x)=x가 되는 주기 m이 있을 거고 k%m을 해서 원래 문자열의 합성을 O(n^2) 안에 구할 수 있습니다. a[i]를 s[a[i]]로 매핑하는 형태의 문제는 코드포스 같은 곳에서 많이 봤기에 거의 보자마자 짤 수 있었습니다.
그러나 예제조차 돌지 않는 맞왜틀의 저주에 빠져버리고 맙니다. 하아.... 아무리 봐도 제 코드에 틀린 게 없습니다.
혹시 s[a[i]]를 ans[a[i]]로 반대로 매핑했나?? 혹시 array 초기화를 잘못했나?하고 모든 프로토콜을 돌려봅니다. 이게 뭐 풀이가 복잡한 문제도 아니고 틀릴 리가 없습니다. 2차 멘탈 붕괴가 옵니다.
이 시점에서 스코어보드가 프리즈 됩니다. 이 시점에선 다행히 6등이었는데 10등까지 수상이니까 수상권 밖으로 밀려날 것 같다는 걱정이 들었습니다.
다음으로 풀 문제를 찾아야 합니다. E (풍선줄 자르기), G (송신탑 설치) 정도가 후보입니다. G번은 예전에 코포에서 봤던 문제인 것 같습니다. 그래서 규정에 따르면 이미 짠 코드를 사용할 수 있다고 했기 때문에 코포 제출 내역을 다 뒤져봤는데 그 문제가 보이지 않습니다. 뭐지 꿈에서 풀었나?
아니 다시 생각해보니까 D에서 처음에 매핑을 시작하기 전에 시작 string을 정렬을 했어야 되는데 안 했네요. D를 못 풀었다는 생각에 너무 답답했었는데 이걸 찾아냈다는 생각에 막 손이 떨렸고 수정 제출을 눌렀는데 너무 흥분한 나머지
1. E에다가 제출을 (두 번이나) 누르고,
2. 이걸 깨닫고 다시 D에다가 제출을 했는데 cout<<ans를 쓰지 않고 제출을 하는
블런더를 저질러서 E와 D에 WA를 하나씩 쌓는 레전드 사건이 일어납니다... 진짜 얼탱
E (풍선줄 자르기)
(+1 2:57 AC)
이제 시간이 약 20분 정도 남았습니다.
E를 자세히 읽어보니 그냥 흔한 경로 찾기 문제입니다. 남겨놓은 선의 길이의 최댓값을 구하는 문제로 생각하고 MST 문제라고 착각을 해 버리고 맙니다.... 그래서 일단 다급하게 제 union find 템플릿을 찾습니다. UDPC의 경우 어떤 팀노트도 사용 가능하고, 인터넷 검색도 자유롭지만, 코드를 복사를 하면 안 된다는 규정이 존재합니다. 그래서 이 순간부터 저는 인간 복사기가 되어 제 5nn타의 초스피드 영타로 템플릿을 치기 시작합니다.
근데 다시 읽어보니까 풍선의 높이들의 합의 최소를 구하는 거잖아? 아니 시1ㅂ 다익스트라잖아 ㅋㅋㅋ 다익스트라 템플릿을 찾습니다. 이 시점에서 시간이 10분 정도 남았습니다. 이제부턴 내가 과연 10분 안에 다익스트라 템플릿을 짤 수 있을까?에 대한 문제입니다. 정말 다행히도 딱히 변형할 게 없어서 그냥 그대로 쳤고
버저비터로 AC를 받을 수 있었습니다! 캬
손이 덜덜 떨리고 토할 것 같아서 끝나자마자 화장실로 달려갔는데 이렇게 손 떨리는 경험은 대학교 입시 이후로 처음이었습니다.
카페인 때문이었을까요 대회 때문이었을까요? 몰?루
결과: 5솔로 6등(4등상)을 받았습니다!
여담으로 슼보 깔 때 진행자가3x3x173은 얼마일까요? 계산을 해 보겠습니다 하고 계산기를 냅다 켜더니 1557입니다. 이래서 좀 웃겼음
후기
팀노트도 되고 인터넷 검색도 되기 때문에 사실상 코드포스 Div.3를 치는 기분이었는데 실전 대회라는 압박감이 엄청납니다. 사실 저는 평소에 B 같은 복잡한 게임이론 construction을 짧은 시간 안에 깔끔하게 잘 떠올리지 못하는데, 이걸 해냈다는 게 역대급 고점을 띄워서 기분이 좋습니다.
그리고 뭔가 난이도 순이라고 해도 내가 느끼는 난이도와 진짜 난이도는 다를 수도 있겠다고 생각했습니다. 저에게는 A가 너무 어려웠어서 이 때 멘탈이 나갈 뻔했는데, N 범위 보고 브루트포스 같이 말렸을 때 뚫을 만한 좋은 방법들도 생각해두면 좋을 듯?
