월간 향유회 8월 오프라인 대회 후기

 
월간 향유회가 오프라인으로 열린다길래 냉큼 신청해봤어요! ㅋㅋ
방학때 UCPC, SCPC, 앨리스 기타 등등 타 대회 많이 나가느라 바빴는데 다들 광탈해버리는 바람에 ㅜㅜ 실전 감각도 좀 길러볼겸 신청했는데 저렇게 메일이 왔네요.
 

오 대회 치러 갔다가 공짜 티셔츠는 예상치 못한 수확이라 좀 좋네요 ㅋㅋ 강의실에 입고 가서 월향의 위상을  드높이도록 하겠습니다 bb
 
등록하는데 운영진 분들이 저를 알아봐 주셔서 신기했어요.
 

대회 장소 건물이 되게 이뻤는데(찍지는 않았지만) 내부도 깔끔하고 엄청 좋더라고요. 장소 후원해주신 분들께 감사의 인사를 드립니다.
그리고 제가 1시 40분쯤? 도착했는데 2시에 대회 소개 같은 걸 안하고 바로 시작해서 마음의 준비가 좀 덜될 뻔했어요 하핫
근데 원래 긴장할 시간 없이 바로 시작해야 본인 컨디션이 제일 잘나와서 결과엔 나름 만족하는 부분이에요.
 
암튼 부랴부랴 로그인하고 백준 뒤적거리면서 템플릿 좀 긁다보니 벌써 시작 시간이 되었네요.
 
 
지금부터는 문제 및 간단한 풀이과정입니다.
 

A. 다음 달에 봐요

사실 딱히 설명할 건 없고 문제가 시키는 대로 구현하면 끝입니다. 시작한지 1분만에 AC. 다행히 1번 문제는 자존감을 쑥쑥 올려주는 문제였네요. 근데 다음 문제가..
 
 

B. 네모의 꿈

지문 보고 좀 멘붕.. 삼각형 2개를 붙여서 사각형을 만들라던데 오목사각형 같은 건 안 되는 줄 알고 한참 고민했네요.
 

오목사각형

 
세 변의 길이를 가지고 각도를 구해서 붙여봐야 하나..? 코사인 법칙 구글에 검색해봐야 하나 심각한 생각을 하고 있었어요. (구현이 너무 귀찮아서)
 
음.. 근데 이 생각을 하는 사이 스코어보드에 B랑 C를 전부 다 푸신 분들도 몇분씩 보이더군요. 원래 이럴 때일수록 더 보면 안되는건데 눈이 돌아가는 건 어쩔 수가 없나 봐요. 그런데 이런거에 조급해져셔 생각하기 전에 코드부터 치기 시작하면 더 꼬이기 시작하고 그럼 더 급해지고 이런 악순환에 빠지게 되더라고요.
 
다시 침착하게 생각해서 두 변이 같은 삼각형이 존재하기만 하면 붙여서 삼각형이 되더라도 뒤집어서 붙이면 사각형이 될 수 있지 않나 하는 생각을 하게 됐어요. 나중에 에디토리얼에서 반례에 대해 보여주시고 특수한 조건을 넣으셨다고 했는데 멍충이라 거기까진 생각못했지만 아무튼 12분만에 AC. 체감상 30분은 되는 것처럼 느껴졌는데 생각보다 빨리 풀었네요.

 
 

C. 아보와 킨텍스

 

문제를 읽고 가장 처음에 든 생각이 일단 모든 경우의 가짓수를 다 넣고 중복되는 경우를 빼야겠다는 생각을 했어요.
음.. 이때쯤 저의 치명적인 실수를 깨달았는데 집에서 까먹고 노트와 펜을 안 들고왔네요. 껄껄껄
 
뭐 어쩌겠어요 머리가 안좋으면 머리가 고생해야죠. 머리를 좀 굴려 보니 n+1 가지의 자리에 알파벳을 넣을 수 있겠고 알파벳의 개수는 26개(기억안나서 구글에 검색) 가 있으니 총 가짓수는 26*(n+1)가지로군요. 이제 중복되는 경우를 없애는 방법에 대해 생각해 보려는데..
 

아하 규칙을 좀 찾아보니 어떤 글자가 있으면 그 양옆에 같은 글자를 넣는 경우가 겹치는 경우네요. 그러면 지금은 a가 1개 연속되니 1개를 총 가짓수에서 빼면 되겠고.. 
 

x글자가 연속되면 (x+1)가지가 같은 경우니까 그 중 x가지를 빼주면 되겠네요~
그럼 예시로 본 abbbcccc 는 [1, 3, 4] 로 표현할 수 있고 각각의 숫자를 총 가짓수에서 빼기만 하면 되겠어요.
 
아니 생각해보니 저걸 다 더한거면 그냥 처음에 줬던 문자열 길이랑 같은 거잖아...

실전에서도 다 구해놓고 급히 틀었습니다. ㅋㅋㅋㅋㅋ 처음부터 이거만 있으면 되는 거였는데..
그래도 시작한지 19분에 AC.
 
 
 

D. 꿀잼 루비 문제

