C/C++로 알아보는

UCPC2024는 출전 못할 줄 알았다. 극적으로 디코에서 팀원을 구해서 신청하게 되었다. 

그래서 최종 팀원은 @rustiebeats, @ychangseok과 함께 나가게 되었다. 팀명 후보로는

"팀 이름 후보 드릴테니 이중에 정해주세요", "); DROP TABLE Teams;--", "어디갔어다", "1.팀 이름 후보 드릴테니 이중에 정해주세요 2. ); DROP TABLE Teams;-- 3. 어디갔어다" 정도를 제시했는데 "); DROP TABLE Teams;--"가 채택되었다.

')', ';' 등이 사용할 수 없는 문자여서 강제 리젝당했고 결국 가-힣ㄱ-ㅎㅏ-ㅣa-zA-Z0-9-_가 팀명이 되었다.

너무 흔한 팀명을 써서인가 결국 "정규식 팀"이 세팀이나 만들어지는 불상사가 생겼다...

 팀 연습부터 대회까지 @rustiebeats님이 ABCD, 내가 EFGH, @ychangseok님이 나머지 문제를 먼저 읽는 방향으로 문제풀이를 했다. 예선의 경우 A가 가장 쉬운 문제가 나오기 때문에 @rustiebeats님이 A번을 빨리 구현하고 스타트하게 되었다. 

주로 @rustiebeats님이 구현이 까다로운 문제를 맡아주셨고 @ychangseok님은 내가 구현하다가 틀린 코드 리딩과 반례찾기를 해주셨고 내가 아이디어를 내고 구현을 팀원한테 던지고 도망가는 역할을 맡았다. 개인적으로 스스로 직관력이 좋은 편이라고 생각하는데 직관에만 의존하는 나머지 에지케이스를 못보고 넘어가는 경우가 아주 많아서 상당히 도움이 되어주셨다.

예선에서는 @ychangseok님이 HIJK를 읽어주셔서 나는 맨 처음에 EFG까지 읽었다.

A (00:01) @rustiebeats님이 그냥 풀어주셨다. 여전히 무슨 문제인지 읽어보지도 않았다.

C (00:02) @rustiebeats님이 A를 그새 다 풀고 C가 스택이라고 하고 넘어갔다. 이게 뒤에서 크게 작용하는데...

G,H(00:03) EF를 읽고 당장 풀 문제는 아니다 싶어서 G로 넘어왔는데 쉽게 풀리겠다는 직감이 들어서 풀이 스케치를 시작했다. @ychangseok님이 구현을 시작하셨다.

G,H(00:05) G의 솔루션이 나왔고 H가 WA를 받았다. 이후 팀원 두 분이서 H를 계속 고민해주셨다.

E (00:19) G만 잡고있어서 지루했던건지 E를 갑자기 잡는다고 했다. 결국 1분도 안돼서 다시 G를 구현하러 감

G(00:27) 2번의 RE 끝에 AC를 받았다. DSU 프리셋과 빠른 타자속도만 있었으면 퍼솔도 노려볼만하지 않았나 하는 생각도 들었다. RE 사유는 100만 크기의 배열을 잡으려고 했으나 10만이라 쳐서...

E (00:29) E를 다시 고민하러 왔다. @rustiebeats님이랑 같이 고민을 하다가

E,C,D(00:31) @rustiebeats님이 솔루션을 내주셨다. 고전적인 dp/bfs에는 나보다 훨씬 식견이 높으신듯. 구현을 맡기고 C와 D를 읽으러 갔다. 여전히 E 푸는데 토의도 같이 했다.

D,J(00:39) D와 J의 풀이가 거의 동시에 나왔다. D는 내가, J는 @ychangseok님이 풀이를 냈다. 하지만 둘다 틀렸다.
E(00:49) E의 구현이 끝나고 AC를 받았다. 이때 상당히 가능성을 본 느낌을 받았으나... ...

J (00:55) 2WA를 받았다는 소식을 들었다. 그리고 세명 다 J로 모였다.
D(01:07) D를 WA받았다. 그냥 WA가 아니고 로직을 깨는 반례를 맞았다. 여기서 포기.

J(01:18) @ychangseok님이 짝수번째만 뒤집는 발상을 해주셨는데 내가 이해를 못하고 그냥 묵살해버렸다...

C(01:20) J만 잡고있어서는 답이 안나올 것 같아서 C와 번갈아 가면서 봤다. C는 @rustiebeats님이, J는 @ychangseok님이, 나는 두개를 번갈아가면서 봤다. 

C(01:30) C의 대략적인 솔루션을 제시했다. 정답 알고리즘의 명세를 @rustiebeats님한테 던지고 나는 예제를 손으로 테스트해봤다. 이쯤에서인가 @ychangseok님이 D를 구현시작하셨다. 세그트리를 비벼먹은거같은데 잘 모르겠다.

J(01:42) 불현듯 든 생각이 정답을 만들었다. 괄호 문자열이라는 생각을 하고 나서 계속 구현하던 @ychangseok님이 아닌 내가 구현을 새로 해서 AC를 받았다. 32비트정수만으로 짜서 1WA를 추가로 더 받긴 했다.

