7월의 PS 일지 - Part 2

7월 말 ~ 8월 초에서는 먼저 UCPC 예선, 본선이 있었다. 문제를 몇 개 안 풀어서 나중에 업솔빙을 할 생각이다.

SNUPS에서 SCPC 대비 스터디가 있어서, SCPC 예선 문제를 가능한만큼 밀었다. 본선은 추후에 진짜 대회처럼 돌아볼 생각이다.

그리고 친구들과 만나서 셋을 돌거나 개인적으로 셋을 돌고, 덤으로 그냥 지나가는 문제들을 몇 개 풀었다. 

BOJ 1624 데크소트

데크가 특정 연속한 크기의 수들을 모두 담을 수 있을지만 체크하면 된다는 것을 증명할 수 있다.

즉, 등장하는 수들의 집합이 $\{1, 2, 3, 4, 5\}$라면, 등장하는 1을 전부 한 데크에 넣을 수 있는지, 그게 가능하다면 1, 2를 모두 한 데크에 넣을 수 있는지, 1, 2, 3을 모두 한 데크에 넣을 수 있는지 등을 순서대로 확인하면 된다. 이를 차례대로 진행하면서 필요한 데크의 개수를 추가해주면 문제를 해결할 수 있다.

BOJ 19548 그건 망고가 아니라 고양이에요

비슷한 문제로 NEERC 2016 List of Primes가 있다. 대회 때 얘 때문에 멘탈 나갔는데 조금만 더 붙잡을 걸 그랬다.

LaTeX 표기 문제가 귀찮으므로, 여기서는 달러 표기를 #으로 명명한다.

일단 #의 개수가 1인 경우와 2 이상인 경우를 분리한다. 첫 경우는 답을 쉽게 처리할 수 있다.

이제 #의 개수가 2 이상인 경우를 생각해보자. 가장 기본적인 절차는 $M_k$의 한 구간을 출력하는 것을 $S$의 일부분을 출력하는 것과 $M_{k-1}$의 여러 구간을 출력하는 것으로 문제를 변환하는 과정이다. 이를 효율적으로 하기 위해서는 단순히 부분합 + 이분탐색 등을 활용할 수 있다. 

그런데 이렇게만 하면 $\mathcal{O}(k)$에 준하는 시간이 걸릴 수 있으므로, 더욱 최적화를 해야 한다.

규칙 문자열이 $S_0$#$S_1$#$\cdots$ 형태로 이루어져 있다고 생각해보자. 이제 $S_0$에 대해 경우를 나눠야 한다.

$S_0$가 빈 문자열이라면, $R<|M_t|$인 최소의 $t$를 잡고 $M_t$의 한 구간을 출력하는 문제로 바꿀 수 있다.

현재 #의 개수가 2 이상이므로, 이는 $k$의 값을 순식간에 로그 스케일로 줄여주는 역할을 할 수 있다.

또한, $S_0$가 빈 문자열이 아니더라도, $M_k$는 결국 $S_0 * t + M_{k-t}$로 시작된다. 

그러니 $|S_0| * t + |M_{k-t}| > R$인 최대의 $t$를 잡고, 문제를 $M_{k-t}$로 옮길 수 있다. 이러면 문제 해결.

구간의 인덱스를 바꿔가는 과정에서 주의가 필요하고, 나는 여기서 실수를 좀 했다. 고치려고 시도도 안하고 놓은 게 문제.

추가적으로 오버플로우 문제도 꽤 발생할 수 있으므로, 주의가 필요하다. 여러모로 (내가 못풀어서) 아쉬움이 남는 문제.

Pacific Northwest Regional 2019 (Division 1)