아.. 제목을 보니 뭔가 난이도가 루비일 것 같습니다. 스코어보드를 보니 그 정도까진 아니더라도 D는 패스하고 바로 E로 넘어가신 분들이 많이 보이더군요. 하나의 칸을 고르면 상하좌우 4개의 칸을 고를 수 없다고 하네요. 이거 유량에서 비슷한 문제를 본 거 같기도 하고.. 최근 m개의 칸을 저장하는 비트마스킹 문제도 생각이 났지만 그러기엔 너무 판이 큰 것 같아요.
 
역시 다들 거르는 문제는 그럴만한 이유가 있나 싶었는데 조건에서 뭔가 이상한 걸 발견합니다.

흠.. K가 최대 5라니 뭔가 좀 수상한 부분인데요. 관심법으로 시간복잡도 궁예질을 해보니 K가 크면 해결하기 힘든 그런 뭔가가 있나 봐요. 그리디적인 사고방식이 통할 것도 같습니다. 증명은 잘 모르겠지만 가장 큰 칸 50개만 골라서 백트래킹을 해보기로 했어요.

제가 평소에 쓰는 계산기로 조합을 해보니 경우의 수가 시간 내로 충분히 들어오겠더군요. 백트래킹은 ChatGpt가 잘 해주니까 그 친구한테 시켜서 무난하게 맞습니다. 코드는 제가 직접 짠게 아니니 대신 gpt에게 보낸 쿼리를 첨부할게요.
 

이 친구가 파이썬으로 짜길래 C++로 다시 해달라고 했는데 거의 정확하더군요. 대신 최대 K개가 아닌 정확하게  K개만 고르는 경우를 계산하길래 그 부분만 조금 수정했습니다. 원래같았으면 여기에 1시간쯤 썼을 것 같은데 40분만에 AC를 받았네요. 푸는데 20분 걸렸습니다 오예
 
 

E. Knight Cruising

 
제가 또 체스 짬이 6년이 넘었는데 체스를 여기서 보니 반갑군요. 요즘 한국에서 체스가 점점 유행을 타는 것 같아 좋습니다. 여러분 평생 섭종할일 없는 짱짱체스 많이 둬주세요.
 
이 3차원 나이트는 이동하는 방법이 뭔가 대칭적(?)이군요. x, y, z축을 임의로 바꿔도 이동할 수 있는 칸이 모두 같아요. 예시를 잘 보니까 좌표의 합이 홀수인지 짝수인지에 따라 가능 여부가 나뉘는 것 같습니다. D를 풀때 활용한 감각적 직관이 또 발동이 되네요.

근데 한번 틀린건 뭣 때문이냐면 그 와중에 욕심이 그득해서 숏코딩 하겠다고 불필요한 헤더파일 지웠다가 필요한 것까지 지워버리는 바람에 런타임 ㅇㅔ러.. 패널티 냠냠 먹었네요. 문제는 2분만에 풀었지만 22분만에 푸는 효과를 줘서 스스로 밸런스를 맞췄습니다.

 
 

F. 선분의 합집합

아.. 여기서부터 문제가 그냥 개어려워요. 조금 생각해가지곤 택도 없겠다 싶어서 F, G, H 돌아가면서 10분씩 생각하는 BFS적 사고를 해보지만 영 소득이 없습니다. 특히 요거는 컨디션 좋을 때 진득하게 생각하면 풀 수 있을 것 같은 삘이 나는 문제였는데 대회때는 똥줄이 타기 시작하니까 정상적인 사고가 안되는군요. 그래도 스코어보드에서 그나마 많이 풀린 문제니까 이거라도 잡고 풀어봅니다.
 
이 문제가 어렵다고 생각한 이유는 선분 집합을 골랐을 때 가능한 길이의 최대값 뿐만 아니라 최소값이 존재한다는 거였어요. 그러니까 어떤 쿼리에서 A의 비용으로 B의 길이를 만들라고 시켰는데, 최대값(상한)만 존재한다면 그냥 길게 이어서 B보다 큰지만 체크하면 되지만 이 문제에서는 선분의 집합에서 가장 긴 선분의 길이가 집합의 최소값(하한)이 되네요.
 
일단 하한을 맞추는게 더 중요하다고 판단이 되서 선분의 길이순으로 정렬하고 생각해봤습니다.
이제 쿼리에서 길이 B가 주어지면 이 B보다 작은 선분들만 골라서 B보다 더 크게 만들어봐야겠다고 생각했어요.
 

 
이렇게 dp식을 만들어 보았는데 정확히 cost만큼의 비용을 사용해서 만드는 부분이 생각할 여지가 좀 있더군요.
 
그리고 무엇보다 제가 이 답에 확신이 없었던게 n=100, A=10^6 이라 dp배열을 다 채우면 크기가 1억이에요. 여기까지만 해도 좀 빡센데 쿼리 하나를 처리할 때 i(B보다 작거나 같은 선분의 위치)를 배열에서 이분 탐색을 이용해서 찾았기 때문에 쿼리 하나 처리할 때 O(log n) 이 걸리는군요.
 
결국 시간복잡도는 O(NlogN+AN+QlogN)이 됩니다. (NlogN은 선분 정렬) 설마하는 마음으로 제출을 해봤지만..
 

 
 