C(02:21) C를 구현시작했다.

C(02:34) C 구현을 마치고 WA를 받았다.

D(02:35) @ychangseok님이 구현을 마치고 AC를 받았다. C를 구현하는 나를 제외하고 H로 모였다.

C(02:46) C를 AC했다. 정말 정신없이 마무리했던가 대회가 끝난 뒤 왜 못풀었을까 하고 업솔빙을 시도함...

마지막까지 H를 붙잡고 있었지만 최종 스코어보드는 6솔브 51등으로 마무리했다. 사실 여기서 H를 풀었어야하는데 케이스워크 능력이 좀 부족하다고 느끼게 되었다.

그리고 결국 본선에 가게되었다. LG의 넓은 대관과 회장님의 넓은 아량으로 낮춰진 컷에 겨우 들어서 예선을 통과했다고 들었다. 감사합니다 ㅠㅠ

연습 중에도 ychangseok님께 구현을 많이 떠넘긴 감이 있는 것 같은데 본 대회 중에도 열심히 코드를 짜주셨다...

최종 본선 49등 5솔브로 마무리했다. (2등 올랐다!)

A(+182) 처음부터 고민을 좀 했던 문제였다. O면 +여야한다는건 퍼스트 솔브 이전에 깨달았지만 X일때 판정하는 법에서 off by one같은데서 좀 많이 고민했다.

B(x) 제법 고민을 했던 문제인데 다이어그램 그리는걸 실패해서 포기

C(+239) rustiebeats님과 ychangseok님이 금방 구현해내신 문제. 처음에 이상한 구현문제라서 패스했는데 갑자기 rustiebeats님이 "아니 이거 개쉬운데"하고 금방 구현해내셨다. 이거 처음에 잡았으면 퍼솔도 먹고 패널티도 많이 줄었을 듯. 두분이 뚝딱 풀어주셔서 L번에 매진해서 고민할 수 있었고 해설 공개때까지 문제를 읽어보지도 못하고 AC당했다.

D(+25) 팀 내 첫 솔브 문제이다. 사실 문제 지문은 다 안읽었고 rustiebeat님이 문제를 빨리 해석해서 요약본을 주신 것만 읽고 바로 풀었다. 최대한 균등하게 나눠주면 되는 문제였고 연습때 쌓인 업보인지 나보고 구현해 달라는 요구를 하셨다... 결국 생 라이브로 짜긴 함.

E(+298) 맨 처음 읽은 문제인데 처음에는 그냥 넘기고 다시 돌아와서 봤을 때는 연속된 1과 2로 둘러싸인 빈칸을 잘 처리해주면 된다는 것이었다. 150분즈음에 답을 얻었지만 확신없음+구현이슈때문에 뒤로 미뤄뒀다. 결국 나 아니면 상대가 먹어야 한다는게 대칭 포인트였는데 엄밀한 증명에는 실패하고 PBA를 시도했다.

J(x) HLD 아이디어는 문제를 보자마자 캐치했지만 HLD를 짤 줄 몰라서 시도도 못한 문제. 하지만 HLD가 정해가 아니라는것에 1차 충격, 하지만 HLD로 푼 팀이 대부분이고 정해대로 푼 팀이 한 팀밖에 없었다는 것에 2차 충격

L(-1) 이걸 풀었어야 하는데 실패했다. 이분 매칭에 대한 이해 없이 그냥 무지성으로 플로우를 흘리는 코드를 외우기만 했어서 벌어진 참사라고 생각한다. 아이디어 자체는 작은 정점부터 플로우를 흘리면 된다는걸 알았지만 코드를 짜는법을 몰라서 AC를 받지 못했다. 이분매칭 공부다시할것

M(+290) 다른 문제는 잘 모르겠지만 이 문제는 오류가 있다. +290분이 아니라 +297분에 AC를 받았기 때문. 종료 직전에 버저비터를 눌렀다고 생각했지만 특별상 조건인 마지막 AC를 받지 못했다. 많이 아쉬울 따름.

문제 자체는 +30분 이전에 다이어그램은 혼자 머리속으로 그려보긴 했으나 풀이 방향을 완전히 다른 방향으로 잡아서 실패. rustiebeats님이 중간에 캐치해서 마지막의 마지막에 AC를 받았다. 대회가 끝나고 "산을 그리세요"를 얼마나 들은건지 잘 모르겠다.

끝나고는 참가자 몇 분과 대회 후원자분 하고 뒷풀이를 가졌다. 오래 하지 않은 것으로 들었는데 집가는 열차 시간 때문에 중간에 나오게 되었다.

집가는 SRT경부선에 탄 시점은 휴대폰이 1%남았던 시점... 하마터면 지하철에서 못내릴뻔

후기

1. 플래티넘 랜덤 디펜스는 상당히 중요하고 실력 향상에 도움이 된다.

2. 구현력을 키워야함. 

3. 보조배터리를 잘 챙기자

이분 탐색은 탐색 시간이 자료 크기의 로그스케일에 바운드되는 자료 검색 알고리즘이다.

