작년 7월 6일에 블로그를 처음 만들었었다. 처음에는 블로그에 PS하는거 기록하고 개발하는 얘기를 쓰려고 했었다. 물론 개발은 아직까지 하나도 안했고 주구장창 PS만 해버렸다.
선배들이 다 하나씩 블로그같은거 만들어 놨길래 ‘헉 나도 저런거 갖고 싶다..’라는 생각으로 이곳 저곳 다 뒤져보면서 겨우 겨우 만들어낸 블로그다. 카테고리도 원래 테마에 없었는데 여러개 찾아보고 힘겹게 만들었다. 심지어 그 당시에는 웹에 대해 아무것도 모르는 상태로 머리 박치기해서 만들어냄..
원래 블로그 테마 색을 민트로 해놨었다. 난 민트가 마음에 안들어서 여러번 바꾸려고 했는데, 색깔 바꾸는 걸 계속 실패해서 1년째 미뤄뒀다가 오늘 드디어 해냈다. 알고 보니까 깃헙 서버에 뭔가 반영이 느려서 색깔이 안된거였는데 무지하게 급한 성격인 나는 그걸 못참고 ‘아 안되네’ 하고 그냥 민트 그대로 뒀었다.
개인적으로 파란색 ~ 보라색 계열의 색을 좋아해서 보라색으로 바꿨다. 일단 지금은 약간 애매한 색감의 보라색인데 나중에 시간날 때 이쁜 색깔로 바꿔봐야겠다. 사실 오늘 보라색 바꾸는거 말고도 플러그인 몇 개 추가하고 이모지 쓸 수 있는 플러그인도 넣어서 되게 뿌듯함 ㅎ. 근데 이모지 알고보니까 win + . 써서 넣는 것도 되더라. 약간 허무했음. 좀 억울하니까 당분간 글 쓸때 이모지좀 쓰려고요 ㅇㅇ
이 블로그를 만들었을 시점이 아마 solved.ac 기준 골드5 짜리로 아무것도 모르는 뉴비였을 때다. 블로그 만들고 한달 정도 뒤에 플래를 찍고 이걸 지켜본건지 뭔지 잘 모르겠는데 얼마 안 있다가 “알로하 학술부 하실?” 하고 연락이 왔었다. 대략 1년이 지난 지금은 다이아4(2312)가 되었다.
사실 티어야 어느정도 수준 이상이면 그냥 지적 유희라고 생각하는데.. 그렇지만 다이아4정도면 적어도 최소한의 알고리즘 실력은 갖춘거 같아서 나름 뿌듯하긴 하다. 흔히 “웰노운”이라고 불리는 알고리즘들도 이제는 구현은 못해도 이름은 다 들어본 느낌이고, 뭔가 할 줄 아는건 그닥 많지 않지만, 머리에 지식은 많이 쌓인 듯 하다.
최근에 배운 것 중에서 가장 신기했던 알고리즘 하나를 뽑자면, 역시 Heavy-Light Decomposition이 아닐까? 트리를 체인으로 잘 분할해서 \(\scriptsize O(log N)\) 만에 어떤 경로에 대한 쿼리를 처리할 수 있다는 게 너무 신기했다. 다만, 처음부터 구현하라고 하면 아직은.. 못할 것 같긴 하다.
다른 공부는 죽어도 안하는 사람
알고리즘 말고 흥미가 생기는 분야가 그닥 많지가 않다. 원래 ML이 되게 하고 싶어서 혼자 공부하고 찍먹했었는데.. 끈기가 없기도 하구 뭔가 나랑 잘 안맞았다. (요새 ML 성과로 나오는 프로그램들 보면(코파일럿 같은거) ML 해야지 미래가 생길 것 같긴 함) 그래서, 작년에 Linear Regression하는 방법까지만 배우고 그냥 덮어뒀다. 누가 안시키면 잘 안하는 유형의 사람이라서 동아리라든지 스터디라든지 해야했었는데 그것마저 귀찮아서 안했다. 이렇게 보니까 진짜 노답이네.. 다음 학기에 HAI 들어갈 수 있으면 들어가봐야겠다.
겨울에 웹 공부랍시고 HTML + CSS만 배우고 그냥 가만히 뒀다. 그 조금이라도 한 덕에 이제 개발자 도구 켜서 이 태그가 뭘하고 저 속성이 뭔지 대충 이해할 수준은 됐다. 뭔가 배우면 배울수록 포토샵 노가다하는 기분이랑 동일한 그게.. 떠올라서 어느 순간부터 안했다. 다른 개발자분들이 프론트 개발하는걸 디코로 훔쳐보고 그랬는데 보면 볼수록 프론트 쪽은 나랑 안맞는 느낌이 강하게 드는 것 같다.
그래서, 이번 방학에 백엔드 쪽으로 뭔가 배워보려고 node.js를 하려고 시도했다! 플레인 js부터 배우고 간단한 프로젝트라도 해보려 했는데 js만 배우고 아무것도 안했다. 사실 ucpc 준비랍시고 알고리즘 문제 푸느라 안한거라 이제는 정말 해야겠다라고 느끼는 중. 노드로 서버 빌드하고 뭔가 만들어내는 선배님들 보면 진짜 짱 멋있다. 나도 해보고 싶음 ㅋㅋ 혹시 같이 배울사람 있으면 연락좀 해줘요.. 같이 하자 ㅎㅎ
지금은 알고리즘이 재밌어서 매일 주구장창 뭔가 배우고 풀고 하고 있는데, 맨날 이러고 사는거 아니냐고 과 동기가 팩트로 팼다. 아니 틀린말은 아니긴 한데 요새 너무 더워서 나가기도 싫어서 그런거임 아무튼 그럼. 이 날씨에 어떻게 여행을 가고 어떻게 운동을 하고 그럽니까?? 나는 일단 못함 ㅇㅇ
이런 블로그를 보는 사람이 있구나
그냥 PS기록용에 가깝게 쓰고 있었는데, 의외로 내 블로그를 보는 사람이 꽤 있었다. 풀이 글 보고 고맙다는 사람도 있었고, 어떻게 푸는지 더 물어보는 사람도 있었다. 웹에 뭔가 올리면 보는 사람이 생기긴 하는구나 라는걸 느끼는 순간 ㅋㅋㅋ 검색 실적에 어떤게 상위권인지 구경하는 것도 재밌더라. 글 캡쳐해서 들고오는 사람도 있었는데.. 그거 그렇게 들고오면 좀 부끄럽습니다. 보라고 올린 건 맞지만 여튼 막상 그러면 부끄러움.
블로그 글 쓰는거 처음엔 좀 어색했다. 글을 쓰는데 마크다운 문법도 알아야 했고, 이미지 삽입부터 어려운게 한 둘이 아니었다. 분명 글써서 야무지게 올렸는데 글이 안뜨는 이슈도 있었음. 서버 날짜보다 글 쓴 날짜가 더 빠르면 글 업데이트가 안됐던거였음(한국 시간대가 서버 시간대보다 빨라서 생기는 이슈). 여간 어색한게 한 둘이 아니였다. 근데, 이젠 이쪽으로 글 쓰는게 훨씬 편해졌다. 좀 성장했구나 나 새기..
좀 힘들었던 1학기
1학기 진짜 힘들었다. 진지하게 휴학하고 쉬고 싶었다. 뭐 때문인지 아직도 모르는데 우울증이 너무 심해져서 약 먹고 그랬다(의사선생님이 중등도 우울증과 고도 우울증 경계에 있다고 했었음.) 중간고사때가 젤 심했던 듯 대인기피 max에 리얼 아무것도 하기 싫었음. 하여튼 거의 5개월간 병원을 다녔는데 어찌저찌 잘 치료된건지 이젠 괜찮은 것 같다. 사실 병원 n개월 더 오라고 했는데 괜찮을 거라는 믿음으로 안가는 중.
딱히 말하고 다니진 않아서 모르는 사람이 더 많았을 건데, 여튼 어캐 버티고 학교 어캐 다녔는지는 아직도 잘 모르겠다. 중간에 학교 축제 안했으면 진짜 휴학했을지도 모름. 이제는 전혀 그런거 없고 예전의 평범했던 그 상태로 돌아온 느낌이다. 다행인듯.. 헤헤
이렇게 써놓으니까 뭔가 많이 한 것처럼 보이긴 하네요. 알고리즘 원툴인데 그 마저도 그리 잘 하는 느낌이 아니라 진짜 열심히 해야겠다고 매일 생각한다. 알고리즘 말고는 plane js배우고 go-lang 찍먹하고 sql도 찍먹하고 이것저것 건드려보기만 했다. 다른것도 좀 파서 프로젝트도 해보고 뭔갈 만들어내고 싶다. 되돌아보니 진짜 알고리즘만 한 것 같아서 살짝 후회되기도 하구 좀 아쉽다. 이제는 증말 딴 것도 할거야~~~
기타 배우고 싶어요
예전부터 락 밴드 노래들 엄청 좋아했는데 너바나라던가 오아시스라던가.. 하루종일 집에서 밴드 라이브 영상보면서 코드 짜다보니까 진짜 기타 배우고 싶어졌다. 요새 국카스텐 - Mandrake 거의 맨날 듣는데 진짜 기타 겁나 멋있음. 조만간 학교 근처에서 자취를 하게 될거 같은데 알바좀 해서 기타 사고 말겁니다.. 집에서 기타나 끄적일 생각에 벌써 재밌네 ㅋㅋㅋㅋ
만드레이크 기타 리프 칠 수 있을 때까지 배우고 싶음.. 라이브 영상볼때마다 보컬도 보컬인데 진짜 기타 뽕이 차올라서 안배울 수가 없습니다. 딱 기다려~~~~~
하여튼, \(\scriptsize N\)개 중 \(\scriptsize M\)개를 골라 합을 만들고 그 값들 중 소수만 골라 출력해주면 되는 문제다.
조합을 다 만들어주면 되니까, \(\scriptsize O(\binom{N}{M})\) 에 해결 가능하다. 조합을 만드는 건 DFS로 할 수 있다. 어떤 원소를 뽑으면 카운트를 증가시키고 아니면 증가시키지 않도록 해서 M개가 될 때까지 값을 만들면 쉽게 합을 구할 수 있다.
모든 합을 구하고 나서는 그 값들이 소수인지만 봐주면 되는데, 이거는 대략 10,000까지 소수를(왜냐면, 최대 9000까지만 값이 나올 수 있거든요) 전처리 해두면 쉽게 해줄 수 있다. 전처리하는 방법은 에라토스테네스의 체를 사용해서 구하면 된다. 소수 판정을 가르친적이 없어서 이걸 넣으면 안됐을 것 같긴 한데.. 멘토 멘티님들 똑똑하시니까 잘 하셨을거라 믿는다.
풀이가 어렵진 않은데.. 실수할 수 있는 부분이 하나 있다면, 소수인 합이 하나도 안나올 수 있으니 그 경우에 예외처리를 잘 해주자.
1번 노드부터 다른 모든 노드까지 거리를 구하면 풀 수 있다. 그래프 간선의 가중치가 모두 동일한 것으로 생각할 수 있으니까 거리는 BFS로 구할 수 있다. BFS로 1번노드로부터의 거리배열을 다 채워주자. 그런 이후 가장 먼 노드까지의 거리값을 가져온 뒤에 노드번호, 거리, 개수를 세어서 출력해주면 어렵지 않게 맞을 수 있다.
위 문제랑 이름만 같고 다른 문제다. 2번 문제는 다른분이 들고 오셨고 3번 문제는 내가 들고왔는데 모으고 나서 보니까 문제 이름이 같았던 우연..ㅎㅎ
문제 내용은 다른데 풀이는 비슷하다.
좌표를 전부 하나하나 노드로 봐주면 그래프 문제로 바뀐다. 헉! 그러면, 가중치가 같은 그래프 상에서 최단거리를 찾는 문제가 된다. 이는 마찬가지로 BFS로 해결할 수 있으니, 거리 배열을 만들고 다 채워넣어주자. BFS 종료 이후 K 인덱스 값에 접근해서 거리 값을 확인해 출력해주면 된다.
DSLR 연산을 구현하고 A를 B로 변환하는 가장 빠른 명령어를 아무거나 하나 출력하는 문제다. 음.. 일단 이것도 마찬가지로 숫자 하나하나를 노드로 보면 그래프 문제로 바뀌고, 각 연산 또한 전부 가중치가 같은 간선으로 봐줄 수 있다. 즉, 가중치가 모두 동일한 그래프 상에서 최단거리를 찾고 최단거리를 만든 명령어를 역추적하는 문제다.
최단거리 찾는건 어찌저찌 할 수 있겠는데요.. 명령어는 어떻게 해야하죠? 가 사실 이 문제의 핵심이다. 나는 큐에 노드 번호뿐만 아니라, 명령어도 같이 삽입해서 B에 도달하면 해당 명령어를 출력하도록 했다.
한번, 탐색할 때마다 BFS로 10,000개의 노드만 보면 되니까 시간내에 잘 돌아갈거라 짐작할 수 있고 믿음을 가진채로 구현을 하면 AC를 받을 수 있다.
구현이 좀 난잡한데 여러분들은 이것보다 훨씬 간단하게 짤 수 있으니까 아이디어만 얻어가길 바랍니다 ㅎㅎ
벽을 안부수고 이동한다면 그냥 평범한 BFS 문제다. 그런데… 벽을 하나 부술 수 있다고 한다. 그럼, BFS 돌다가 벽 만나면 해당 벽을 부순셈 치고 계속 BFS를 돌면 될까?
그렇게 쉽게는 안풀린다. 왜냐면 벽을 부수기 전과 벽을 부순 이후의 상태공간이 동일하지 않아서 그렇다. 벽을 부순 이후에는 아예 다른 공간이라서 방문체크도 새로 해줘야 한다. 벽을 부숨으로 경우의 수가 달라져 버린다고 생각하면 이해가 되려나? 예제를 몇개 직접 그려보면 내 얘기가 무슨 얘기인지 알 수 있을 것이다.
따라서, 벽을 부수기 전과 부순 이후의 상태공간이 달라서 방문 체크를 아예 새로 해줘야한다. 거리로 부순 이후로 새로 구해야 하고, 이런식으로 구한 값들을 모아서 최종적으로 한번 벽을 부수고 이동한 거리와 부수지 않고 이동한 거리를 서로 비교해 작은걸 출력해주면 된다. 부숴도 끝까지 못 이동하면 그건 -1을 출력해주면 된다.
자세한 이해는 코드를 보는게 편할 듯.. 이 문제에서는 벽을 한 번만 부수지만 이 원리를 확장시키면 벽 n개 부수는걸로도 확장할 수 있다.
숫자말고 변수로 한 번 생각해보자. 예제로 설명을 해보자면, 수식 트리를 잘 따라가서 식을 정리하면, a - b + c - d + e 처럼 뭔가 부호가 붙어 있는 식으로 나온다. 양수는 양수끼리 음수는 음수끼리 정리한다고 치면, (a + c + e) - (d + e) 처럼 정리 가능 하다. 그럼 그리디하게 앞에는 큰 수들을 넣고 뒤엔 작은 수를 넣으면 항상 값이 최대가 된다. 헉! 이제 문제가 바꼈다. 중요한 건 마이너스 부호가 붙은 노드의 개수이니 그 개수만을 알아오면 된다.
트리를 잘 쳐다보자. 마이너스 연산자의 오른쪽 자식은 변수의 부호가 바뀐다. 왼쪽 자식은 그대로다. 플러스 연산자는 부호가 안바뀐다. 이건 DFS로 잘 구현하면 된다. 부호가 바뀔 때만 주의해서, 리프 노드에 도달하면 해당 부호를 반영해주고 DFS를 완료하면 음수 개수를 카운팅하자.
오름차순으로 정렬해서 카운팅한 갯수만큼은 \(\scriptsize neg\)에 더하고, 나머지는 \(\scriptsize pos\)에 더한 뒤 \(\scriptsize pos - neg\)를 출력하면 된다.
끔찍한 길이의 HLD + 끔찍한 길이의 lazy prop 을 짜면 맞출 수 있는 문제다. 나는 코드길이가 8225byte(..)나 나왔다. 먼저, 오일러 투어 테크닉으로 서브트리에 대한 정보를 얻어두자. \(\scriptsize v\)를 루트로 하는 서브트리의 시작을 \(\scriptsize in[v]\)라고 하고, 끝을 \(\scriptsize out[v]\)라고 생각하자.
1번 쿼리는 \(\scriptsize in[x]\)에서 \(\scriptsize out[x]\)까지 V를 더하면 된다. 다들 잘 알고 있는 구간에 값을 더하는 쿼리다.
2번 쿼리는 경로에다가 값을 더하는 쿼리다. 이는 HLD로 해결해줄 수 있다. HLD로 해당 경로에다가 구간 값 업데이트 쿼리를 날려주면 된다.
3, 4번은 나중에 생각해보고 5, 6번을 먼저 보자.
5번 쿼리는 \(\scriptsize in[x]\)에서 \(\scriptsize out[x]\)까지 구간 합 쿼리를 처리해 출력해주면 된다.
6번 쿼리는 마찬가지로 HLD를 사용해 경로 위에서 값을 잘 얻어와줘서 출력하면 된다.
3, 4번 쿼리가 문제인데.. 얘네는 좀 복잡하다. 그냥 막 구간에 값을 곱한다고 바로 나오는게 아니라서 조금 생각을 해봐야 한다. \(\scriptsize (a, b)\)를 해당 노드에서 \(\scriptsize a\)만큼 곱하고 \(\scriptsize b\)만큼 더하는 lazy값이라고 생각해보자. 초기 lazy값은 다 \(\scriptsize (1, 0)\)이어야 함이 자명하다.
어떤 구간에 \(\scriptsize u\)가 곱해지고 \(\scriptsize v\)가 더해지는 쿼리가 들어왔다고 해보자. 그럼 \(\scriptsize (u, 0)\)이 되었다가 \(\scriptsize (u, v)\)가 되는게 자명하다. 그냥 그렇게 처리해주면 된다. 반면, 순서가 반대로 되면 조금 달라진다.
이번엔 반대로 어떤 구간에 \(\scriptsize v\)가 더해지고 \(\scriptsize u\)가 곱해지는 쿼리가 들어왔다고 해보자. 그러면, \(\scriptsize (1, v)\)가 되었다가 \(\scriptsize (u, uv)\)가 되어야 한다. 왜냐하면, 리프 노드값이 \(\scriptsize a\)라고 했을 때, \(\scriptsize a + v\) 에서 \(\scriptsize (a + v) \cdot u\)가 되기 때문이다. 즉, 더해지는 값이 uv가 된다. 그래서 합에 대한 레이지 값에도 \(\scriptsize u\)를 곱해줘야 하는 것이다.
흠.. 그러면 lazy를 어떻게 짜면 될까? 먼저 곱에 대한 propagate를 해주고 합에 대한 propagate를 해주면 된다. 그 이후 위의 내용을 적용시켜서 노드를 잘 업데이트 해주면 된다.
propagate_prod();propagate_add();//현재 노드 업데이트//레이지 값 업데이트
느낌으로 짜주면 된다. 곱셈 update와 propagate에서는 합 lazy에 값을 곱하는 것을
잊지 않고 이리저리 잘 짜주면 된다. \(\scriptsize v\)를 곱하는 업데이트 함수를 짜라면 아래처럼 짜면 된다.
흠.. 그럼 이제 레이지도 다 짰고, 각 쿼리에서 뭘 해야할 지 알았으니 그대로 구현을 해주면 된다. \(\scriptsize 2^{32}\)로 나눈 나머지를 구해야하기 때문에 나머지 연산을 잘 적용시켜서 풀면 된다.
.
.
.
.
.
.
라고 생각했지만, 그렇게 naive하게 풀면 정확하게 4퍼센트에서 WA를 받는다.
아마 보통 long long으로 세그먼트 트리의 노드를 관리할텐데 mod값이 너무 큰 나머지 곱해서 long long 범위를 초과할 수 있다. 헉! 무슨 뜬금없는 소리인가.. 그래서, 어떻게 해야하냐면 unsigned long long으로 모조리 고치던가 아니면, 그냥 unsigned int를 쓰는것으로 해결할 수 있다. 전자는 쉽게 이해가 갈꺼지만, 후자는 무슨 소리일까?
unsigned int에서 오버플로우가 나면 마치 \(\scriptsize 2^{32}\)로 mod값을 취한 효과가 발생한다. 헉.. 누가 이런 발상을 한대요? 진짜 무슨 생각으로 낸건지 궁금해진다. (아무리 생각해도 내 풀이가 맞아서 게시글을 봤는데 무려 이런 내용이;; ㅋㅋㅋㅋ __int128 써야할줄 알았는데 그건 아니였고 uint나 ull로 충분했다는 사실..) 그래서 mod값 처리할 필요없이 그냥 unsigned int로 다 처리해주면 AC를 받을 수 있다.
로프 하나만 있으면 해당 로프가 버티는 최대 중량값이 답이다. 두개 이상이 되면 (버틸 수 있는 최대 중량의 min값 * 로프 개수)가 해당 로프들이 버틸 수 있는 최대 중량임을 쉽게 알 수 있다. 알고싶은 것은 N개의 로프가 주어질 때, 로프를 잘 써서 버틸 수 있는 최대 중량값이다.
그리디하게 접근하자. 먼저 로프가 버틸 수 있는 최대 중량 값을 기준으로 내림차순 정렬한다. 앞에서부터 로프를 하나씩 추가해가며 로프들이 버틸 수 있는 max값을 찾아주면 쉽게 답을 찾을 수 있다.
완전탐색으로 풀리는 문제다. d진법 숫자가 한번 씩 모두 등장하는 수를 다 보려면 \(\scriptsize O(d!)\)이다. d개의 숫자를 나열하는 경우의 수랑 같기 때문이다. 따라서, 순열을 만드는 함수를 작성하면 되고 만든 수가 N보다 큰 지 확인하고 그 수들 중 min값을 저장해놓으면 된다.
태그에 백트래킹이 있는데 왜 있는지는 모르겠다. 그냥 완전탐색으로 쉽게 풀린다. Naive하게 시키는걸 구현해도 풀린다. N이 작아서 벡터에 현재 에너지 구슬을 뺀 나머지를 새로 다 넣고 전달해서 풀면 된다. 그런 뒤 찾아낸 값들 중에서 max를 리턴하도록 하면 답이 구해진다.
N이 20으로 작다는 점에 주목하자. S로 만들 수 있는 부분 수열을 모두 만들어보면 된다. 각 원소가 있다 없다로 생각하면 2가지 경우의 수만 생기므로, 탐색해야할 경우의 수는 \(\scriptsize O(2^{N})\)가지이다.
이때, N이 최대 20인데 \(\scriptsize 2^{20}\)은 백만 정도니까 충분히 시간내에 풀린다. 각 원소를 선택하고 안하고 하면서 모든 경우를 만들어주자. 그런 다음, 만들어질 수 있는 합에다가 체크하고 모든 체크가 다 끝나면 해당 배열에서 mex(Minimum EXcluded)값을 찾아주면 된다.
뭔가 순서가 중요할 것 같지만 사실 그렇지 않다는 걸 캐치하면 풀 수 있는 문제다. 1만큼 성장하는 물뿌리개의 사용횟수와 2만큼 성장하는 물뿌리개의 사용횟수가 항상 동일해야한다. 홀수 높이만큼 성장하려면 1만큼 성장하는 물뿌리개가 필수이다. 따라서, 모든 높이를 훑어보고 홀수이면 1의 사용횟수를 증가시킨다. 2의 사용횟수는 높이를 2로 나눈 몫이다. 이렇게 하면 (2의 사용횟수) > (1의 사용횟수)가 되는데, 이때, 2 = 1 + 1이라는 점을 이용해 2를 하나 감소시키고 1을 두개 증가시키며 사용횟수가 같아질 수 있는 지 보면 된다.
그리디한 전략을 생각해내면 풀 수 있는데.. 쉽진 않다. 먼저, 양수 좌표에만 가져다 놔야 할 책이 있다고 쳐보자. 역순으로 생각하면 조금 쉬운데, 일단 가장 먼 거리에 있는 것은 마지막에 가져다 줘야지 다시 0으로 돌아오지 않을 수 있다는 걸 알 수 있다. 마지막에 있는걸 가져다 놓는 김에 그 전에 있는 책 M - 1개도 다 가져다 주면, 0으로 되돌아 오지 않고 최소 거리로 움직일 수 있다.
마지막 책들을 가져다 놓기 전에 그 책들 이전 위치에는 다 책이 놓여 있어야 한다. 마지막 이전에 M개의 책이 놓였다는 사실을 알 수 있고, 그전에도 M개가 놓였을 것이다. 그러다가, M개보다 적게 놓여야할 위치가 있음을 알게 되는데 고걸 잘 처리해주면 된다.
그럼 양수 음수 좌표가 둘다 있으면요? 가장 먼 곳에 있는 좌표가 음수일 지 양수일 지 모르니까 둘 중에 절댓값이 더 큰쪽이 마지막이 되면 된다. 책 가져다 놓는건 양수만 있을 때랑 동일한 전략을 적용하면 된다. 단지 방향만 반대라 두 방향 모두 다 구해주면 된다.
마지막 처리가 좀 어려울 수 있는데, 모든 거리를 다 구해 더한 다음 절댓값 MAX를 빼주면 된다. 무슨 소리인지 이해가 어려울 수 있는데 코드를 보는게 이해가 빠를 듯!
이분탐색이 분할정복인가..? 는 잘 모르겠는데 살짝 변형된 이분탐색으로 풀 수 있다. \(\scriptsize A[x]\)를 가져올 때, B에서는 \(\scriptsize B[N - x]\)를 가져오면 된다. 그리고 그 두 값을 비교해서 작은 값이 있는 쪽의 인덱스 범위를 키우면 된다. 그러면 앞에서부터 N번째 값을 찾아낼 수 있다.
요걸 이분탐색으로 구해주면 된다. l = 1, r = N으로 두고 위 논리를 적용시켜서 mid값으로 질의를 던져서 얻어낸 값으로 범위를 조절하자. 질의가 하필 40번인 이유는 \(\scriptsize O(log(2^{19}))\)번 각각 배열에 질의를 하고 마지막에 N번째 값이 무엇인지 찾으려고 2번 더 해야해서 그렇다.
아이디어 자체는 그리 어렵지 않은데.. 한번에 맞기 좀 어려운 문제다. 범위 조절하고 N번째 값이 무엇인지 좀 생각해야할게 많은데 잘 생각해서 풀면 되긴함.
코드 보기
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<int,int>;usingppii=pair<int,pii>;intmain(){ios_base::sync_with_stdio(false);intN;cin>>N;intsa=1,ea=N;intsb=1,eb=N;intf,g,ma,mb;while(sa!=ea&&sb!=eb){ma=(sa+ea)/2;mb=(sb+eb)/2;cout<<"? A "<<ma<<endl;cin>>f;cout<<"? B "<<mb<<endl;cin>>g;if(f<g){sa=ma+1;eb=mb;}else{ea=ma;sb=mb+1;}}cout<<"? A "<<sa<<endl;cin>>f;cout<<"? B "<<sb<<endl;cin>>g;cout<<"! "<<min(f,g)<<endl;return0;}
원래는 알로하 부회장님, 다른 학술부원님이랑 같이 나가기로 했는데, 부회장님이 몰입캠프를 가버리시는 바람에 팀이 분해됐다. 그 뒤로 그냥 가만히 있다가 UCPC 팀 어떡하지?? 이런 생각이 들 때, 연진이 누나(yjinpark)가 같이 팀하자고 연락을 해줬다. 두명이서 다른 한명을 더 찾으려고 했는데, 둘 다 못구해서 내가 그냥 친구인 서진이(sj1226m)한테 같이 나가자고 했다. 너무 고맙게도 무슨 대회인지 잘 모르는데도 불구하구 같이 나가준다고 해서 그렇게 UCPC팀이 꾸려졌다.
어찌저찌 예선을 마무리하고 운이 좋게도 본선에 진출하게 됐다. 난 오프라인 대회가 그냥 처음이었던지라 너무 설렜다. 본선에서 뭐라도 풀어보겠다고 급하게 Mo’s랑 FFT같은거 열심히 풀어봤고(사실 의미는 없었..다..ㅋㅋ) 요상한 2차원 짜리 FFT도 풀었다. FFT가 자주 나왔길래 그걸 열심히 팠는데 본선엔 내가 못 풀 난이도로 나와서 의미가 없었던..ㅎ (심지어 본선 문제 하나 보자마자 NTT 쓰는거인걸 알았는데 알아도 못풀 난이도였음)
근데 왜 노란색 옷….??
본선 대회 장소에 도착하니까 노란색 옷을 입고 있는 사람들이 한가득 있었다. 저게 본선 티셔츠인걸 부정하고 싶었지만, 어림없지 ㅋㅋ 그게 우리가 입어야할 티셔츠였다. 사이즈가 좀 작게 나와서 끼는 느낌이 있었지만 뭐 그래도 대회 온 느낌도 나고 좋았다. 책상 위에 놓인 봉투 뜯어보니까 solved.ac 별조각 쿠폰이랑 한별이 스티커가 있었다(둘 다 랜덤).
생각치도 못한 게 들어있으니까 좀 웃기고 어이없긴 했다. 등록하고 좀 앉아 있으니까 갑자기 11시 5분에 대회가 시작된다고 했다. 사전 유의사항 그런거 알려주고 시작할 줄 알았는데 그런거 없이 그냥 자연스럽게 진행하라고 해서 좀 당황스러웠다. 11시 ~ 16시가 진짜 대회 시간인줄은 상상도 못하고 있었는데, 그렇게 5시간동안의 대회가 시작됐다.
왜 쉽지?
누나가 문제 읽으면서 이거 쉬운데? 하면서 막 풀어냈다. 작년 본선 난이도를 생각하고 와서.. 3문제 푸는게 사실 목표였는데 의외로 한문제가 빨리 풀려서 신기했다. 그러다가 누나가 또 이거 그냥 그리디인데? 하더니 막 풀어와줬다. 갑자기 2솔브가 되더니 20등대가 되서 “오 이게 뭐지? 이게 선배미..?” 이러고 있었다. 나는 J번 보고 풀이 한 번 잘못 구상해서 코드 한 번 갈아엎고 제대로 풀이 짜와서 AC 받았다. 그때가 대회 시작 1시간정도 되는 시점이었다. 한 시간만에 목표 달성하고 재밌다~~ 이러고 그 뒤로 뭔가 쭉 막혔다.
어림없지 바로 하드모드
서진이가 K번을 읽고 이거 풀만해보인다면서 나한테 문제지를 넘겨줬다. 엄청 열심히 써놓구 설명도 해주길래 할만해보이네~ 싶어서 조금 읽다가 감이 안잡혀서 난 다른 문제를 잡았다. 그리구 K번은 연진이 누나가 보고 나는 F번을 봤다. K번을 본 누나가 뭔가 복잡해보이는 풀이를 보여주더니 그걸 계속 풀고 보여주고 반복했다 ㅋㅋㅋ. F번을 읽는데 N도 의미심장하게 500,000으로 엄청 크고 약간 그리디스럽게 풀리지 않을까 싶어서 서진이랑 같이 문제를 봤다. 어쩌다 보니 문제지 자체를 넘겨주고 나는 D번을 풀려고 봤다. 누가봐도 레이지 세그 문제라서 어떻게 잘 하면 풀리지 않을까 하고 수식 정리를 시도했다. 잘 줄여봐도 뭔가 가중치가 앞에 붙는채로 레이지하게 업데이트해야하는 풀이밖에 안 떠올랐다. 가중치가 앞에 붙어서 lazy prop 자체가 그냥 안되서 멍 때리고 있었더니, 서진이가 엄청 그럴듯한 F번 풀이를 가져와서 설명해줬다.
앞에서부터 보면서 카드를 매칭시키는데, 이미 쓴 카드가 나오면 현재까지 진행한 카운트와 \(\scriptsize \lceil \frac{K}{2} \rceil\)을 비교해서, 카운트가 크거나 같으면 지금 들고 있는 카드를 모두 버리고 가져온 셈 치는 풀이였다. 두 장씩 다 버린다고 치면, \(\scriptsize \lceil \frac{K}{2} \rceil\)번 버리면 카드가 다 비니까, 중복된 카드를 먹기 위해서 그냥 버린걸로 생각하는 풀이였다.
엄청 그럴듯 해 보이지 않나요? 난 진짜 맞는 풀이 같아서 조금 더 나은 풀이를 만들어 냈구 (실제로 카드를 버리는게 아니라 set을 활용해서 set에 넣는 걸로 중복 체크) 시간 복잡도도 \(\scriptsize O(NlogK)\)로 진짜 될 것만 같았다.
배고프길래 서브웨이 준거 먹고 코드 짜기로 했다. 그 와중에 누나가 진짜 세상 열심히 K번 코드를 짜고 고치고 하길래 구경했는데, 뭔가 잘 안되는 것 같았다. 밥 다먹구 노트북 가져가서 서진이가 내 코드 훈수두는 식으로 코드를 같이 짰다 ㅋㅋㅋㅋ. 이런 저런 구현 실수 때문에 조금 오래 걸려서 코드가 만들어졌는데, 예제도 잘 나오고 뭔가 될 것만 같은 기분이 들어서 떨리는 마음으로 제출했다.
1퍼 돌아가자마자 터졌다. 이때가 제일 아쉬웠다 ㅠㅜ. 잘 생각해보니 몬스터가 안나오는 턴이 좀 문제가 될 수 있었고, 그걸 살짝 억지로 고쳐보는 로직을 추가해서 제출해도 역시나 WA를 받았다. 이때가 거의 3~4시간이 흐른 시점이었고, 나는 다시 D번을 보고 누나는 여전히 K번과의 사투를 하고 있었다.
K번 풀이는 뭘까?
D번을 보다가 도저히 식 정리가 안되서 포기하니, 서진이가 G번을 들고와서 이거 쉬워보인다구 했다. 뭔가 나름대로 식도 적혀있길래 문제를 읽고 들어줬다. 그때까지만 해도 G번 푼 팀이 거의 없어서 나는 어려운 문제인게 딱 감이 왔는데.. 혹시? 하는 생각으로 풀이를 들었다. 둘이서 보다가 순서가 있다는 사실을 놓쳐서 쉬운 문제인것처럼 보였을 뿐 아쉽게도 ㅠㅠㅠ 어려운 문제가 맞았다. 그래서, 그냥 K번을 보기로 했다. 이왕 본선왔는데 4솔은 해야할 거 같아서… 여튼 누나가 풀이를 설명해주는걸 딱 듣고 있었는데 언젠가부터 살짝 흐름도 놓치고 약간 풀이가 장황해지길래 뭔가 정해가 아닌 것 같다는 생각을 했다.
그래서, 나도 문제를 보고 다른 풀이를 떠올려봤다. 나는 a가 b를 이기는 걸 방향 그래프로 만들어서 트리 2개를 만들고 그걸 잘 보고.. 어떻게하면 원래 트리 모양이 나올 지를 생각했다. 왠지 그냥 트리 높이랑 자식 개수로 잘 합치면 답이 나올 것 같아서 누나한테 이걸로 풀어보는거 어떰? 하고 제안을 했는데 누나가 “나 못믿음?” 시전하길래 10분 정도 더 기다려줬다. 누나가 열심히 완성한 코드가 WA를 받길래 얼른 내 풀이를 실행으로 옮겼다. 대회 종료 30분 남은 시점이라서 엄청 급하게 짰는데, 어떻게 예제 답을 낼 수 있었고 제출을 하기 전에 누나가 만든 테케를 넣어보니 답이 안나왔다. 너무 아쉬웠다. 끝나기 전까지 고쳤지만 결국엔 WA만 더 쌓고 끝났다. 아래는 대회 종료 직후 슬픈 내 WA코드..
나중에 해설 들어보니 누나 풀이가 정해였고.. 내가 짠 풀이는 소개해주지도 않았다. 누나 약간 옆에서 억울해했음ㅋㅋㅋㅋ 쏘리.. 다른 팀 얘기 들어보니까 나랑 비슷하게 트리 어찌저찌 잘 합치는 풀이로 AC받았다는 거 같은데 왜 나는 안됨 ㅋㅋ
끝나버린 첫 본선
그렇게 본선이 끝났다. 그 이후로 후원사 홍보 세션, 수상 세션이 있었고.. 피곤했던 우리팀은 엎드려서 자다가 박수치고 자다가 박수치고 ㅋㅋㅋㅋㅋ 그러다가 사진 찍으려고 앞에 나갔다가 사람이 너무 많아서 뒤로 잠시 갔는데 그 사이에 벌써 사진을 찍었길래 그대로 퇴장했다. 티셔츠가 볼만했으면 같이 사진이라도 찍을 걸 그랬는데.. 티셔츠가 너무 노란색에 안 이뻐서 그냥 벗고 그대로 집으로 갔다.
본선에서 얻은건.. 본선 티셔츠, 후원사 티셔츠 (좋은 잠옷)랑 몰로코 굿즈였다. 개인적으로 몰로코 굿즈가 좀 이쁜 것 같다. 파란색 노트 좀 힙해서 좋은듯. 여튼, 5시간 동안 대회해본 것도 처음이고 오프라인 대회도 처음이라 재밌었다. 비록 3솔로 끝났지만, 다음번엔 더 나은 결과를 기대해볼 수 있지 않을까..ㅎ?
연습이랑 예선, 본선까지 멀리서부터 계속 와준 문서진씨 너무 고마웠고 덕분에 좋은 추억 쌓은 듯! 같이 팀하자고 해준 연진 누나도 짱 고맙고 사실 우리팀 버스기사였기에 너무 멋있었다 선배미 폭발 ㄹㅇ 두 사람 다 엄청 수고많았음!