• E : 각 알파벳을 넣거나 말거나 선택하고, 넣을 때 그 위치를 선택하면 된다.
• D : $a \le b$가 성립할 때까지 나눗셈을 반복하고, 그 뒤로부터는 쭉 1을 더하면 된다.
• C : 특정 정점까지 도달하는 최단거리를 기준으로 색칠을 하면, 답이 최단거리에 1을 뺀 값임을 쉽게 확인할 수 있다.
• M : 근본적으로는 단순 BFS 문제인데, 홀짝성을 다루고 간선을 제대로 긋는 과정이 은근 헷갈린다.
• L : 1의 자릿수부터 순서대로 재귀적으로 결정하면 시간 안에 작동한다. 실패했을 때 바로 재귀를 끊는 과정도 필요하다.
• J : 각 행성이 기여하는 값이 piecewise linear function이므로, 이를 모두 때려박은 다음에 각 유의미한 구간의 끝점에서만 함숫값을 계산하여 그 중 최댓값을 취하면 답을 얻는다. 말은 쉽지만 생각보다 구현이 쉽지는 않다. 특정 구현 방법은 실수오차에 매우 민감할 수 있으므로, 조심해야 한다.
• A : 이런 문제는 한 정점에서 인접한 다른 정점으로 갈 때 답이 얼마나 변화하는지를 탐구하는 것이 좋다. 어쨌든 구해야 하는 것은 거리의 합과 가중치와 거리의 곱의 합이므로, 이 두 값의 변화를 따져보자. 조금 생각해보면 결국 서브트리의 크기와 서브트리 내 가중치의 합을 관리하면 이 변화를 쉽게 계산할 수 있음을 알 수 있다. 그러니 DFS 2번으로 문제를 해결할 수 있다. 좋은 연습문제.
• G : 두 신호가 교차할 조건을 잘 정리하면, 일종의 inversion 같은 조건을 얻을 수 있다. 정렬 후 세그먼트 트리.
• I : even/odd permutation을 생각하면, 한 번의 swap으로 같게 되는 두 permutation을 간선으로 이었을 때 얻어지는 그래프는 자명하게 이분그래프임을 알 수 있다. 이제 이 그래프의 최대 독립집합을 구해야 하고, 그 여집합은 최소 정점 커버와 같다. 그러니 최대 매칭 문제로 환원되며 문제 해결.
• B : 이런 문제는 보통 맨 처음에 올 수 있는 게 무엇인지 고르는 것을 반복하는 것으로 해결된다. $i$가 처음으로 올 수 있을 조건은, $i$의 첫 위치가 "다른 모든 원소들의 마지막 등장 위치 중 가장 앞에 있는 것"보다 앞에 있는 것이다. 이 조건을 만족하는 $i$의 최솟값은 결국 특정 구간의 최솟값과 같다. 이제 첫 원소를 고정하면, 그 원소는 이제부터 없는 것 취급해도 된다. 즉, 다음 원소의 조건을 따질 때에도 고려할 필요가 없다. 이를 반복하여 답을 얻는다. 이를 효율적으로 구현하기 위해서는 최솟값 세그먼트 트리, 가장 최근에 뽑은 원소의 위치, 그리고 현재 남은 원소들 중 마지막 등장 위치의 집합 등을 모두 관리하고 있어야 한다. 세세한 디테일은 독자에게 맡긴다. 이 셋에서 가장 재밌었던 문제 중 하나였다. 전형적이지만 좋은 연습.
• F : 이 문제도 처음에 오는 원소를 결정하고 재귀적으로 내려가는 방식으로 해결된다. 이 과정에서 가장 핵심적인 과정은 교란순열 느낌의 DP를 정의하고 계산하는 것이다. 두 집합 $I_1, I_2$가 있고, $|I_1|=|I_2|=n$, $|I_1 \cap I_2| = m$이라고 하자. $I_1$의 원소를 이미 순서대로 깔아놓은 상태에서, $I_2$의 원소를 적당히 나란하게 깔아놓았을 때 매치가 형성되는 개수가 정확하게 $k$개인 경우의 수를 $dp[n][m][k]$라고 하자. 이 DP를 채우면, 이를 기반으로 문제를 해결할 수 있다. 점화식의 유도는 독자들에게 맡긴다. 나는 오버플로우가 무서워서 그냥 Python을 사용했다.
• K : 2번 쿼리가 들어올 때, 이 위치가 현재 "몇 번째 쿼리에 의해 들어온 값인지"를 파악하도록 하자. 이를 위해서는 lazy propagation을 지원하는 세그먼트 트리를 이용할 수 있다. 이제 쿼리의 번호를 안다면, 그 당시의 데이터 값을 확인해야 한다. 이건 단순히 Persistent Segment Tree를 이용해서 계산할 수 있다. 여기서 구간 업데이트 점 쿼리를 구간 쿼리 점 업데이트로 바꾸는 요령이 필요하다. 전체적으로 아이디어는 어렵지 않은 문제다.
• H : 기하 문제고 사실 그냥 각도정렬 한 번이면 해결할 수 있을 것 같다. 가능한 상태가 몇 개 없으니까 상태 이전만 효율적으로 할 수 있게 하면 충분하고, 이건 각도정렬으로 할 수 있기 때문이다. 구현할 자신은 없다. 기하 연습이 절실하게 필요한데 하고 싶지는 않다.

Codeforces Educational Round 92