어떤 자료 a가 이분 탐색을 할 수 있으려면 
1. 어떤 조건식 bool f(element)를 상수함수로 가져야 한다.

2. 참인 요소와 거짓인 요소가 완전히 분리되어있어야 한다. 좀 더 수식적으로 엄밀하게 표현하면 i<j<k인 인덱스에 대해 f(a[i])!=f(a[j])!=f(a[k])인 i,j,k쌍이 없어야 한다.

두 조건을 만족해야 한다. 이때 찾는 값은 f(a[i-1])!=f(a[i])인 i, f에 대한 평가가 달라지는 가장 작은 인덱스 또는 f에 대한 평가가 달라지는 경계의 바로 오른쪽 인덱스이다.

2번 조건은 f(a[i-1])!=f(a[i])가 존재하면 유일하다는 것을 의미한다. 예를 들어 f(a[i-1])!=f(a[i])이고 f(a[j-1])!=f(a[j])라면 WLOG i<j에서 1. f(a[i])==f(a[j-1]), 2. f(a[i])!=f(a[j-1])인데 1의 경우 i-1<i<j, 2의 경우 i-1<i<j-1이 2의 조건을 만족하지 못한다. 따라서 답이 존재하면 유일하다. 좀 더 자연스럽게 표현하면 평가가 참인 요소는 모두 전체가 연속해야하고, 평가가 거짓인 요소는 모두 전체가 연속해야 한다. 좀 더 쉽게 표현하면 f에 대한 평가를 기준으로 정렬되어있어야 한다.

만약 모든 요소의 평가가 같다면 어떨까? WLOG 왼쪽의 평가를 거짓, 오른쪽의 평가를 참이라고 강제하고 생각해보면 f(a[i-1])!=f(a[i])라는게 사실은 f(a[i-1])이 거짓, f(a[i])가 참인 i를 반환하는 것으로 생각할 수 있으므로 모든 n개의 평가가 참이라면 i=0, 거짓이라면 i=n을 반환하는 것으로 볼 수 있다 (0-index). 이때 i=n은 대응하는 자료의 값이 없어 컴퓨터에서는 할당되지 않은 메모리를 가리킬 수 있음에 유의해야 한다. 

이분 탐색의 원리는

1. 왼쪽 끝과 오른쪽 끝의 평가가 다른 어떤 구간을 알고 있다. WLOG, 왼쪽의 평가를 거짓, 오른쪽의 평가를 참이라고 할 수 있다. 반대이면 f의 평가를 뒤집는 함수를 생각하는 것으로 충분하다.

2. 여기서 구간 가운데 어떤 인덱스를 잡는다. 이 인덱스가 가리키는 요소의 평가는 참 또는 거짓이다. 이때 조건 2에 의해 평가가 참인 경우 현재 인덱스와 왼쪽 끝의 평가가 다르고, 평가가 거짓인 경우 현재 인덱스와 오른쪽 끝의 평가가 다르다.

3. 이는 1에서 찾은 양 끝의 평가가 다른 어떤 구간보다 작은 구간이다. 따라서 1을 크기가 더 작은 부분구간에 대해 반복할 수 있다. 더이상 2에서의 가운데 인덱스를 잡을 수 없을 때까지 반복한다. 이때의 오른쪽 끝이 구하고자 하는 답이 된다.

의 반복으로 저런 인덱스를 찾을 수 있다는 것이다. 여기서 가운데 인덱스를 잡는 방법에 따라 시간복잡도가 결정되는데, 가운데 인덱스를 정확히 구간의 가운데로 잡으면 자료의 순서에 관계없이 크기의 로그스케일에 바운드된다.

예를 들어 자료 a=[1,1,2,2,3,4,6,6,7]에서 f(x) = "x>=5"의 평가를 기준으로 이분탐색을 하려고 한다. 자연어로 표현하면 5 이상인 가장 작은 인덱스를 찾으려고 한다. 0-index를 기준으로 구간 [0,8]은 왼쪽 끝과 오른쪽 끝의 평가가 다른 구간이다. 구간의 가운데인 인덱스 4를 잡았다. f(a[4])는 "3>=5"로 거짓이므로 구간 [4,8] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 다시 구간의 가운데인 인덱스 6을 잡으면 f(a[6])은 "6>=5"로 참이므로 [4,6] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 다시 구간의 가운데인 인덱스 5를 잡으면 f(a[5])는 "4>=5"로 거짓이므로 [5,6] 또한 평가가 다른 조건을 만족하는 더 작은 구간이다. 이때 더이상 가운데 구간을 잡을 수 없고, 5+1==6이므로 f(a[i-1])!=f(a[i])를 만족하는 인덱스 i=6을 찾았다.

C++ STL의 std::upper_bound/lower_bound를 비롯한 많은 언어가 이런 이분 탐색의 특정 케이스를 지원한다. 특히 std::upper_bound는 어떤 값 t를 받아 f(x) = "t<x"를 기준으로, std::lower_bound는 f(x) = "t<=x"를 기준으로 이분 탐색을 진행한다. 자연어로 설명하면 upper_bound는 초과를 기준으로, lower_bound는 이상을 기준으로 이분탐색을 진행한다. 또한 std::upper_bound/lower_bound는 네번째 인자를 람다로 받을 수 있는 오버로딩이 되어 있어 연산자 <, <=를 람다 형식으로 넘길 수도 다. 

