본선대비 연습 1, 2, 3일차

포기했던 본선에 예상치 못하게 올라가게 되가지고 최대한 PS에 시간을 투자하고 있다. 

1일차는 선린 가을맞이 알고리즘 대회 셋이 있길래 이걸 3시간 잡고 돌았다. 

Celebrity는 이전에 비슷한 문제에서 비트마스킹 써서 그래프 나타내는 풀이를 몰랐다면 시간 내에 못풀고 저기서 막혔을거 같다. 구름다리 같이 서로 다른 걸 고르는 게 루트개 이하로 떨어진다는 걸 사용하는 풀이는 이제 많이 익숙해진거 같다.

 

2일차는 구사과님 run@kaist 연습 게시글을 토대로 셋을 짜고 외계 미생물이란 문제를 풀었다.

네시간 잡고 돌렸는데 D에서 트리 DP 생각하다가 시간을 많이 쓰고 마지막엔 C를 쭉 고민하다가 끝났다. C는 x축에 수직인 직선을 그으면 만나는 원이 얼마 안된다는 것이 제일 중요한 관찰이었다. 문제는 이걸 하고도 원이 겹칠 수 있다는 조건을 내 맘대로 만들어놓고 허우적댔다. G는 꽤 생각하기 어려운 DP였다. DP인건 명확히 보였고 M이 작은 걸 보면 이걸 잘 써서 상태수를 줄여야 하는 거였는데 정렬해서 고르는 순서를 강요할 수 있었다. 꽤 자주 나오는 사고방식이다. 잊지 말자. H는 결국 숫자 안 겹치게 잘 골라서 세우는 거라는 거기 때문에 숫자를 정점, 직사각형을 간선으로 생각한 다음에 간선에 방향을 줘서 정점 별 outdegree를 1이하로 만드는 과정을 수행해야 한다. 무조건 답이 있는 입력이 주어진다는 걸 컴포넌트가 하나인 입력이라고 해석해서 한 번 틀렸다. D는 모르겠다... 검역소였나 맛집 추천이었나가 비슷한 느낌의 문제였던거 같은데 그것도 어렵다.

외계 미생물은 PS란 걸 해본적도 없을 때 교내 대회에서 봤던 어려운 문제로 기억한다. 갑자기 이걸 왜 풀었는지는 모르는데 문제 풀이 설명하는 걸 이해도 못했었는데 금방 푸는 걸 보면 역시 하면 어느정도 되나보다. 문제 자체는 전형적인 DP.

3일차는 시간을 잡고 풀진 않고 구사과님 셋 2개 + 문제 한개 박고 쭉 돌았다. 그리고 앳코더 비기너 223 버츄얼을 한번 돌렸다. 여기서 괄호 문자열 문제를 세그로 풀어가지고 백준에도 괄호문자열과 쿼리란 문제가 있었던 거 같아서 풀었다. 

A 13분에 풀고 B를 141분에 푼 게 보이는가.... 투포인터 구현이 안되가지고 이걸 2시간 넘게 잡고 있었다. 큰일이다 정말

B의 여파인지 C도 간단한 브루트 포스 문제를 구현에 오래 걸림 + 시간 초과로 굉장히 시간을 많이 썼다. D는 예제 안 보고 문제만 본다음 풀이 나와서 코드 짰다가 예제가 내 생각이랑 달라서 한참을 멈춰 있었다. 문제를 제대로 읽지 않았다는 걸 보여준다. 문제 자체는 재밌는 문제다. 정점이 N개 간선이 N-1개 있을 때 그래프 별로 케이스워크 해서 푸는 문제였다. 

E는 그 전날에 보고 모르겠어서 셋에 넣었다. 이것도 케이스워크로 풀었다. 엄밀한 증명 없이 풀긴 했는데 충분히 맞는 거 같아서 냈다. 케이스가 r이 LCA(u, v)의 서브트리에 존재하냐 없냐로 나뉘는데 만약 r이 없다면 LCA(u, v)가 쿼리의 답이 된다. 이건 당연하다. 그러면 이제 r이 LCA(u, v)의 서브트리 안에 있을 때인데 LCA(r, u), LCA(r, v) 이 둘 중에 r에 가까운 애가 답이 된다. 왜냐면 어차피 r, u, v가 LCA(u, v)의 서브트리에 존재하기 때문에 둘 중 하나가 답이 될 거고 더 r에 더 가까운 애가 u, v의 common ancester가 될거라는 추측이었다.

H는 입력을 그래프로 보는 게 중요했다. 레이팅 별로 랭킹을 계산하고 순위 i, i+1을 간선으로 놓고 여기서 DFS 돌리면 된다. F는 진짜 못하는 구성적 문제다. 100만과 2000이라는 숫자에 집중하면 1000*1000=100만 이므로 1000이 1000개, 1이 1000개 있으면 전부 나타낼 수 있다. I는 기하라 업솔빙을 안할 거 같다. 어렵다. 풀이도 모르겠다. G는 오늘 해야지요

앳코더는 지금보니 F를 74분에 풀었는데 E를 25분동안 못풀었네요... 문제 보자마자 뇌정지 와서 던졌나 25분 있었으면 풀었야 할 문제였던거 같은데 왜 못풀었는지 복기를 해야한다. 아마 소인수 분해 쪽으로 생각을 처음에 잡았는데 이걸 빠르게 못버리고 간단한 방법부터 시도해볼 생각을 해야 했다. 3개니까 2개부터 푼다든가 일단 한 변을 전부 쓴다든가 하는 방식 말이다.