Div 1 + Div 2 합쳐서 11등. 오랜만에 코포를 쳤는데 (out of competition) 기분이 좋았다.

• A : $r/l < 2$면 당연히 불가능하고, 아니면 $l, 2l$을 찍으면 된다. 이런 문제 좋다.
• B : 왼쪽으로 가는 횟수를 고정하고 생각하면 그리디 풀이가 가능하다. 근데 생각이 안나서 DP로 풀었다.
• C : 가능한 문자열은 $aaa \cdots aa$ 또는 $abab \cdots ab$다. 여기서 $a, b$로 가능한 문자를 모두 시도하면 된다.
• D : 결국 1만큼의 intersection을 얻기 위해 소모해야 하는 비용을 생각할 수 있다. 만약 두 구간이 처음부터 겹쳤다면, 비용이 1이었다가 "특정 시점" 이후로 2가 된다. 그러니까 비용이 1인 걸 최대한 뽑아먹고 비용이 2인 걸 사용하면 된다. 두 구간이 처음부터 겹치지 않았다면, 우선 겹칠때까지 비용을 소모하다가 "한동안" 1만큼의 intersection을 위한 비용이 1이었다가 "특정 시점" 이후로 2가 된다. 그러니 실제로 사용될 구간의 개수를 고정하고 생각하면 답을 빠르게 얻을 수 있다. 여기서 "특정 시점"이 무엇인지 파악하는 것은 독자에게 맡긴다. 재밌었던 문제.
• E : 합동식을 써놓고 생각하면 문제에서 요구하는게 정말 간단한 합임을 알 수 있다. 노잼이다.
• F : 우선 정렬 + 좌표압축은 기본이다. $dp[e][idx]$를 끝점이 $e$ 이하인 구간들만 모았을 때, 마지막 구간이 $idx$ 색깔인 경우 선택할 수 있는 구간의 개수라고 하자. 그러면 $dp[e][idx] = \text{max}_s (dp[s-1][3-idx] + ENC(s, e, idx))$가 되는데, 여기서 $ENC(s, e, idx)$는 구간 $[s, e]$에 포함되는 $idx$ 색깔 구간의 개수이다. 이제 $dp[s-1][3-idx] + ENC(s, e, idx)$라는 값들을 갖는 세그먼트 트리를 생각하자. $e$를 증가시킬 때 고려해야 하는 것은 추가되는 그 값이 끝점인 새로운 구간들이고, 이는 특정 범위의 $s$에 대한 $ENC(s, e, idx)$ 값을 증가시킨다. 그러므로 필요한 것은 구간에 1을 더하는 쿼리와 구간의 최댓값을 구하는 쿼리를 지원하는 lazy propagation 세그트리다. 끝.

SCPC 1차 예선