Solved.ac 주최 그랜드 아레나 파티에 신청을 해 뒀는데, 선발되었다는 메일이 도착했다.

사실 무엇보다 선발 기준이 좀 궁금해졌는데, 선발 시점 마지막 아레나 A16을 지각+실력 이슈로 처참하게 말아먹고 난 직후였기 때문에 왜 선발됐는지 정말 궁금해졌다.

처음 예상은 1, 2번 조건은 해당 없음, 3번 조건은 100명을 뽑아도 컷에 못 들기 때문에 불가능, 4번 조건은 7회 모두 (A10~A16)참여한 사람 중 운이 좋은 경우, 5번 조건은 상위권에서 뽑겠다는 의미에서 컷보다 낮을 것으로 예상, 6, 7, 9번 조건에서 운이 좋게 선발되는 경우정도가 선발되는 경우라고 생각했기 때문이다. 실제로 4, 6, 7번 조건 내에서 우선순위를 높이려고 7회 모두 참여했는데 (A16은 컴퓨팅 환경이 없어서 휴대폰으로 억지로 참여하기도 했고), 예상 외로 4번 조건에서 7회 참가자가 전원 선발되었다.

사실 선정 확률을 높여보고자 컨퍼런스 발표 신청이라도 할까 했는데 마땅한 주제가 없어서 결국 신청 못하고 되면 좋고 하는 마인드로 기다렸는데 약간은 허무하게(?) 선정되었다.

11시까지 대회장에 도착하는 것을 목표로 계산해본 결과 8시까지는 동대구역에 도착해야 했고, 전날 금요일 저녁약속에서 집에 돌아왔을 때 이미 12시였기 때문에 바로 잠자리에 누웠다. 그런데 6시까지 잠들지 못해 밤을 샌 채로 서울행 KTX에 올랐다....

한 11시 10분쯤 돼서 대회장에 도착했다. 프론트에는 @shiftpsh 대표님, @kipa00님, 대회 후원을 해주신 Chris "utilforever" Ohk님 및 여러 스태프 분이 계셨고 (죄송합니다... 얼굴이 매칭이 잘 안돼서...) 안내를 받고 대회 유니폼으로 갈아입었다.

대회장에 들어서자마자 스태프 분들과 퍼즐 헌트를 진행중인 많은 참가자 분들이 분주하게 움직이고 계셨다. 자리를 찾아 앉자마자 퍼즐 헌트 팀원이셨던 @mingmingmon님이 빠르게 저를 납치해 가셨고 눈치 살필 겨를도 없이 퍼즐 헌트 이벤트에 바로 뛰어들었다. 

팀 스코어 최종 6솔브로 마무리했다. 내가 푼 문제는 네 번째 이야기인데, 원래부터 이런 유형의 문제에 강했기 때문에 가장 먼저 시작했다. 혼자 풀 때는 잘 안풀렸는데 예전에도 그런 경험이 있어 팀원 중 아무나를 붙잡고 설명하면서 문제 풀이를 똑같이 했는데 답이 나왔다... 답안 제출할 때까지만 해도 그냥 그런줄 알았는데 지금 다시 보니 답이 "TAB UI"였다. TABUI가 뭐지 하면서 그냥 제출하긴 했는데... 이후 다섯 번째 이야기의 io.cpp를 해석하고 시간이 끝났다. 결국 답을 얻지는 못했고 최종 6솔브로 끝났다.

@toycartoon님이 대회장 전체를 돌면서 많은 참가자분들의 사인을 받으러 다니셨는데, 퍼즐헌트를 본격적으로 시작해보려 하기 직전에 사인을 뺏겼다. 본 대회가 시작되기 전 쉬는 시간 Chris "utilforever" Ohk님이 잠시 시간이 있어보이시길래 지난 대회 검수 감사 인사도 드릴겸 인사드리고 왔다. 

본 대회가 시작하기 전 갑자기 책상이 무너져서 상당히 당황했는데, @shiftpsh 대표님께 말씀 드리니까 즉시 책상을 교체해주셨다. 감사합니다.

본 대회에서는 3솔브로 마무리했다. A, B는 5분 이내로 빠르게 마무리 했는데 C를 풀다가 구현의 늪에 빠져버려서 120분째에 포기, D, E를 번갈아가면서 보다가 D가 빠르게 솔루션이 나와서 119분째에 해결했다. 해결하자마자 스코어보드가 프리즈됐는데, 스태프 분들이 프리즈 이후 해결로 잘못 보셨는지 결국 풍선은 두 개밖에 받지 못했다...

C 구현이 너무 힘들어서 자주 스코어보드를 들여다보게 됐는데 C번에서 많이 갈렸던 듯 하다. C번이 까다로운 구현 문제였었던지 많은 분들이 제 위로는 그런 분들이 많지 않았는데 아래로는 AC를 받았던 받지 못했던 많은 횟수를 트라이하신 분들이 많았다. 덕분에 3솔브 스코어보드가 패널티가 상당히 큰 셋이 되었고, 아예 C를 일찍 포기했던 내 등수가 3솔브가 상당히 늦었음에도 불구하고 3솔브 중 중간정도 등수까지 올라갈 수 있었다. 더군다나 그 덕에 특별상도 수상하게 되었다.

