1/7 ~ 1/17동안 IOI 겨울학교가 있었다. 이번 겨울학교는 여름학교 때보다 뭔가 동기(?) 같은게 더 강해져서 더 열심히 했다. 결과적으로 이번 겨울학교에서 실력도 꽤 늘었고, 얻어간 것도 많았다고 생각한다. 그래서 PS에 대한 동기가 어느 때보다 강해졌다. 올해는 이걸 시작으로 진짜 열심히 해야겠다고 생각이 들었다.
아래는 1월 사이에 한 것들을 대충 정리하였다. 1차 선발고사는 따로 글을 쓸 것 같긴 한데.. 2차 치고 나서 묶어서 쓸수도 있고 모르겠다.
1. IOI 겨울학교 계속반
겨울학교 계속반에서는 SCPC, ICPC, OI 기출을 랜덤하게? 줬다. IOI'17의 Nowruz, Ancient Books를 제외하고는 모두 업솔빙했으며, Ancient Books는 아마 나중에 업솔빙하지 않을까 싶다. Nowruz는 적당히 긁는 건 쉬운데 왜 긁히는지도 모르겠고 만점은 그냥 모르겠다. 휴리스틱으로 뚫는건지..
1일차 (1/7)
scpc 문제들은 codeground에서 볼 수 있다. 년도는 직접 계산한거라 오류가 있을 수 있다.
SCPC 2018(4회) 본선 - 우주정거장2
작업의 형태를 보면 결국 삼각형을 떼어내는 형태임을 알 수 있다. 어떤 그래프의 최초 구성이 정점 2개와 간선 1개로 이루어진 트리일 때 이 그래프를 Triangle Tree라고 하자. 정의에 의해 주어진 그래프가 Triangle Tree일때는 답이 자명하게 |E|(간선 개수)이다. 그렇지 않으면 이 그래프는 절대 지울 수 없는 코어에 Triangle Tree가 달려 있는 형태의 그래프가 된다. 또한 이 때 코어와 Triangle Tree에 걸쳐 있는 정점은 단절점이 되므로 Triangle Tree 각각을 결국 간선 하나로 수렴시킬 수 있다. 또한 이 때 작업을 통해 간선 1개만을 남길 수 있을 것이고 그 경우의 수는 결국 Triangle Tree에 걸치는 단절점이 Triangle Tree만 남겼을 때 가지는 degree와 같다. 따라서 이 값들을 모두 곱해주면 된다. 구현은 직접 지워가면서 하면 되는데, 지우는 순서를 이상하게 하면 degree 값이 꼬일 수 있으니 주의하자.
SCPC 2021(7회) 본선 - 산탄총 2
먼저 좌표를 45도 돌리자. 그럼 결국 중심을 기준으로 1,2,...,k칸씩 떨어진 정사각형 합이 X 이하인지를 빠르게 판별하면 된다. 배열의 값이 양수여서 k에 단조성이 있으므로 k의 최댓값을 찾는다고 생각해보자. 그럼 결국 중심이 일정한 길이 1,3,...,2k-1의 정사각형 합을 O(1)에 구할 수 있는지 묻는 문제이다. 2차원 누적합 및 2차원 누적합에 대한 대각선 1차원 누적합을 관리하면 O(1)에 구해줄 수 있으므로 O(N^2logN) 정도에 풀린다.
하지만 이 문제의 진짜 난관은 구현이다. 인덱스가 범위 밖으로 나가는 등의 처리를 정확히 해야 AC를 받을 수 있다. 나는 이런 구현을 진짜 못해서 이 문제에만 5시간 정도 썼다. 난이도랑 별개로 다시는 풀고 싶지 않다.
SCPC 2021(7회) 예선 - No Cycle
앞 간선부터 주어진 방향성대로 줬을 때 사이클이 생길 수밖에 없다면 반대로 주고, 그렇지 않으면 그대로 방향성을 준다. 이 전략은 똑같은 문제를 K번 푸는거라서 정당하다는 것을 알 수 있다.
SCPC 2021(7회) 예선 - 패턴 매칭
BOJ 25008에서 매칭하는 문자열이 K개가 된 문제이다. (K개의 패턴 길이의 합 <= 30000)
먼저 BOJ 25008의 풀이부터 알아보자. '='의 정의를 바꿔서 kmp를 하면 되는데, 자기 앞에 있으면서 문자가 같은 가장 뒷 위치를 dist라는 배열로 관리하자. 이 dist와의 거리가 일치할 때(또는 둘 다 문자열 범위 밖일 때)를 '='로 정의한 후 kmp를 돌리면 된다.
그래서 결국 이 문제를 풀려면 BOJ 25008을 아호코라식으로 풀면 된다.아호코라식? 처음반 때 대충 보고 까먹었다.. 그래서 다시 찾아봤는데 내 기억에 비해서 꽤 간단한 알고리즘이었다. 그래서 그냥 여기서 정의만 바꿔서 해주면 되는데, 아호코라식 이해도가 부족해서 애를 좀 먹었다. trie의 각 정점의 depth를 저장해놓고 failure link를 타고 갈 때 dist를 갱신해줘야 하는데 꽤 어려웠다. 그래도 이 문제 덕분에 아호코라식 이해도는 많이 늘었다.
+) 이 문제와 비슷하지만 '='의 정의가 좀 더 어려운 대신 아호코라식을 안 써도 되는 문제가 BOJ에 몇 개 있다. ex)BOJ 3308 / BOJ 20298. 3308은 안 풀었다.
2일차 (1/8)
COCI 2019/2020 Contest #3 - Sob
B 집합에서 m부터 보면서 (n-1)&(m+i) = n-1을 만족하면 {n-i-1,...,n-1}과 {m,...,m+i}를 쭉 매칭시킨 후 A에서 n-i-1 ~ n-1을, B에서 m ~ m+i를 지운다. 이렇게 지운 새로운 집합을 고려할 때 집합의 크기를 줄이면서 같은 문제를 푸는 형태가 만들어지므로 정당한 전략이 된다. (사실 끝까지 매칭 불가능한 경우에 어떻게 되는지는 잘 모르겠다. A 집합이 0부터 시작해서 무조건 되는건가?)
ICPC Seould Nationalwide Internet Competition 2020 G - Hotspots
난이도를 모르고 선입견 없이 보면 꽤 직관적인 dp로 보이지만 그렇지 않다. 이 문제의 핵심은 반지름으로 가능한 후보를 O(N)개로 줄이는 것이다. 이게 가능한 이유는 결국 넓이가 제곱식이라 반지름은 maximal하게 하는것이 최적일텐데, 이게 결국에 자기 양 옆의 반지름 상태에서 오는 것이고 그걸 따라가다 보면 근원지가 나올텐데 그 근원지가 O(N)개라 그렇다. (라고 생각하고 풀었다. 꽤 직관적이지만 엄밀한 증명은 모르겠다)
그래서 전처리를 통해 반지름 후보를 구해주면 O(N^2) dp를 풀 수 있다. 아마 구현할 때는 귀찮아서 map 박고 O(N^2logN)으로 했던 것 같다.
ICPC Asia Regional Daejeon 2014 G - Road Repair
BOJ에서는 채점 준비 중이 걸려있다.
어떤 정점을 지나는 모든 경로를 고려할 수 있으면 좋을 것 같다. 따라서 센트로이드 분할을 때리고 트리dp 비슷한 짓을 해보자. IOI'11 Race처럼 센트로이드를 시작점으로 서브트리로 내려가면서 어떤 비용으로 먹을 수 있는 최대 가치 같은걸 관리하면서 합쳐주는데, 이걸 빨리 찾아야 되니까 lower bound가 되도록 계단을 관리해주면 된다.
ICPC 2023 Seoul Regional A - Apricot Seeds
진짜 진짜 어려웠다..
쿼리가 엄청 무섭게 생겼다. 이 문제를 풀려면 일단 bubble sort를 k번 진행했을 때 상태를 잘 관찰해야 한다. 일단 원하는 건 [l,r] 합이니까 [1,r] - [1,l-1] 꼴로 바꾸고 [1,x] 구간의 합을 구한다고 생각하고 bubble sort를 k번 했을 때 합의 상태를 관찰해보면 결국 그 구간에서의 최소 원소 n-k+1개의 합이라는 걸 알 수 있다. 증명은 min heap을 이용해서 k번째 bubble sort 결과를 구하는 과정에서 나온다고 한다.
그래서 결국 구간을 한정했을 때 그 구간에서 최소 원소 몇 개의 합을 빠르게 구할 수 있으면 되는데, 이건 PST로 풀 수 있다. IOI'14 holiday 풀 때도 쓰는 테크닉이다.
3일차 (1/9)
SCPC 2020(6회) 예선 - 우범 지역
이 점이 convex hull에 안 들어갈 확률을 구하자. 결국 이건 점을 기준으로 나머지 점들을 봤을 때 이루는 도형이 180도 안에 들어오는 것과 같다. 따라서 어떤 직선에 대해 한쪽에 쏠려있는 형태가 되며, 이건 각 점을 기준으로 투포인터 + 세그먼트 트리로 확률을 쭉 곱해주는 형태로 구해줄 수 있다.
Seoul Nationalwide Internet Competition 2023 E - Paper Folding
여러분들이 생각하는 그 풀이가 맞습니다.. 기하를 못해서 6시간 걸림
2024 ICPC Asia Seoul Regional F - Pair Sorting
제한이 0.7n^2인 이유는 모르겠다. 그냥 정렬이 안된 가장 큰 수를 뒤로 끌고 올 때, 2개 중 더 작은 수와 swap하는 걸 반복하는 그리디가 성립한다. 이건 진짜 왜인지 모르겠지만 local에서 n <= 100까지 다 돌길래 PBA했다.
Seoul Nationalwide Internet Competition 2022 J - Rectangles
x좌표가 같은 점들을 하나의 그룹이라고 하면, 두 그룹의 교집합 크기를 빨리 구해야 한다. 뭔가 자료구조로 풀려고 하면 쉽지 않다. n <= 70000이라는 이상한 제한에서 루트 풀이를 생각해볼 수 있다. 그룹의 크기가 B 이하인 그룹과 B 초과인 그룹으로 나누자. B 초과인 그룹과 그 밖의 그룹에 대해서는 그룹의 개수 자체가 N/B 이하이므로 naive하게 세주면 O(N*N/B)에 셀 수 있다. 이제 남은건 B 이하인 그룹끼리 세주는 것이다. 이 경우 그룹당 O(B^2)에 선분을 싹 훑어줄 수 있으므로 같은 선분의 개수를 std::map 등으로 카운트하면 O(NB^2logN) 정도에 풀 수 있다. 이제 B = sqrt(N) 정도로 잡아주면 무난하게 풀린다.
4일차 (1/10)
SCPC 2022(8회) 예선 - 지우개
한 문자를 기준으로 보는게 편하니 b는 공백이라고 치고 a만 남기자. 인접한 a 사이 거리를 그 사이에 있던 b의 개수로 정의하면 이 개수를 담은 sequence를 만들 수 있다. 이렇게 X에서 만든 sequence를 x, Y에서 만든 sequence를 y라고 하자. X->Y가 가능할 조건은 결국,
(1) y[1...|y|-2] = x[k...k+|y|-3] (0-indexed, 0 < k < |x|-|y|+2)
(2) x[0...k-1] 합 >= y[0], x[k+|y|-2...|x|-1] 합 >= y[|y|-1]
이어야 한다. 이건 kmp로 (1)을 만족하는 구간을 찾은 후 (2)를 prefix sum으로 판정해줄 수 있다.
SCPC 2024(10회) 예선 - 딱 맞게
max(F(A,B))에 영향을 주는 원소 쌍을 1개로 고정하고, 나머지를 최소화하는 전략을 생각할 수 있다.
일단 F(A,B)를 최소화하는 방법을 생각해보면, A[i]와 B[i]를 매칭해주면 된다. 그렇지 않고 swap을 하면 반드시 교차하게 되어 손해를 본다.
이제 파라메트릭 서치를 하자. 답이 x 이하라고 가정하고, A[i]에서 A[i]+x 이하인 최대 B의 위치를 찾아 매칭시키자. 그리고 이 둘을 제거한 A', B'에서 F(A',B')를 최소화했을 때 x 이하라면 답은 yes가 된다. 이걸 모든 i에 대해서, 또한 B[i]에서 A[i]+x로 가는 경우까지 고려해서 판단해주면 된다. min(F(A',B')) 매칭은 세그먼트 트리를 이용하면 O(logN)에 해줄 수 있다. 따라서 O(Nlog^2N)에 풀 수 있다.
SCPC 2022(8회) 예선 - 독립
조건이 되게 좋다. '.'에서 출발해서 항상 끝까지 갈 수 있기 때문에 '#'의 배치가 꽤 규칙적이게 나온다. 이제 (x,y)에서 시작하는 경로에 대해 다음과 같은 전략을 생각하자.
1. 최대한 아래로 간다
2. 최대한 오른쪽으로 간다
그럼 (x,y)에서 독립인 칸의 개수는 이 두 경로 사이에 없는 칸의 개수이다. 이건 prefix sum 등으로 잘 세줄 수 있다. 그냥 counting을 열심히 해주는 다른 풀이가 있지만 이 풀이가 가장 깔끔한 것 같다.
SCPC 2022(8회) 예선 - ABC
K != -1인 경우는 간단한 dp로 해줄 수 있다. 재귀로 짜면 간단하게 짤 수 있다.
K = -1인 경우는 SCC로 묶은 후 한 SCC에 A,B,C 간선이 모두 있는지 확인하고, 그렇지 않으면 비슷한 dp로 해주면 된다.
SCPC 2022(8회) 본선 - 돌무더기 게임
일단 O(N^3)를 고려해볼 수 있다. dp[i][j] := [i..j]에서 얻을 수 있는 최대 돌의 수로 정의하면,
dp[i][j] = max(i<=k<=j) (min(dp[i][k-1],dp[k+1][j]) + A[k])
라는 점화식이 나오고, O(N^3)에 풀 수 있다.
이걸 O(N^2logN) 내지는 O(N^2)으로 최적화해야 한다. 여기서 우리는 dp의 정의에 따라 dp[i][j] <= dp[i-1][j], dp[i][j] <= dp[i][j+1]임을 알 수 있고, 따라서 min(dp[i][k-1],dp[k+1][j])라는 식에서 dp[i][k-1] 부분은 단조증가하고, dp[k+1][j] 부분은 단조감소한다는 사실을 알 수 있다. 따라서 min에서 둘 중 어느쪽이 나올지는 특정 k를 기준으로 나뉘며, 이 k를 이분 탐색으로 찾아주면 min을 풀 수 있다. 이제 min을 푼 두 식의 구간 최댓값을 O(1)에 구할 수 있게 전처리해두면, O(N^2logN)에 풀 수 있다.
5일차 (1/13)
IOI 2017 Day 1 - Nowruz (BOJ : Nowruz 1 ~ 10)
상술했듯이 모르겠다. 여기서는 총합 75점 정도를 긁은 방법을 설명한다.
결국 리프노드의 수를 최대화한다고 생각해볼 수 있다. 대충 중앙을 잡은 후, 정점이 1개인 트리로 시작하여 4방향으로 새롭게 리프노드를 추가할 수 있으면 추가한다. 이걸 불가능할 때까지 반복하면 적당히 많은 수의 리프 노드를 얻을 수 있다. 놀랍게도 Nowruz 1은 만점을 받고 나머지는 7~8점 정도가 나온다.
수 (Hard)와 거의 동일한 문제이다. 핵심은 매칭 중에서 의미를 둘 매칭을 생각해보는 것이다. 그러면 의미를 두지 않은 매칭은 그냥 가장 가까운 위치로 매칭시켜주면 된다. R과 B를 하나의 배열로 병합해서 오름차순으로 넘버링하자. dp[i] := i번째 위치까지 보았을 때 최소 매칭 비용이라고 정의하면, i를 의미없는 매칭으로 매칭하는 경우와 의미있는 매칭으로 매칭하는 경우로 나뉜다. 의미없는 매칭의 경우 그냥 제일 가까운 위치를 cost로 해서 계산하면 되고, 의미있는 매칭의 경우 R과 B 사이의 원소 몇개를 동시에 매칭시켜줄 건데, 이 때를 j~i라고 하면 이 사이에 있는 R 개수와 B 개수가 같아야 한다. 따라서 이러한 j 중 최댓값만 관리해주면 거리도 절댓값이니까 prefix sum으로 O(1)에 계산할 수 있고, 결과적으로 dp를 선형로그 정도에 계산할 수 있다. 개인적으로 발상도 발상이지만 구현도 어려웠다. (이건 나만 그런듯..)
방향을 잘못 잡으면 영원히 못 풀 문제 같다. 섭태랑 정해도 별로 관련이 없는 것 같다. 충전역 정점 집합을 C라고 하자. 만약 A 관점에서 B의 동작과 관계 없이 모든 정점을 최종적으로 C 중 하나에 도달시킬 수 있다면 A가 모든 정점에 대해 승리한다. 그렇지 않으면, "A 관점에서 최종적으로 C 중 하나에 도달할 수 있는 정점 집합"을 S라고 하자. 또한 S의 여집합을 T라고 하고 "B 관점에서 최종적으로 A가 어떻게 하든 T 중 하나에 도달할 수 있는 정점 집합"을 X라고 하면, X에 속하는 위치에서는 무조건 B가 이긴다. 이제 전체집합에서 X에 속하는 모든 정점을 지우고 재귀적으로 문제를 해결할 수 있다.
6일차 (1/14)
가장 쉬운 셋이었다.
SCPC 2022(8회) 예선 - 수열 연산
k 미만인 가장 왼쪽 원소부터 가장 오른쪽 원소까지는 반드시 포함해야 하며, 당연히 그때 비용도 최소이다. 이제 이 왼쪽 원소와 오른쪽 원소 중 하나가 k 이상이 될때까지 구간 합을 취해주면 되고, 이건 레이지 세그로 할 수 있다. 아마 세그 안써도 구간에 똑같은 수를 계속 더해나가기 때문에 변수 하나만 관리하면 풀 수 있을 것이다.
ICPC WF 2018 F - Go with the Flow
일단 나는 O(80N^2)이 되는 줄 몰랐다.. TL 12초를 문제 풀고 봤다.
암튼 정해는 그냥 가능한 모든 width를 보면서 하던데, 내 풀이도 width 대부분을 보긴 하지만 의미있는(뭔가 변화가 있는) width만 본다. 대신 set을 썼기에 로그가 하나 붙는다. 이걸 관리하려면 그냥 덱 여러개를 관리하면서 width는 decremental하게 줄이면서 어차피 text가 옮겨가는 건 항상 back의 원소가 다음 행의 front로 가는 거기 때문에 O(1)에 해줄 수 있다. 대신 행 그룹마다 여러가지 원소를 잘 관리해야 한다.
암튼 저런거 없어도 TL은 문제 푸는 데에 충분하다. 결국 핵심은 여기서 강을 찾는건데, 이건 행마다 자기 윗 행을 보면서 투포인터 + dp로 해줄 수 있다.
SCPC 2023(9회) 예선 - 타이젠 윷놀이
윷놀이 구현이 귀찮다.. 암튼 생각해보면 결국 똑같은 짓을 K번 반복하는 건데, 결국 정점이 30개 정도 되기 때문에 30번 반복 안에는 같은 state가 올 수밖에 없고, 그렇게 같은 state에 오면 그 사이클을 쭉 타면서 최대한 K에 가까워질때까지 사이클을 돌린다. 그럼 또 naive하게 된다. 대충 O(60N) 정도?
7일차 (1/15)
ICPC WF 2019 E - Dead-End Detector
dead end 보고 소실부터 생각남먼저 트리의 경우를 생각해보면, 그냥 리프노드에 쭉 달아주면 되고 그게 최소이다.
그렇지 않으면 BCC 느낌으로 보면 코어 묶음이 하나 있고 거기에 트리가 달려있는 형태일텐데, 그렇게 트리로 가는 엣지에 1개씩 달아주면 된다. 개인적으로 문제 서술이 좀 모호했던 것 같다.
SCPC 2021(7회) 본선 - 1등 단어
문제 조건을 만족하는 저런 단어를 lyndon word라고 한다고 한다. 그건 잘 모르겠고 암튼 저러한 단어의 조건을 살펴보면, 첫 문자 뒤에 나오는 문자는 자기보다 사전순으로 크거나, 같은 경우에는 끝까지 쭉 비교했을 때 결국은 자기보다 사전순으로 커야 한다. 그래서 이 조건을 그냥 case work로 구현해줘도 되고(이거 많이 귀찮다.) 아니면 그냥 suffix array에서 첫 원소 찾고 지우는 거 반복해도 풀린다. suffix array 까먹었는데 공부해야겠다고 느꼈다. 최근 suffix automaton 글을 읽고 좀 귀찮아 보여서 미루고 있었는데 이거라도 공부해야하나
SCPC 2020(6회) 예선 - 범위 안의 숫자
문제가 무서워 보이지만 k <= 9를 보면 갑자기 자신감이 생긴다. 그냥 naive하게 바꿔본다음 점 업데이트 구간 쿼리 <=> 구간 업데이트 점 쿼리로 바꾸는 세그만 쓰면 된다. 근데 다이나믹 세그 쓰면 MLE고 좌압해야한다. 다이나믹 세그는 짤때마다 TLE/MLE가 나는 것 같다. 이걸로 뭔가 푼 기억이 없다.
8일차 (1/16)
ICPC Asia Regional Seoul 2020 D - Electric Vehicle
일단 최단경로로 생각해보자. dist[i][j][k] := i번 위치에서 j만큼의 연료를 가지고 k번 충전했을 때 지금까지의 최소 비용으로 정의하면 당연히 TLE가 난다. 여기서 크게 2개 정도를 추가로 관찰해야 한다.
1. 거리가 manhattan distance로 정의되므로 삼각부등식을 만족한다. 이는 곧 내가 가고싶은 위치가 있는데 쓸데없는 위치를 방문하면 절대 이득이 될 수 없다는 뜻이다. 여기서 굉장히 중요한 사실이 유도되는데, 바로 충전을 하지 않을 위치는 방문한다고 생각하지 않아도 된다. 충전을 하지 않을 거라면 들를 이유가 없기 때문이다. 따라서 M <= 10 제한을 이용하면 결국 최대 10번정도 이동해서 도착지점까지 가는 문제라고 생각할 수 있다.
2. 각 위치에서 가능한 용량은 O(N)개이다. u->v로 간다고 했을 때, u에서는 결국 꽉 채우거나, v로 딱 맞게 갈수 있는 만큼만 채우거나 둘 중 하나만 하면 되기 때문이다. 이게 가능한 이유는 v의 충전 비용이 u보다 비싸다면 당연히 꽉 채우는 것이 이득이고, 그렇지 않다면 당연히 v에서 채워야 하기 때문이다. (1번 관찰에 의해 당연히 v에서는 충전을 해야 한다.)
이제 거꾸로 생각해보면, 어떤 정점 v로 들어올 때 가능한 용량은 결국 W - dist(u,v) 꼴이고 u가 O(N)개이므로 가능한 용량도 O(N)개이다.
이제 구현만 하면 되는데, 상태가 대충 O(N^2)개고 M번 반복하므로 O(N^2M)이지만, state를 계단으로 관리하면서 의미 없는 state를 제거해주면 꽤 많이 상태가 날아가서 꽤 넉넉하게 돌아간다. 근데 BOJ가 느린건지 BIKO에서는 빨리 도는데 BOJ는 간신히 통과했다.
Seoul Nationalwide Internet Competition 2020 D - Coronavirus Trend
꽤 정의가 무섭게 생겼는데, 런 길이가 3 이상이기만 하면 되서 LIS를 세그로 푸는 느낌의 dp를 생각할 수 있다.
dp[i][j][k] := i까지 (증가, 감소) 덩어리를 k개 이어붙였을 때 최대 길이(k는 3 이하로 bound)
이러면 구간 최댓값을 빠르게 찾으면 최적화 가능한 식이 나오므로 좌압 + dp를 관리하는 세그로 풀 수 있다.
Seoul Nationalwide Internet Competition 2019 E - Choreography
문제 서술이 무섭지만 천천히 생각하면 풀 수 있다. 생각해보면 사람 간의 위치 관계는 절대 바꿀 수 없기 떄문에 가야 하는 위치가 고정되어 있고, 만약 갈 수 있다면 겹치지 않게만 옮겨주면 되므로 그냥 가능한 사람을 어떻게든 옮겨주면 된다. 옮겨줄 때 방향성이 고정이므로 최대한 끝쪽 선분으로 옮겨주면 된다.
ICPC Asia Regional Seould 2021 J - Squid Game
수올 문제라고 한다. 그냥 이 풀이가 어떻게 나왔는지도 모르겠다. 그래서 설명할 자신도 없으니 신의 블로그를 보도록 하자.
여담으로 친구가 DLAS로 이 문제를 푼 거 같은데 이건 또 이거대로 모르겠다. DLAS가 뭔데
9일차 (1/17)
Day 1보다는 쉽다고 생각한다.
IOI 2017 Day 2 - The Big Prize
일단 90점은 쉽다. 사탕의 제외한 상품의 개수가 O(sqrt(N))개이므로 사탕의 위치를 모두 구하면 된다. 이건 질문을 날리면서 이분 탐색으로 연속하면서 maximal한 사탕 그룹을 구해줄 수 있고, 이러한 사탕 그룹 또한 O(sqrt(N))개이므로 O(sqrt(N)logN) 정도의 질문을 날리면 된다. 한 8000개 정도 질문을 쓰는 것 같다.
97점 정도를 맞으려면 더러운 최적화를 해야 한다. 버킷질을 할건데, 그룹 크기는 474 정도로 잡고 각 그룹마다 사탕이 아닌 위치를 찾으면 된다. 그룹 크기가 512 미만이므로 9번이면 이분탐색으로 찾을 수 있고, 총 4700~4800 정도의 질문을 쓸 것이다. 여기서 전처리에 쓰는 값이 좀 커서 한 5200개의 질문을 쓸텐데, 이걸 더럽게 좀 최적화하면 99.xx점이 나오고 여기서 더 더럽게 최적화하면 100점이 나온다.
풀이 자체는 재미있었다. (=구현이 더럽다) 일단 51점은 그렇게 어렵지 않은데, 정해랑 크게 관련이 없는 풀이로 풀어서 생략한다. (잘 기억도 안나고..)
풀이는 크게 두 파트로 나뉜다.
(1) 아무 스패닝 트리나 잡고, 이 스패닝 트리의 왕의 길에 대한 정보를 O(N)번 정도에 구한다.
(2) 스패닝 트리 밖의 back edge들을 총 NlogN번 정도에 구한다.
일단 단절선은 무조건 왕의 길이다. 그렇지 않으면 애초에 스패닝 트리를 못잡는다.
일단 아무 스패닝 트리나 잡고 이때의 count 리턴 값을 x라고 하자. 또한 이때 트리 간선 집합을 E라고 하자.
단절선이 아니라면 각 edge는 자기 위로 가는 back edge가 있을 것이다. 만약 back edge가 왕의 길인지 여부를 안다면, back edge 사이에 있는 트리 간선에 대해서, E에서 각 트리 간선을 지우고 back edge를 추가한 다음 count 리턴 값을 x와 비교하여 왕의 길인지 여부를 알 수 있다. 이 경우 사용하는 쿼리 수는 N개를 넘지 않는다.
만약 back edge도 모른다고 하자. 이 경우에도 알 수 있는데, 일단 위와 비슷하게 각 간선을 지우고 back edge로 대신한 후 쿼리를 날리자. 이때의 리턴 값을 순서대로 모아둔 배열을 y라고 하자.
(i)y의 원소가 모두 일치하지 않는 경우: y[i] 값이 작았던 간선이 왕의 길이고, 작지 않은 간선은 왕의 길이 아니다. back edge도 x와 비교하면 구할 수 있다.
(ii)모두 일치하는 경우: 이 경우 x-1로 같거나, x로 같거나, x+1로 같다. x-1인 경우는 back edge는 왕의 길이 아니고, 모든 트리 간선은 왕의 길이다. x+1인 경우는 back edge는 왕의 길이고, 모든 트리 간선은 왕의 길이 아니다.
x인 경우는 back edge와 트리 간선의 속성이 같은 경우인데, 이 경우 모두 왕의 길이 아니다. 그렇지 않으면 사이클이 생기기 때문이다.
이렇게 질문하면 O(N)번의 질문으로 스패닝 트리에 속하는 모든 간선의 왕의 길 여부를 알 수 있다. 이제 이걸 토대로 남은 back edge들을 NlogN번 만에 구할 수 있다. 핵심은 정점을 고정하고, 그 정점에서 뻗어나가는 back edge들의 왕의 길 여부를 이분 탐색으로 구할 것이다. 이건 쿼리가 count이므로, back edge를 순서대로 넘버링한 후 [0..k]까지 질문했을 때 count 값이 변했는지 여부를 통해 왕의 길이 존재하는 가장 왼쪽 위치를 알 수 있고, 왕의 길은 N-1개이므로 이분탐색에서 쓰는 질문도 최대 (N-1)logN 정도에 비례하기 때문에 가능하다.
구현이 정말 힘들다.
IOI 2017 Day 2 - Ancient Books
상술했듯이 업솔빙을 안 했다. 이런 문제 싫어..
2. CF/Atcoder
이번 겨울학교를 통해 실력이 꽤 상승한 것은 확실히 체감이 된다. 하지만 코포는 최근에 친 라운드는 오히려 최근 실적 중 최악의 퍼포를 내면서(블루) 점수가 더 떨어졌다. 분명 나와 비슷한 실력대의 사람들은 오렌지를 다 갔는데 왜 나만 몇개월째 못가고 있는가.. 라는 느낌이 들 수밖에 없었다. 하지만 내가 간과한게 있었다. 분명 코포/앳코더는 일반적인 백준/oi와는 그 문제 스타일이 다르고, 시간도 2시간~3시간 정도로 짧은 편이다. 또한 oi와는 다르게 문제를 푸는 속도가 점수에 반영되므로 느긋하게 문제를 보면 망한다. 그리고 나는 최근에 이 감을 아예 잃어버린 것 같다. 특히 수학/애드혹 문제를 푸는 감을 많이 잃어버렸다. 이건 뭐 애초에 수학을 못하는 것도 있지만, 문제를 너무 어렵게 생각하는 느낌이 강해진 것 같다. 여기까지가 최근에 버추얼/실제 라운드를 겪어보면서 느낀 점이다.
그래서 결론은 그냥 경험을 많이 해야 한다는 것이다. 그래서 최근 며칠 동안은 버추얼을 돌렸고, 그 과정에서 내가 얼마나 못하는지를 알 수 있었다.
이 라운드 참가 안하길 정말 잘했다.
A
더럽다. 정사각형끼리 겹칠때 제거되는 부분을 빼주면 된다.
B
주어진 인접행렬을 가지고 순서 관계를 파악할 수 있다. 디테일은 기억 안남
C
내가 위에서 쓸데없는 말을 막 싸지른(?) 이유는 이 문제 때문이다. 그냥 구성적 문제인데, 진짜 1시간 동안 이상한 수열 다 그려가면서 n을 넘는게 언제인지 하나하나 찾고 있었다. 근데 진짜 아무리 해도 답이 안나오길래 D로 넘어갔다.
풀이)[1,2,3,...,n-2,1,2]로 하면 팰린드롬이 2n-6개라서 n = 6만 예제로 복붙하고 저걸 하면 된다.
아
D
진짜 거짓말 안치고 C보다 쉽다. 근데 이미 C에서 멘탈 다 나가고 들어와서 median이 x인 경우의 수를 세는 것까진 알겠고, 이걸 prefix sum을 잘 관리하면서 해야된다는 것까진 알았는데 그 뒤로 몇십분 멍때리다가 그냥 끝났다.
풀이)median이 x인 경우의 수를 세자. 어떤 값이 x 이하면 -1, 초과면 1로 배정하자. 이때 median이 x 이하인 경우의 수는 prefix sum이 일치하는 경우의 수와 같다. 근데 정확히 x인 경우를 세려면 x가 그 구간에 포함되면 된다. 따라서 어떤 x를 기준으로 왼쪽 prefix, 오른쪽 suffix에서 일치하는 경우의 수를 잘 곱해주면서 관리하면 된다.
후기)C가 진짜 코포형 문제라고 생각한다. 풀면 그냥 넘어가고 말지만 저기서 걸리면 진짜 바로 말리는 지름길인 것 같다. 그리고 나도 문제인게, 문제에서 막히면 backtrack을 안하고 계속 될 것 같아서 비슷한 풀이로 넘어간다. 그래서 초반에 복잡하게 생각해서 잘못 들어가면 바로 망하는 것 같다. 그리고 이건 다음 라운드에서 확실히 알 수 있다.
또 수학에 걸렸다. 그래도 이건 C까지 속도가 나쁘지 않아서 최악은 막았다.
A
솔직히 문제 이해는 지금도 못했다. 그냥 예제 보고 b-a인데 b=1일때만 다르길래 그렇게 해서 냈다.
B
결국 [l,r]에서 큰 값들을 작은 값으로 교체하는 것이 목표이다. 그리고 생각해보면 [l,r] 내부 개수 = [0..l-1] 개수가 되도록 subsequence를 고르면 값이 싹 교체되고, 역시 [l,r] = [r+1..n-1]이 되도록 고르면 값이 싹 교체된다. 만약 양쪽에 걸치게 하면 의미가 없게 된다. 그래서 끝에서 최솟값 몇개, 내부에서 최댓값 몇개를 골라서 이득일때까지 골라서 교체해서 왼쪽 오른쪽 중에 min 취하면 된다.
C
만약 인접한 정점을 고른다면 간선을 고르는 것이 되고 컴포넌트 개수는 u-v 간선일 때 deg(u)+deg(v) -2이다.
인접하지 않은 정점을 고른다면, 고를 정점 하나를 고정하면 인접하지 않은 정점 중 max(deg(v))를 골라 deg(u) + deg(v) - 1을 취하면 된다. set으로 deg를 관리하면서 정점 u를 볼때 인접한 정점은 지워주는 방식으로 구현하면 각 정점은 O(deg(x))만큼 지워지므로 O(NlogN)에 풀 수 있다.
D
접근은 거의 다 했다. 한 직선에서 2개를 고른다면 양끝에 2개를 매칭하는게 당연히 최적이다. 그래서 이걸 수식으로 좀 세웠으면 이분탐색/삼분탐색으로 들어갔을 것 같은데 괜히 선형으로 풀려다가(정렬 제외) 덱 관리하다가 꼬여서 망했다.
풀이)y=0, y=2 직선을 각각 a,b라고 하자. k가 고정일 때 f(x)를 a에서 최적으로 x개 골랐을 때, g(x)를 b에서 골랐을 때 값으로 정의하고 h(x) = f(x) + g(k-x)으로 정의하면 문제는 x 범위가 주어질 때 h(x)의 최댓값을 찾는 것이 된다. 이때 h(x)는 정수 단위에서 convex한데, 정의상 x가 증가하면 a에서 고를 값 중 최소를 b로 옮기는 것이기 때문에 이게 어느 순간까지는 양수다가 특정 시점부터 쭉 음수가 된다. 따라서 convex하며 이건 삼분탐색으로 찾거나 어차피 변화량만 보면 되기 때문에 이분탐색으로 해줄 수 있다.
후기)D를 너무 복잡하게 생각했다.
체감 난이도가 D<A<B였다. ARC는 최근에 점수랑 난이도가 매칭이 잘 안되는 것 같다.
A
결국 같은 수로 연속하게 이어진 걸 하나의 그룹으로 보고, 인접한 그룹을 합쳐주는 연산이 있을 때 결과적으로 저런 배열이 나오는 경우의 수를 구하는 문제이다. 한번 합치면 undo가 안되기 때문에 결과 그룹을 기준으로 독립적으로 합쳐주는 경우의 수만 잘 곱해주면 되고, 나머지는 간단한 수학이다.
B
홀짝성 나누는 것까지는 관찰을 했고(i에 연산을 하면 i+1에만 영향을 주고 i+2에는 영향을 안줌), x의 중앙값 차에 대한 관찰을 하다가 끝났는데 에디토리얼을 보니까 x 중앙값 차가 아니고 그냥 x 차이를 관찰하면 쉽게 풀리는 문제였다.
D
left/right nearest lower bound를 찾아서 유니온 파인드로 잘 묶어주면 된다. 이게 끝이다. 아니 이게 왜 D인데
후기)ARC는 뒷문제까지 잘 봐야한다고 느꼈다. D는 근데 왜 진짜 700점인지 모르겠다.
A
연산이 복잡하게 생겼는데, [l,r]이랑 그 밖에 하는 거라서 대부분 2번 정도만에 될거라는 관찰을 할 수 있다.
먼저 1번만에 끝나는 경우를 처리해주자. 2번 만에 끝나려면 disjoint한 두 구간이 존재하거나 완벽하게 포함관계에 있는 두 구간이 존재하면 된다. 또는 그냥 2개만에 [1,n]이 다 커버되면 된다.
그렇지 않으면 3번 만에 되거나 불가능하다. 2번만에 안 끝나기 때문에 [l,r]을 l 기준으로 정렬하면 l이 증가하면 r도 증가하는 형태의 구간들이 나온다. 만약 n=2였다면 불가능하고, 그렇지 않으면 정렬된 인덱스 기준으로 l[0]~r[0](1번 연산), l[n-1]~r[n-1](1번 연산), l[1]~r[1](2번 연산)을 하면 된다.
B
업솔빙 하려고 남겨놨는데 아직 안했다.
후기)망한줄 알았는데 뒷문제가 어려워서 괜찮게 나왔다.
B<A였다. 아마도?
A
가끔 나오는 dp 상태를 최적화하는 유형이다. 결국 prefix sum 관점에서 parity가 같은 쌍을 세야 하는데, 0,1을 반전시킨 것도 같은 상태라서 하나로 묶으면 상태가 4개가 나온다. 또한 상태 개수의 합을 알기 때문에 3가지 상태 개수만 dp식에 넣어주면 O(N^4)에 된다.
B
비수학적으로 접근하다가 늦었다. n이 4의 배수이면 불가능하고, 그렇지 않으면 0, 2k, -2k, 4k, -4k, ... 순서대로 mod N을 취한 위치에 칠해진다. 이걸 쭉 칠할 때 주기를 생각해야 한다. n이 홀수일 때는 n과 k가 서로소여야 하며, 짝수이면서 k도 짝수면 n, k에 2를 나눠서 홀수인 문제로 바꿔준다. n이 짝수면서 k가 홀수면 역시 n과 k가 서로소여야 한다.
후기)내가 수학을 얼마나 못하는지 다시 깨달았다. 왜 이상한 접근을 하는건지 모르겠다.
B<A. A에 또 말렸는데 B를 빨리 풀어서 살았다.
A
앳코더에서 이런 문제가 나오다니 좀 놀랐다. 처음엔 그냥 버블소트하듯이 해줬는데 생각해보면 마지막 2개 남았을 때는 k를 처리하기가 힘들다. 그래서 inversion이 아닌 쌍 (i,j)를 하나 잡고 하면 편한데, 만약 이런 쌍이 하나도 없다면 적어도 1개는 k를 더해줘야 한다. 따라서 모든 쌍이 inversion이면 min, max만 각각 n-1, n-2에 남기고 swap해줬을 때 inversion이 아닌지 확인해준 후 나머지는 걍 구간에 kx 더하는 느낌으로 정렬될때까지 쭉 더해주면 된다.
B
앳코더는 문제를 무섭게 쓰는 걸 정말 잘하는 것 같다. 연결성만 보니까 대충 merge 연산이라고 생각하고 보면, 결국 컴포넌트가 끊긴다는 것은 어떤 i가 있어서 prefix min[0..i] > suffix max[i+1..n-1]이어야 한다. 이 관찰을 통해 컴포넌트는 한 구간을 이룬다는 것도 알 수 있고, 컴포넌트 개수에 대한 관찰도 할 수 있다.
이제 double counting을 할 것이다. 저 식에 따라 위치 i에서 총 몇개의 컴포넌트가 끊기게 되는지 볼 것이다. (이때 답은 각 위치에서 끊기는 개수 + M^q가 될 것이다) 그 계산을 위해서는 다음과 같은 배열을 구하면 된다. prefix[i][j] := [0..i]에서 j 이상의 수만 사용하는 경우의 수 / suffix[i][j] := [i..n-1]에서 j 이하의 수만 사용하는 경우의 수
저 두 배열을 전처리해놓으면, 각 분할점 i에 대해 끊기는 컴포넌트의 개수를 셀 수 있다. 저 배열들은 어떻게든 구하면 되는데 dp가 제일 간편하다.
후기)이번엔 반대로 생각만 빠르게 하면 내가 충분히 잘할 수 있다는 걸 깨달았다. 옛날에는 퍼포먼스가 최하~최상을 왔다갔다 했는데 이제는 퍼포먼스가 극소 부근/극대 부근 2개밖에 없는 것 같다.
1월 PS (2)가 있을지는 모르겠다. 여기에 대부분 쓴 것 같은데?
'일기' 카테고리의 다른 글
| 1월 PS (2) (1) | 2025.01.31 |
|---|---|
| 2025 국제정보올림피아드 대표학생 선발고사 1차 후기 (2) | 2025.01.27 |
| solved.ac Ruby V (2) | 2025.01.19 |
| 재미있는 문제 (0) | 2025.01.13 |
| 11월 PS (2) (0) | 2024.11.17 |