• 1회 1번 : 그리디하게 가능한만큼 멀리 뛰면 된다.
• 1회 2번 : 시키는대로 구현인데 조금 귀찮은 수준이다.
• 1회 3번 : $b$진법 균일수가 되려면 $n$이 $1+b+ \cdots + b^k$의 배수가 되어야 한다. $k=1$과 $k \ge 2$를 구분하여 따로 처리하자.
• 1회 4번 : 이분탐색 + 좌표압축 + 2차원 부분합으로 문제를 해결할 수 있다.
• 1회 5번 : 단순히 다익스트라를 열심히 돌리면 되는 문제다.
• 2회 1번 : 최솟값은 작은 $N$에 대해 도달 횟수를 전부 계산하면 얻을 수 있고, 최댓값은 자명하다.
• 2회 2번 : DP 식을 세운 후 적당히 빠르게 계산할 수 있게 식을 정리하면 된다.
• 2회 3번 : 결국 이어진 로봇이 $K$개 미만이거나 이어지지 않은 로봇이 $L$개 미만이면 제거가 된다. 그러니 현재 조건을 만족하지 않는 로봇은 뭘 어떻게 하던 상관없이 무조건 제거되어야 한다. 그러니 그냥 최소 합 같은 조건은 신경쓰지 말고 제거되어야 하는 얘가 있을 때마다 제거해주면 된다. 재밌음.
• 2회 4번 : 단순히 다익스트라를 열심히 돌리면 되는 문제다. 시작점이 여러 개인 것만 잘 하면 된다.
• 2회 5번 : 대놓고 플로우 문제라서 그래프 잘 그리고 플로우 돌리면 된다.
• 3회 1번 : 이게 왜 1번인지 모르겠다. 먼저 $dp[i]$를 $i$번째 인덱스에서 시작하는 최소 길이의 올바른 괄호문자열이라고 하자. 이는 stack을 이용하여 구할 수 있다. 여기서 괄호문자열이 깨지면 stack을 초기화하는 것이 중요하다. 이제 이 계산과정이 끝나면, 이제 $dp[i]$의 정의를 $i$번째 인덱스에서 시작하는 최대 길이의 올바른 괄호문자열이라고 변경하고, 뒤에서부터 동적계획법을 돌려서 DP 테이블을 채울 수 있다. stack 쓰는 거 너무 어렵다 ㅋㅋ
• 3회 2번 : 그냥 꺾은선 그래프를 생각해서, 올라갔다 내려갔다 하는 횟수를 세기만 하면 된다. 근데 은근 헷갈린다.
• 3회 3번 : 2-SAT 형태의 문제지만, 특수한 형태 때문에 단순한 disjoint set으로 해결할 수 있다.
• 3회 4번 : 오목한 각도 구간이 전체 영역을 덮는지 확인하면 된다. 기하 너무 어렵다 ㅠㅠ
• 3회 5번 : 이걸 어떻게 푸냐? 추후에 스터디에서 풀이를 듣고 풀어야 할 것 같다.
• 4회 1번 : 그리디하게 배치하면 된다. 배치를 효율적으로 하고 싶다면 사용할 것은 std::set.
• 4회 2번 : 회문인 수가 몇 개 없어서 단순하게 전탐색을 하면 된다.
• 4회 3번 : 차수가 2인 정점을 순서대로 고려하면 충분하다. 위상정렬처럼 구현하면 된다.
• 4회 4번 : 거리 순서 배치를 시도하고 랜덤 swap을 반복하면 만점 비슷한 점수가 나온다.
• 4회 5번 : 높이에 대한 이분탐색을 한다. 그 후, "가장 좋은 위치"에 해당하는 전등을 모두 찍고, 그들이 덮는 영역을 구간으로 표현하자. 이들 중 $l$개 이하를 선택하여 전체 구간을 덮을 수 있으면 된다. 이는 단순한 정렬 + 그리디로 가능하다. 구현에 함정이 꽤 있는 편이라서 주의를 하는 게 좋다. 
• 5회 1번 : DP + 부분합으로 간단하게 해결할 수 있다.
• 5회 2번 : 대놓고 수학문제고, 머리 싸매면서 식을 정리하면 해결할 수 있다.
• 5회 3번 : 앞/뒤 몇십만개만 계산하면 된다는 믿음, 충분히 큰 값에서는 최대 삼각수를 계속 빼나가는 작업을 반복하는 것이 최적이라는 믿음, 그리고 첫 수천개의 값들에 대한 naive DP를 돌려주는 방식을 취하면 해결할 수 있다. 솔직히 대회 때 해결 당시에도 찍어서 풀었다.
•  5회 4번 : 대회 당시 코드를 봤는데, 그냥 큰 원부터 넣으면서 랜덤 & 그리디하게 원을 넣은 것 같다. 구현량 레전드 갱신.
•  5회 5번 : 이분탐색을 하면, 또 다시 특정 구간들이 큰 구간 하나를 덮을 수 있는지 확인하는 문제가 된다.

SCPC 2차 예선