대회가 끝나고 유저 컨퍼런스를 진행했는데 @kiwiyou님, @cki86201님, @kipa00님 순서로 발표가 이어졌다. 요약하자면 @kiwiyou님과 @kipa00님은 "그들만의 웰노운", @cki86201님은 "yandex cup 재밌었다" 정도였다. 추이공간과 다면체군, 법률과 OOP 같은 "그들만의 웰노운"같은 발표할만한 자료가 있긴 한데 준비가 된다면, 그리고 기회가 된다면 해보고 싶긴 했다.

모든 순서가 끝나고 바깥에 계시던 @kiwiyou님, @dohoon님, Chris "utilforever" Ohk님 등 여러 분이 모여계시길래 잠시 인사를 하고 나왔다. @kiwiyou님께서 문제 잘 풀었다고 감사의 말을 해주셨는데 사실 무슨 문제인지 잘 모르겠다. (파댕이컵 H번인 것 같긴 한데... 맞나요...?) 아무튼 잘 풀어주셔서 감사합니다. @dohoon님은 "가을 프사분"으로 기억하고계셨다...

마지막으로 @mugamta 선배님과 저녁을 먹고 다시 서울역으로 갔다. 부족한 잠을 채우기 위해 KTX 안에서 잘까 했는데 스트릭을 위해 다른 문제를 KTX 안에서 풀고 잤다.

한 일.

@kiwiyou님, Chris "utilforever" Ohk님, @toycartoon님께 :fan:이에요 시전

릭롤링당하기

TODO.

@shiftpsh 대표님, Chris "utilforever" Ohk님 명함에 사인 받기

구현 문제 보고 도망가지 않을 정도로 연습하기

대회 링크: https://www.acmicpc.net/contest/view/1208

첫 대회 개최인 만큼 열심히 공들였던 것 같다. 출제/검수진 모집, BOJ 대회 개최 신청 컨택, 무엇보다 이모티콘 작가님 컨택까지 제법 오래 신경썼던 것 같다.

내가 출제한 문제는 E번, H번이다.

E번은 원래 "정점 분할 말고 간선 분할이 정해인 문제를 만들어보자"하고 만든 문제인데, 간선분할 데이터를 만들고 보니 정점 분할이 더 최적해였다... ... 정점 분할이 적정 부하를 받도록 문제를 세팅하고 보니 간선 분할이 메모리를 2GB나 먹는 사태가 벌어졌다. 

실제 출제 과정에서 가장 조용히 넘어갔던 문제였다. 조용히 세 분이 풀어주시고 디스크립션 수정 한두번이 끝이었다.

하지만... 대회가 시작되자마자 가장 많은 질문과 지문 수정과 토의가 이루어진 문제가 되었다. 대회 전에 문제 꼼꼼히 읽어야 한다는 것을 다시금 깨닫게 해준 문제였다.

H번은 이상한 알고리즘같은걸 찾아보다가 보로노이 다이어그램을 발견하고 읽던 와중에 떠오른 아이디어이다. 쌍대그래프라는 단어가 등장했는데, 쌍대를 이용한 문제를 만들고자 했다. 그때 4차원 기하학 문제를 만들고 싶어서 여러가지 생각이 많았는데, 4차원 쌍대를 발견하고 이거다 해서 만들게 되었다. 사실 결국 쌍대다포체가 풀이에 반드시 필요하지는 않아서 에디토리얼에서 쌍대다포체 얘기를 빼고 싶었는데, 예전에 문제 풀때 에디토리얼이 불친절해서 고생했던 기억이 떠올라 그래프 모델링 과정까지 작성했다. 출제검수단계에서 이 문제를 사람들이 어떻게 느낄지 좀 궁금했다. 당연히 내가 봤을 때는 4차원 이상의 기하학, 정다면체 등에 대해 집중해서 찾아봤기 때문에 대놓고 이분매칭이라는 느낌이 들었는데, 검수진들 반응을 보니 그렇지 않았던 것 같다. 특히 검수 코멘트로 "이분 그래프인지 알기 어려웠다"는 멘트가 달려서 제법 난감했다. 그래서 다차원 입방체가 이분그래프라는 말을 에디토리얼에 추가로 작성해줬다.

실제 대회에서도 이분 그래프라는 사실을 파악하지 못하고 General matching으로 해결하신 분이 있었다. 크기가 작아서 해결됐지만, 4차원이 아니고 k차원으로 줬으면 해결 못했을지도...

원래 전체 문제가 난이도 순으로 정렬될 예정이었으나 문제 순서에 맞게 디스크립션을 작성하다 보니 결과적으로 A,B,H정도만 제외하면 Gold~Platinum 난이도에서 섞여있는 모양새가 되었다. (C번이 빡센 구현이 된 것이 컸던 것 같다.)