앗;; 이럴수가.. 백준신을 향한 기도가 통하지 않았네요. 역시 1억개의 dp 테이블은 시간도 메모리도 빡센 걸까요. 저는 여기서 현실부정을 하느라 조금만 수정하고 제출을 해서 TLE를 몇번 더 보게 되고 다시 생각에 들어갑니다.
 
생각해보니 선분 하나의 길이는 10000을 넘지 않으니까 만약 쿼리에서 B가 주어졌을 때 10000보다 크면 i는 무조건 n-1로 고정이겠네요. 뿐만 아니라 O(10000)의 전처리를 하면 i를 O(1)로 찾을 수 있겠어요. 그럼 쿼리 하나도 O(1)로 처리할 수 있겠네요.
 
O(NlogN+AN+Q)의 코드를 다시 제출해 봅니다. (두근두근)
 
 
 
 

TLE렸습니다

 
아잇 역시 이 풀이는 출제자가 의도한 풀이가 아닌 걸까요? 그런데 아무리 코드를 살펴봐도 여기서 더 최적화를 시킬 방법이 떠오르지 않습니다. 그런데 코드를 몇번이나 점검하던 도중 뭔가 수상한 점이 보이네요.
 
 
 

네... 맞습니다. 제가 fastIO 설정을 하지 않았어요. 아직도 이런 초보적인 실수를 하다니.. 이 부분을 고치자마자 귀신같이 맞아서 더 야속해요.. 이렇게 대회를 시작한지 119분만에 F를 맞춥니다.
 

O(NlogN+AN+QlogN) 코드는 아직 채점은 안해봤는데 그것마저도 맞추면 더 홧병날 것 같습니다. 끝나고 나서 다른 분들 코드를 보니 이건 진짜 정해가 아니었던 것 같아요. 나중에 더 자세히 이해하려고 노력해 봐야겠네요.
 
 
 

G. 아이보리와 함께 푸는 스도쿠

우여곡절 끝에 F를 맞췄으니 좀 여유가 생겼습니다. 그리고 아직 시간은 1시간이 남았구요. 근데 스포를 하자면 남은 1시간 동안 1문제도 못풀었습니다.
 

그래도 이 문제는 보니까 직관적으로 n-1 칸까지는 최소한 답이 2개 이상일 거라는 생각이 떠올랐어요. 그리고 나머지는 이분 탐색으로 답이 1개가 나오는 최소값을 찾으려고 해봤는데 시간복잡도도 계산이 잘 안되고 구현도 할게 많더군요.
 
다시 gpt한테 시켰는데 이녀석이 약발이 다 들었나 영 신통치가 않습니다. D에서 짜준 코드가 이상하리만치 너무 완벽하긴 했어요. 제가 점검을 해 봐도 틀린 부분이 도통 안보이더군요.
 
 

H. 코코아와 마법사의 돌

 
이건 접근 방법조차 잘 생각이 안 났네요. 무작위화가 답인가 싶어서 그냥 정점을 랜덤으로 이어봤는데 당연히 될 리가 없습니다.

WA만 하나 적립한채로 대회가 끝났군요. 
 
 

I. 순열 제작의 달인

이거는 읽자마자 제가 대회 시간에 내에 풀 수 없다는 걸 깨닫고 바로 손절을 해버렸습니다. 근데 I가 어려워서 J는 더 어려울 줄 알고 읽지도 않았는데 J가 더 해볼만 하더군요 ㅠㅠ
 
 

J. 래빗 홀

대회가 끝나고 나서 읽어 본 거지만 그래도 님 게임의 변형인 것 같습니다. 님 게임을 이기는 법은 전부 XOR해서 그런디 수 어쩌구가 0이 되어야 했던가 0이 되면 안됐던가 아무튼 그런 비슷한 배경지식이 있었어요. 보니까 구멍을 줄이는 건 그런디 수는 안 바꾸고 그냥 턴을 넘기는 액션이네요. 구멍 수의 홀짝성에 따라 승패가 바뀌는 그런 느낌인 것 같아요.
 
 
 

 
스코어보드 오픈의 시간이 왔군요. 프리즈될때 제가 7등이었는데 등수 유지만 한 걸로도 저는 매우 만족합니다. 역시 고수 분들 많으셔요ㄷㄷ
 
 
그 다음엔 상품추첨 시간이 있었는데 공이 랜덤으로 내려와서 늦게 들어가는 분에게 상품을 수여하는 심장이 쫄깃쫄깃한 이벤트가 있던데요, 안타깝게도 저는 안걸려서 아깝네요 ㅠㅠ
 
음 영상을 첨부하고 싶었는데 어떤 프로그램인지 이름을 잘 모르겠어요.
 

아무튼 이렇게 월간 향유회 오프라인 대회가 끝이 났어요. 쉬는 시간에 심심해서 다음번엔 미리 아는 분을 만들어서 가야겠다고 생각했습니다. 좋은 문제 출제해주신 출제진, 검수진, 운영진 모두 고생 많으셨고 좋은 대회 열어주셔서 감사합니다(꾸벅)