• 1회 1번 : 사실상 최대공약수의 약수의 개수를 구하는 문제. 동일한 원소가 있는 경우를 조심하면 된다.
• 1회 2번 : 그냥 두 팀이 게임을 하고 있다고 생각하고, finite impartial game을 다루는 전형적인 방법을 그대로 쓰자. 
• 1회 3번 : DP를 짜면 문제가 해결된다. 지루한 문제고 2번이 더 어려운 것 같다.
• 1회 4번 : 왼쪽 끝으로 정렬한 다음 최장 단조 감소 수열의 길이를 계산하면 된다. 
• 1회 5번 : 1차 예선과 특별히 다른 점이 없는 문제고, 비슷하게 풀면 된다.
• 2회 1번 : DAG를 구축하고 위상정렬 + DP로 해결하는 매우 전형적인 문제다.
• 2회 2번 : 단순한 DP를 짜면 문제가 해결된다. 지루한 문제.
• 2회 3번 : 수직선이 맨 왼쪽에 있을 때를 생각하고, 수평선의 위치에 따른 점수를 세그먼트 트리에 넣자. 이제 수직선을 오른쪽으로 움직이면서, 세그먼트 트리의 값을 변경하자. 이를 위해서는 구간 최댓값 쿼리와 구간에 값을 더하는 쿼리를 지원하는 lazy propagation 세그먼트 트리가 필요하다. 시간 제한이 빡세서 쿼리 횟수를 적당히 잘 최적화해야 한다. 솔직히 시간 제한이 지나치게 빡센 것 같다.
• 2회 4번 : 문제가 뭔 소리인지부터 모르겠다.
• 2회 5번 : 대강 큰 그림은 알겠는데, 구현이 너무 힘들 것 같아서 보류하고 있다.
• 3회 1번 : 일단 하노이 문제가 모두 그렇듯이, 재귀적 패턴을 먼저 찾아야 한다. 이제 가장 큰 원판의 상태부터 차례대로 보면서, 현재 상태가 "재귀의 어느 위치에" 있는지 파악을 할 수 있다. 이를 반복하면 문제를 해결할 수 있다. 개인적으로 엄청 마음에 드는 문제.
• 3회 2번 : 중국인의 나머지 정리 템플릿이 있으면 간단하게 해결할 수 있는 문제.
• 3회 3번 : 문제의 답을 오프라인으로 구한다. 쿼리를 오른쪽 끝 기준으로 정렬하여, 순서대로 해결한다. 배열의 각 원소를 추가하면서, $i$의 배수가 등장하는 가장 마지막 index $lst[i]$를 관리한다. 이제 쿼리를 대답하는 것은 $lst$ 배열을 참조하여 간단하게 할 수 있다. 약수의 집합은 미리 전처리하자.
• 3회 4번 : 뭔가 말이 복잡한데, $p=1$인 경우 트리의 중심을 구하라는 말이 된다. 이를 구하는 가장 쉬운 방법 중 하나는 리프를 순서대로 쳐내는 것이다. priority_queue에 리프를 넣고, 가중치가 작은 리프부터 순서대로 쳐내면 된다. 이는 일반적인 $p$에 대해서도 올바른 답을 낸다. 왜인지는 증명을 시도하지 않아서 잘 모르겠다 ㅋㅋㅋ 여기서 "가중치"가 의미하는 바가 무엇인지는 독자에게 맡긴다. 원리를 자세히 알고 싶은 문제.
• 3회 5번 : 구간 DP 문제인걸로 알고 있는데 잘 모르겠다.
• 4회 1번 : prefix/suffix 최소/최대를 저장하면 쉽게 해결할 수 있는 문제다.
• 4회 2번 : 이 문제와 중복. 아래서부터 순서대로 보면서 현재 위치/현재 나란한 선 개수를 상태로 보고 이때 가능한 높이의 최솟값을 DP로 계산하면 된다. 메모리가 부족하므로 토글링을 추가해야 한다. 이 문제도 subquadratic 풀이가 있는 것으로 아는데, 언제 공부하지 ㅋㅋ
• 4회 3번 : 시작점/끝점을 시작으로 하는 최단 단조 증가 경로의 길이를 구하면 충분하다. 이를 위해서는 간선들을 가중치 기준으로 정렬한 다음, 해당 가중치를 갖는 간선들 및 인접 정점들만 모아서 다익스트라를 돌려주는 것을 반복하면 된다.
• 4회 4번 : 사실상 LIS의 길이를 반복해서 구하는 문제다. 시간 제한이 쓸데없이 빡빡하니까 고통을 좀 받을 준비를 해야한다. 
• 4회 5번 : 이 문제와 동일한 문제. 풀이는 해당 대회의 에디토리얼에 잘 나와있다. 아이디어는 직관적인 편인데, 증명을 어떻게 할지는 또 의문이다. 
• 5회 1번 : 숫자를 제거하면서 수의 크기가 감소하므로, 단순한 DP를 구상할 수 있다.
• 5회 2번 : 뒤집는 문자열의 "중심"을 기준으로 생각하면, 어렵지 않게 문제를 해결할 수 있다.
• 5회 3번 : 시작점에서부터 "가능한 오른쪽으로 가는" 경로와, 끝점에서 "가능한 왼쪽으로 가는" 경로를 생각하면, 이 두 경로 사이의 영역이 답이 된다. 구현은 까다롭지만 이게 가장 구현이 깔끔한 풀이다. 좋은 아이디어를 쓰는 문제. 이렇게 극단적인 경로를 생각하는 문제가 꽤 많은 것 같다.
• 5회 4번 : Set Cover 문제의 일종이므로, 이를 위한 approximation algorithm 하나를 구현해서 내면 된다.
• 5회 5번 : 대각선 위/아래를 구분하여 생각하면 문제가 매우 간단해진다. 이 설명이 매우 좋다.