다른 분이 출제한 문제 리뷰도 해보자면, C번은 O(NMT)를 O(T^3)으로 줄여야 풀리도록 설계되었는데, bitset을 이용해 깡으로 뚫어버린(...) 문제가 되었다.

D, E, F, G는 객관적으로 난이도가 제법 비슷했는데, G가 가장 먼저 풀렸고, 깡 수학이었던 F는 일찍 풀리긴 했으나 푼 사람이 적었다. D나 E는 웰 노운 문제들을 꼬아 낸 문제라 적당한 시간에 적당히 풀린 것 같다.

대회 퀄리티가 아쉬운 부분이 많았는데, 검수진들 시험기간이다 뭐다 해서 일정 여유가 적었고, 애초에 기획단계에서 기간을 촉박하게 잡기도 해서 여러 부분에서 부족한 부분이 보였다. 문제만 좋다고 좋은 대회가 아니라는 것도 겪어 봤고 (문제가 좋은지를 차치하고서라도), 성공하면 늘지만 실패하면 반복하지 않는걸 배운것이라 생각해야겠다.

TODO.

다차원 초다포체 문제 만들기

대회 링크 :https://www.acmicpc.net/contest/view/1151

BOJ에서 첫 출제를 하게 되었는데 문제 선정에 제법 고민이 있었다. 가지고 있는 몇개 문제 중에 기하 문제를 출제하기로 결정했다. 사유는 여러 가지가 있겠지만 이번 문제를 제법 빠르게 내고 싶었다. 출제 마감 기한 전에 문제가 몇개 남아서 문제를 더 추가할까 생각도 했지만 검수진들이 들어오고 나서 보니 안 내길 잘한 것 같다. (14문제 8시간짜리 대회가 될거라고는 상상도 못했다.)

O. 이사하자!

사실 이 문제를 출제하게 된 배경은 약 9달 전 게시판에 쓴 글에서부터 출발한다.

이 문제 이후 문제 조건을 명확히 명시해야 한다고 많은 사람들에게 알려주고 싶었고 이 문제를 만들게 되었다. 3차원 이하의 공간에 직사각형(또는 직육면체)을 적절히 배치해서 어떻게 하는 문제를 출제하고 싶었고, 예전에 한 번 생각했던 직사각형 충돌 문제를 내기로 결정했다. 원래 문제에서 검색을 통해 쉽게 풀릴 수도 있다고 fs_edge님이 얘기해주셨고, 그렇게 수정해서 나온 문제가 이 문제이다. 원래 이 문제에는 정사각형의 각 모서리가 좌표축에 평행하지 않을 수 있다는 힌트가 없었는데, 출제/검수진 두 명이 낚였다. 한 분은 입력 데이터를 가지고 오셔서 "이 데이터는 정사각형이 아닌게 들어오는데요?"라고 하셨고, 한 분은 "~~~하면 CCW 없이 뚫리겠네요?"라고 하셨고 당연히 평행하지 않은 경우 반례가 나오는 풀이였다. 사실 이 부분은 힌트를 줄지 오래 고민해왔다. 그러던 와중에 검수진 한 분이 "악의적으로 받아들이는 참가자가 나올 수 있다"는 말을 해주셔서 좀 더 깊이 고민하게 됐는데, 결국은 1. 생각보다 긴 대회시간과 많은 문제, 2. 생각보다 높게 뽑힌 문제 난이도, 3. 이미 두분의 출제/검수진이 낚인 점을 고려해서 힌트를 넣기로 결정했다. (힌트를 추가했지만 검수진 한 분이 또 낚이셨다...)

대회 도중 계속 O번 제출 코드를 지켜봤는데, 보고 정렬로 해결한(...) 풀이는 정말 문제 입력 범위를 잘 판단해야한다는 것을 다시금 상기시켜줬다.

결국 대회 처음 공지했던 내용은 지켜지지 않았다.(...)

덕분에 첫 출제도 해보고 출제/검수 방법이나 다른 사람들의 풀이같은 곳에서 많이 배워 간 것 같다. (디스코드 사용법도 많이 배웠다.) 

https://www.acmicpc.net/problem/30300

풀이

요약하면, 배열에 x값을 AND 했을 때 MEX값이 최대가 되는 x를 찾는 문제이다.

MEX에 대해 잘 생각해보자. MEX값이 k이려면 k보다 작은 모든 자연수 k-1, k-2, ... , 1, 0이 모두 배열에 있어야 한다.

사실 생각해보면 0부터 차례대로 숫자를 채워 나가야 하는데, 배열 위의 각 수는 자신이 갖고 있던 비트만을 사용해야 하지 없던 비트를 만들어낼 수는 없다. 따라서 MEX가 1보다 크려면 최하위 비트가 0인 수와 1인 수가 모두 있어야 하고, MEX가 3보다 크려면 최하위 2비트가 00, 01, 10, 11인 수가 모두 있어야 하고, ... 과 같은 논리 전개가 가능하다. 대회 도중 이 시점에서 풀이를 작성해 AC를 받았다.

