4월 1, 2주차 PS 정리

왤케 요새 안하지.... 딱히 할 시간이 없냐면 그건 또 아니다. (주로 롤토체스에 빠져 살고 있다)

5문제. 난이도 순 (아마도)

그나마 SNUPS Red Army를 시작해서 문제풀 동기가 조금 더 생겼다. Red Army는 작년에 TAMREF님이 개설한 스터디를 올해 내가 이어서 하고 있는데, Codeforces 기준 블루~오렌지 정도 실력을 가진 사람들이 조금 어려운 문제 (2000+) 를 일주일동안 몇개 풀고 디스커션을 하는, 스터디 그룹 같은 느낌이다. 

다음주에는 Red Army 2주차를 최대한 풀고 풀이를 작성하는걸 목표로 하고 있다 (2주차부터는 이상한 사람들의 영향으로 2600, 2800 문제가 들어가 있기 때문에 다 풀긴 조금 무리가 있다)

 

Codeforces Round 635 (Div1) B, Xenia and Colorful Gems 

난이도 : Codeforces ? (체감은 1900인거같은데 아직 안나왔다)

두달만에 뛴 Rated round의 B번 문제인데, 오랜 공백 탓인지 라운드를 말아먹고 다시 있어야 할 자리 (퍼플) 로 돌아갔다. :( 2솔브했으므로 라운드 후기는 생략하고 이 문제만 풀이를 간단히 쓰기로 하자.

$R, G, B$ 배열이 주어질 때, 각각에서 하나씩 $x, y, z$를 골라 $(x-y)^2 + (y-z)^2 + (z-x)^2$ 를 최소화하는 문제. 

일단 당연히 최대한 $x, y, z$가 가까워야 하고, 관찰을 통해 $x, y$를 정했다면 봐야 하는 $z$는 많아야 두어개 ($x, y$의 평균에 가까운 것들) 임을 알 수 있다. 또한, $x$가 이미 정해졌을 때, $y$ 도 $x$에 가까운 두어개만이 답의 후보가 될 수 있다. 뽑는 순서에 따라 답이 달라질 수 있으므로 가능한 모든 경우를 뽑아 봐야 하는데, 그래봐야 하나의 $x$에 대해서

- 가까운 $y$ 두어개를 뽑고, $(x, y)$ 에 가까운 $z$ 두어개를 뽑는다.

- 가까운 $z$ 두어개를 뽑고, $(x, z)$ 에 가까운 $y$ 두어개를 뽑는다.

이정도만 해보면 된다. 가까운 원소 뽑기는 STL의 $\texttt{lower\_bound}$ 같은 함수를 잘 써먹으면 된다.

Iterator 사용에 심각한 장애가 있는데다 로컬과 채점기의 환경이 달라서 로컬에서는 돌아가는게 채점기에서는 RTE를 띄우기 때문에 (Cygwin과 MinGW의 차이인데도 UB가 다른게 있네...) 디버깅에 30분 이상 걸렸다. iterator의 사용을 제대로 공부하거나, 제대로 공부하기 전까지는 최대한 안전하게 바운드 체킹 해가면서 써야겠다는 교훈(?) 을 얻었다.

 

CF Technocup 2018 Elimination Round 2D, Something with XOR Queries

난이도 : Codeforces 2100

Red Army Week 1, B번 문제. 이번학기는 Red Army 스터디의 문제를 내가 뽑고 있는데 (어차피 스크립트를 돌려 랜덤하게 뽑고 있긴 하다) Interactive 인걸 알았으면 버렸을것같다. 좋게 생각하면 랜덤으로 뽑은덕에 평소같으면 걸렀을 문제에 손을 대보는것 같기도 하고...

요점은, 실제로는 $(0, i)$ 형태의 쿼리와 $(i, 0)$ 형태의 쿼리의 결과만 있으면 모든 쿼리의 값을 확인해 볼 수 있다는 점이다. 쿼리 $(i, j)$ 는 $p_i \oplus b_j$ 로 정의되는데, 이때 저 정보들을 모두 알고 있다면,

$$(p_0 \oplus b_j) \oplus (p_i \oplus b_0) \oplus (p_0 \oplus b_0)$$ 하면 원하는 임의의 쿼리값을 확인할 수 있기 때문이다.

이떄, $b_0$ 의 값을 알고 있다면 모든 $p_i$ 값을 확인할 수 있다. 이제, $b_0$를 아무렇게나 찍과 말이 되는지 (쿼리의 정보가 Consistent한지) 확인하는 것으로 끝.

 

BOJ 15005, BAPC 2017C Collatz Conjecture

난이도 : Solved ac Platinum 2

서로 다른 구간 GCD의 개수를 찾는 문제.

먼저, 다음과 같은 구간 GCD를 생각해 보자. $a_1, a_2, \dots a_k$ 의 GCD들만을 생각한다고 할 때,

Lemma. 서로 다른 Prefix GCD는 많아야 $\log a_1$ 개이다.

Proof. 거의 자명한데, GCD가 '가만히 있거나', '줄어들어야' 한다는 것을 생각해 보자. 만약 '줄어든다'면, 절반 이하로 떨어진다. $n/2 < x < n$ 인 약수 x가 있을 수 없으므로... 이 사실은 매우 유용하므로, 혹시 몰랐다면 기억하도록 하자. 나는 팀연습중에 이걸 쓰는 문제를 처음 만났었던 것 같다.

이제, 앞에서부터 set에 GCD를 저장하면서 나가되, $P_i$ 를 $a_i$에서 끝나는 구간들의 구간 GCD라고 정의하면, $P_i$ 로부터 $P_{i+1}$ 을 빠르게 계산할 수 있다는 사실을 이용하자. 굳이 모든 값을 버리고 $P_{i+1}$을 새로 계산하는 대신, 앞 값에서 ($a_i$ 로 끝나는 구간들에서) $a_{i+1}$ 을 추가로 gcd처리해주면 된다. 

시간 복잡도는 $O(n \log^2 A)$ 인데, $n = 5e5, A = 1e18$ 이라 무려 10초가 주어져 있다.

 

Codeforces Round 201C, Number Transformation II

난이도 : Codeforces 2200

Red Army Week 1, C번 문제.

수 $x_1 \dots x_n$ 이 주어지고, $a$ 에서 출발해서, $b$ 까지 가는데 $a = a - a \mod x_i$ 연산 또는 $a--$ 둘중 하나로만 가야 한다. 최소 횟수 찾기.

일단, $\texttt{a--}$가 가능하기 때문에, $f(x) = b+x$ 에서 출발해서 $b$에 도달하는 연산횟수로 도달하면 이 함수가 단조증가임을 증명할 수 있다. 즉, 최대한 한번에 많이 점프하면서 내려가는게 이득임을 알 수 있다.

여기까지 증명을 했다면, 지금 집합에 들어있는 원소들 중 최대한 많이 내려갈 수 있는 길로 내려가되, 중간에 커팅을 하는 코드를 작성할 수 있다. 자명한 커팅 조건으로, $a$ 를 $b$보다 작은 수로 만들어버리는 $x$는 전혀 도움이 안 되므로 버리기로 하자. 가능한 공간 100만 개 중 10만 개의 $x$가 주어지고, 진행하면서 점점 적은 수의 $x$를 남기는 셈이 되어 시간 안에 돈다. (사실 복잡도 증명은 못했는데 너무 옛날 라운드라 혹시나 했다.)

디스커션에서 나온 얘기로는, Segment tree를 이용한 풀이가 있다고 한다. 

 

BOJ 13310, KOI 2016 4번 먼 별 

난이도 : Solved ac Diamond 5

Ternary Search + Rotating Calipers를 사용한다.

즉, 각 별이 움직이는 좌표가 일차함수이므로 시점 $t$ 에서 각 별의 좌표는 $O(n)$ 시간에 쉽게 알 수 있고. 어떤 특정 시점에 최대한 먼 별은 Convex Hull + Rotating Calipers를 써서 $O(n \log n)$ 에 알 수 있다. 따라서, 수백번 이내의 '먼별 찾기' 를 써야 한다. 이런 경우에는 보통 Binary Search 또는 Ternary Search인데, 단조증가나 단조감소가 아님은 쉽게 알 수 있고, 최댓값/최솟값은 보통 Ternary Search가 잘 먹힌다는 사실을 이용해서 해볼 수 있다. 

시간 복잡도는 $O(n \log n \log T)$. 

내가 가지고 있던 로테이팅 캘리퍼스 코드에 오류가 있음을 처음 알았다. 넣어놓고 안 써봐서...