이번에도 역시 소멤에 투고한 글. ----------------------------------------------------------------------------------------------- 본 글에서는 간선이 하나씩 추가됨에 따라 SCC를 관리하는 Incremental SCC를 오프라인으로 처리하는 방법에 대해서 설명하겠습니다. Link Cut Digraph 문제를 보겠습니다. 문제를 간단하게 요약하자면 $N$개의 정점이 있고 $M$개의 간선을 추가하는 쿼리가 있을 때, 간선을 추가할 때마다 u에서 v로 가는 경로가 있고, v에서 u로 가는 경로가 존재하는 (u, v)(u < v, u != v)쌍의 개수를 구하는 문제입니다. 방향 그래프에서 u에서 v로, v에서 u로 갈 수 있다는 것은 ..
삼성 소프트웨어 멤버십에 투고한 글. 본 글에는 차마 너무 저렴한 어휘라서 담지 못했지만 정말 날먹이 가능한(..) 기법인듯 하다. 뭔가 자료가 있는 것 같으면서도 PS에 관련된 자료는 전무한 거 같아서 (특히 한글은) 작성했다. 나도 뭐 어디서 검색해서 알게된 것은 아니고 NYPC 2019 예선 풀다가 찾은 풀이였는데 그 이후로도 종종 써먹어서 그냥 글로 작성했다. 본격적으로 시작 서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열..
예선 18등 -> 본선 7등으로 기가 막힌 상승 곡선을 그었다!! 예선 때 여러모로 망했던 요인들을 굉장히 많이 보완했다. 에디터를 코드 블럭에서 서브라임 텍스트로 바꾸고, 스테이플러를 이용하여 문제지 관리하고 서브라임 텍스트에서 코드를 바로 프린트할 수 있는 extension을 다운받아서 정말 알차게 뽑아 먹었다 ㅋㅋㅋㅋㅋ 대회 직전에 긴장 풀려고 이런 저런 얘기들을 많이 했는데, 그 때 목표를 10등으로 하고 학교 순위 4등이라도 하자.. 라는 이야기를 했다. 사실 카이스트와 숭실대 팀이 너무 강했기 때문에 월파에 대한 기대는 거의 0에 수렴했는데, ("마지막이니까 재밌게 합시다~!" 라는 말도 했다) 근데 어쩌다보니 결과가 너무 좋게 나와서 기분이 매우 좋다 ㅎㅎ 대회 전부터 이번 리저널에서의 관전..
10월 10일에 ICPC 예선이 있었는데 미루고 미루다가 지금 후기 쓴다. 풀이는 다른 블로그에 있으니 개인적으로 들었던 생각만 적고 본선 준비 다시 빡세게 하러 갈 예정이다. 우선 우리 팀은 1_Hoeaeng_2_Hawawang 이라는 팀명으로 참가했다. 하나하면 호에에엥 둘하면 하와와왕 팀명으로 어그로를 끌고 싶다는 내 의견이 강하게 반영된 팀명이다. 이게 오프라인이면 확실히 어그로 잘 끌렸을텐데 본선까지 온라인 대회로 바뀌면서 얼마나 끌릴지는 모르겠다. 사실 이 정도 난이도 셋에 우리 팀 실력이면 최소 8솔은 했어야 했을 거 같은데 여기저기에서 너무 말리면서 7솔에 패널티 잔뜩 먹고 그닥 좋진 않은 성적으로 예선을 마무리 했다. 우선 여태까지 팀연습을 컴퓨터를 3대로 하고 실제로는 코딩만 겹치지 않..
간단 후기 : 난이도 배치가 예년과 달라졌다. 작년까지는 1, 2번에서 거의 만점자 1000명씩 나왔는데 이번에는 2번 문제 보고 '헉' 소리가 나왔다. 그래도 전체적으로 문제가 재밌어서 좋다. 동방에서 SCPC 쳤는데 정말 집중이 하나도 안되는 분위기였지만... 그래도 어찌저찌 잘 했다 ㅋㅋㅋㅋㅋ 심지어 3번 풀고나서 밥먹고 오니까 누가 맥주까지 사오는 바람에.. 술 한 잔 했습니다.. UPD https://github.com/cheetose/SCPC2020/tree/master/1round 1차 예선 소스 공개 아무튼 풀이 1. 다이어트 더보기 $K$일 동안 밥을 먹는데 점심 $N$종류, 저녁 $N$종류의 식사 중 안겹치게 먹는다고 할 때 점심 칼로리 + 저녁 칼로리의 최대값을 최소화 하는 문제다. ..
요즘 맨날 OI 문제만 풀다보니까 머리가 빠르게 안돌아가고 코딩 속도가 상당히 느려짐을 느껴버렸다. 모 슬랙 덕분에 이 셋을 알게 됐고 solved.ac 기준 절반 이상이 플래티넘 수준의 문제라 스피드런 연습하기 좋아보인다고 판단해서 돌았다. https://codeforces.com/gym/102433 여기랑 https://www.acmicpc.net/category/detail/2131 여기에서 풀 수 있다. 결과는 9솔. B에서 말린 것과 추후에 설명할 서버폭파 코포가 코포함 만 아니었어도 패널티 관리는 매우 좋았을 수도..? 앞으로 쭉 나열할 타임라인에서 자세한 풀이는 안쓰고 문제를 풀면서 들었던 생각들을 적을 예정입니다만 강력한 힌트도 존재하기 때문에 접어두겠습니다. D - Dividing By ..
https://www.acmicpc.net/problem/15555 2018 일본 정올 기출문제로, 상당히 재밌는 문제다. 가장 먼저 할 수 있는 쉬운 관찰은 세로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없고, 가로 스틱끼리는 서로 무슨 일이 있어도 겹칠 수 없다는 것이다. 이를 이용해서 서로 겹치는 세로 스틱과 가로 스틱 쌍으로 이분 그래프를 만들 수 있고, 쾨니그 정리를 이용하면 쉽게 풀 수 있으나 정점의 수가 3000*3000이라 어림도 없다는 걸 바로 깨달았다. 여기서 하나의 관찰을 더 해야한다. 조금 더 쉽게하기 위해 중앙의 G를 기준으로 스틱을 판단해본다고 하자. 어떤 스틱의 G의 좌표가 $(i,j)$라고 하면, 이 스틱과 겹칠 수 있는 다른 스틱의 G의 좌표는 $(x,y), x+y=i+j..
지난주 알프스 내부대회에 이어 18, 19일 이틀간 숭고한 알고리즘 대회를 진행했다. 기도를 해야할 거 같은 굉장히 성스러워보이는 이름이지만 3년째 이어오고 있는 숭실대, 고려대, 한양대 연합 대회다. 지난 2년간은 알고리즘 캠프 4일 + 대회 1일로 이루어졌었는데 올해는 코로나로 인해 대회만 진행했다. 여기에서 문제를 풀어볼 수 있고 (코드포스), 지문 및 풀이는 여기에서 확인 가능하다. 내가 낸 문제는 Advanced I. 찾아라 드래곤볼!, Marathon J. 3N 투어링, Marathon M. 리그 오브 숭고한, 이렇게 총 3문제다. 찾아라 드래곤볼 문제는 대충 HLD와 Lazy propagation과 sparse table과 euler tour technique을 짬뽕시킨 희대의 쓰레기 문제다..
UCPC/ICPC 팀원 소개부터 하자면 cheetose / knon0501 / ryute 이렇게 3명으로 이루어져있다. 3명 모두 최근에 종강해서 거의 5개월 만에 모여서 잃어버린 ps감도 살릴 겸 팀연습을 돌기로 했다. 문제 셋은 그냥 적당히 연습하기 좋아보이는 셋인 SWERC2019로 골랐다. 셋은 https://codeforces.com/gym/102501 에서 확인 가능하다. 문제 읽기, 디버깅 등의 문제로 1인 1컴을 했지만 3인 1컴처럼 연습하기 위해 코딩이 겹치는 일은 없도록 했다. 결과적으로는 8솔을 했고 개인적으로 매우 불만족스럽지만 PS를 거의 2~3개월 안하고 한 상태라서 어쩔 수 없다는 생각을 했다. 한동안은 감 되살리는데 집중해야할 거 같다. I - Rats / cheetose /..