예를 들어 [1, 8]이 주어졌다고 하자. 이 자체로는 MEX가 0이지만 x=1을 AND해주면 8이 0의 자리를 채우면서 MEX값이 2가 된다. 즉, 상위 비트를 0으로 날리면서 0부터 순서대로 채우는 것으로 MEX를 크게 만드는 문제이다. 사실 0으로 날리지 않은 비트가 있다면 그 하위 모든 비트들은 0으로 만들어주면 안된다. AND로 0으로 만든 비트가 있다면 그 비트가 최상위비트가 되는 수가 배열에 존재하지 않게 되고, 그런 수 중 최소값이 MEX값의 상한이 된다. 따라서 AND를 통해 0으로 만든 비트가 있다면, 그 상위 비트에 관계 없이 MEX의 상한이 정해진다. 이때 최대한 많은 정수를 하위 비트들에 채워야 하므로 상위 비트를 0으로 만들어 AND를 통해 결정된 상한보다 작게 만들어 주는 것이 최적이다.

이를 통해 얻을 수 있는 로직은 아래와 같다.

1. 0부터 2^30보다 작은 모든 bit = (1<<i)-1 (0 ≤ i ≤ 30)를 순회한다.

2. bit를 각 배열 요소에 AND해주고 MEX를 구한다.

3. 이전까지 구한 MEX의 최대값보다 크다면 최대 MEX값을 갱신하고 bit값을 저장한다.

4. 순회가 끝난 뒤 최종 갱신된 bit값이 문제의 정답이다.

https://www.acmicpc.net/problem/30191

풀이

애드 혹 태그가 달린 문제답게 풀이도 코드도 간단했지만 풀이를 얻기까지 한두시간 고민했다.

실제 풀이에서 맨 처음 생각한 아이디어는 우선 문자의 쌍을 찾아야 한다는 것이다. 예를 들어 U를 입력하면 그에 대응되는 S가 어딘가에 존재한다. 이런 경우 누적 합을 통해 구간을 관리할 수 있다. BOJ1023(괄호 문자열)과 비슷한 맥락에서 두 부분문자열을 연결한 문자열도 동일하게 해결할 수 있으므로 반대로 원래 문자열을 문제의 조건을 만족하는 두 부분문자열로 컷 한 뒤 해결하는 방법을 생각해봤다.

우선 예제 입출력을 분석해보자. 예제 입출력에서 발견한 특징은 "정답 문자열 제일 끝에 불필요한 N이 붙어있다. 그것도 두개씩이나."였다. 

예제 출력을 따라가면 입력의 문자열을 "뒤에서부터" 구성한다는 것을 알 수 있었다. 예컨대 예제 입력 1은 SS로도 작성할 수 있지만, 뒤에서부터 작성하면  SNNS로 작성하게 된다.

실제로 뒤에서 부터 작성하려는 아이디어를 떠올렸을 때 문뜩 든 생각은 앞서 생각한 문자 쌍을 찾기 아주 쉽다는 것이다. 최소해를 찾는 경우가 아니기때문에 문자 쌍이 대응되는 것이 유일할 필요가 없고, 아무거나 적당히 문자 쌍을 대응시킬 수 있다면(풀이 과정 중의 해의 성질을 여전히 만족하는 이상), 대응시키면 된다. 실제로 이 시점에서 문제의 풀이가 완성되었고, 바로 코드를 작성해서 AC를 받았다. 물론 코드를 작성하는 과정에서 어림으로 계산했던 디테일을 잡아갔다.

일단 최초 상태를 빈 문자열 가장 뒤에 커서가 위치한 것으로 볼 수 있다. 가장 뒤의 문자가 S라고 가정하자. 이 문자는 자명하게 U를 입력해 나온 S여야 한다. 따라서 이 S와 대응되는 U가 앞선 문자열의 일부에 존재한다. 만약 이 이전 문자가 U라고 가정하면, 즉 가장 마지막 두 글자가 US라면 이 두 글자를 제외한 나머지 앞선 부분문자열은 본 알고리즘으로 풀 수 있다. 따라서 UNN을 시행하면 마지막 US를 오른쪽에 입력하고 나머지 문자열을 입력하기 위해 US를 제외한 나머지 빈 문자열 가장 뒤에 위치시킨 것과 같다. 다르게 말하면, US를 가장 오른쪽에 입력하고 나머지 부분문제를 풀기 위한 최초상태로 진입하는 것이다.

앞서 생각했던 괄호 문자열과 비슷하게 입력을 분석해보자. US, SU는 입력할 수 있는 문자열이다. 입력할 수 있는 두 문자열 S, T에 대해 ST도 입력할 수 있는 문자열이고, UTS, STU도 입력할 수 있는 문자열이다. 어떤 부분문자열 T를 입력하고 난 뒤 커서를 가장 왼쪽에 위치할 때 까지 N을 실행하고, 다시 부분문자열 S를 입력하면 ST를 출력할 수 있고, UN을 실행하고 T를 입력하면 UTS, SN을 실행하고 T를 입력하면 STU도 입력할 수 있다.

이 로직에서 커서를 우선 어떤 문자 왼쪽으로 이동시키고 나면 커서 오른쪽 문자열은 어떤 일이 있어도 수정될 수 없다. 따라서 커서 오른쪽 문자열을 입력마다 추적해보자. 커서의 위치를 C로 쓰자. UNUNNN의 경우 "USC" -> "UCS" -> "UUSCS"-> "UUCSS"-> "UCUSS" -> "CUUSS"와 같이 작성된다. 이때 N이 하나 추가될 때마다 커서가 한 칸 왼쪽으로 이동한다. 반대로, N이 하나 추가될 때마다 커서 오른쪽에 문자가 하나 추가된다. 우리가 원하는 로직이 문자를 입력한 뒤 커서를 이미 입력한 문자 왼쪽으로 보내는 것이기 때문에 N을 문자열 길이만큼 입력해야 한다.

실제로 이를 재귀로 실행할 필요는 없다. 두 부분문자열이 연속해서 등장하는 경우는 N을 출력해 커서의 위치를 이동한 뒤 출력하면 되고, STU, UTS의 경우는 UN(또는 SN)을 실행한 뒤 커서 왼쪽의 부분문자열을 보면 S(또는 U)가 하나 U(또는 S)보다 하나 많은 부분문자열이 된다. 이때 입력할 수 있는 문자열을 오른쪽부터 입력하고 난 뒤 S(또는 U)를 만난다면 가장 앞선 문자와 쌍을 이루는 문자라고 생각할 수 있으므로 N을 실행하면 UTS, STU의 문자열을 입력하고 커서를 왼쪽 끝으로 이동시킬 수 있다. 좀 더 자세히 얘기하자면, 오른쪽에서 왼쪽으로 훑으면서 커서 오른쪽의 문자열이 입력가능한 문자열일 때 처음 만난 문자와 대응되는 S<->U는 이 두 문자를 제외하고 입력가능한 문자열이 지난 후에 처음으로 나오는 대응되는 문자인 경우는 해가 된다.

설명이 길었는데, 실제 로직은 아래와 같이 해결된다.

1. 가장 오른쪽 문자부터 순서대로 확인한다. S에 1, U에 -1을 대응시키자. 오른쪽에서 왼쪽으로 이동하면서 문자열의 누적합을 구하자. 누적합이 0이라면 이전까지 탐색한 문자열이 입력가능한 문자열이라는 뜻이다. (문제 조건에서 해가 존재함을 증명가능하다고 서술했다.)

2. 현재 만난 문자가 S이고 누적합이 0 이상이라면 UN을 출력한다.

3. 현재 만난 문자가 U이고 누적합이 0 이하라면 SN을 출력한다.

4. 현재 만난 문자가 S이고 누적합이 음수이거나, 현재 만난 문자가 U이고 누적합이 양수라면 N을 출력한다.

이렇게 완성된 문자열은 N이 문자열 길이만큼 존재하고 문자열 길이의 절반만큼 U나 S를 입력해야 하므로 정확히 3/2N개의 길이가 된다.

뭐라 설명하기는 어렵지만 순서대로 따라가면 해가 되겠거니하는 생각은 쉽게 할 수 있을거라고 생각한다. 애드혹 문제들이 설명하거나 유도하는 과정을 말로 설명하기는 어렵지만 로직을 짰을 때 타당하다고 확인하기 쉬운 문제들인 것 같다.

https://www.acmicpc.net/problem/18185

관점을 바꿔서 어떤 공장에서 라면을 구매하는 가격을 책정하는 문제로 바꿔보자. 한 공장에서 라면을 구매하는 방법은 3원을 주고 구매하는 방법과 특정 조건이 만족되면 2원을 주고 구매하는 방법의 두 방법 뿐이다. 당연히 한 공장에서 라면을 구매하기 위해서는 2원에 구매할 수 있는만큼 구매하는 것이 최적해이다.
첫번째 공장에서는 이전 공장이 하나도 없으므로 무조건 3원에 라면을 모두 구매해야 한다. 따라서 유일한 방법인 3원에 모두 구매하는 것이 최적해이고, 이후에 다른 공장에서 구매하는 것과 관계없다. 두번째 공장에서는 최대 첫번째 공장에서 3원에 구매한 라면의 수만큼 2원에 구매할 수 있고, 나머지는 모두 3원에 구매해야 한다. 두번째 공장에서 3원에 구매했거나, 첫 번째 공장에서 3원에 구매한 것을 토대로 두 번째 공장에서 2원에 구매한 개수만큼 세 번째 공장에서 2원에 구매할 수 있다.
세 번째 공장 이후의 2원에 구매할 수 있는 라면의 최대 개수는 i번째 공장에 대해 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수가 된다.
좀더 일반적으로 두 번째 공장의 경우 i-2번째 공장에서 구매한 라면의 총 개수가 0이라 두면 동일한 계산이 되고, 첫 번째 공장도 i-1, i-2번째 공장에서 라면을 0개 구입한 것과 동일하다.

따라서 존재하지 않는 공장에서 구매한 개수를 0이라 강제하고 min(i-2번째 공장에서 3원에 구매한 라면 개수,i-1번째 공장에서 2원에 구매한 라면 개수)+i-1번째 공장에서 3원에 구매한 라면 개수를 이용해 DP를 돌리는 것으로 해결 가능하다.