180919 ARC CD밀기 #002

ARC는 언제나 어렵다ㅏㅏㅏ

오늘만 푼 문제는 아니고, #001을 올린 뒤부터 풀어낸 문제들.

1편 링크

이번에 푼 문제 (5 / Total 11)

ARC097C K-th substring

ARC094C Same Integers

ARC093C Traveling Plan

ARC101D Equal Cut #Editorial 봄... 근데 생각해 낸 풀이랑 같았다. 증명해볼걸ㅠ

ARC094D Worst Case #맞왜틀 끝에 Editorial 봄. (180919 21:15 추가)

고민중인 문제 : 

ARC099D Snuke Number #Editorial 아직도 이해 못함

ARC097D Equals

ARC095D Binomial Coefficient

---

ARC094C. Same Integers

50 이하의 세 정수 A, B, C가 주어진다. 이 중 둘을 골라서 1씩 더해주거나, 하나만 골라서 2를 더해줄 수 있다. 이 때 세 정수를 같게 하기 위한 최소 횟수를 찾아야 한다.

어차피 \(\max(A,B,C)\)는 51 이상으로 커지지 않는다. 따라서 \(O(A^3)\)의 공간에서 BFS를 돌려주면 된다. 노드당 에지는 최대 6개.

근데 솔직히 이 풀이 마음에 안 든다... 그리디 풀이를 찾고 싶어서 포스팅.

(18.09.19 20:45 추가) : 

그리디도 아니고 constructive한 풀이가 있었다.

\(A > B > C\)라고 하자. 세 정수의 최종값 \(X\)는 \(A + 1\)또는 \(A\)이고, 답은 \((3X-A-B-C)/2\)이다.

---

ARC101D. Equal Cut

ARC는 왜 \(O(N)\)인 문제에 \(N \le 200,000\)을 주는 걸까?

아무튼, 양의 정수 배열을 적당히 4개의 구간으로 쪼개서 부분합을 구한 뒤, 4개 중 (최댓값) - (최솟값)이 가장 작게 해야 한다.

Naive는 \(O(N^3)\)이고, 딱히 발전할 여지가 없다.

3개의 cut 중에 뭔가 하나 고정하고는 싶은데, 왼쪽이나 오른쪽을 고정하는 건 썩 좋은 생각이 아니다. 2번째 (가운데) cut을 고정하자. 그러면 문제가 순식간에 \(O(N)\)으로 바뀐다!

가운데 cut의 왼쪽에서 나온 부분합 2개를 \(L_1, L_2\)라고 하자. 이 경우에는 \(L_1, L_2\)의 차이를 최소화하도록 첫번째 cut을 잡는게 무조건 최적이다. \(L_1 < L_2\)라고 하고 \(L_1\)이 (4개의 부분합 중) 최솟값인 경우, 둘 다 쩌리인 경우, \(L_2\)가 최댓값인 경우를 나누면 쉽게 알 수 있다.

그런데 두 번째 cut이 오른쪽으로 움직일 때, \(L_1, L_2\)의 차이를 최소화하는 첫번째 cut의 위치 또한 오른쪽으로 움직인다. 세 번째 cut또한 마찬가지이다! 따라서 전체 알고리즘을 \(O(N)\)에 돌릴 수 있다.

---

ARC094D. Worst Case (180919 21 : 15 추가)

열심히 사풀을 잡고 2시간을 고민했지만 알고리즘이 틀렸었다. Editorial을 기준으로 설명.

\(A \le B\)라고 두자.

\(A = B\)인 경우, '나'를 한 번이라도 이겼던 사람들만 후보가 될 수 있으므로 답은 최대 \(2A-2\)이다.

\(2A-2\)짜리 실례는 \((1,2A-1),(2,2A-2),\cdots (A-1,A+1)\) + 대칭으로 충분하다.

\(A + 1 = B\)인 경우, 역시 답의 상한은 \(2A-2\)이다. 첫 대회 \(A\)등에는 이미 내가 있고, \((A+1,A)\)는 나와 동률을 이루기 때문.

\(2A-2\)짜리 실례도 비슷하게 잡을 수 있다.

\(B > A+1\)인 경우를 생각하자. 여기서도 왠지 \(A,B\)를 비슷하게 만들면 비교하기 수월할 것 같다. \(C^2 < AB\)를 만족하는 최대의 \(C\)를 가정하자. 즉 두 대회에서 모두 \(C\)등을 한 '가상의 사람'을 상정한다. 이 경우 답의 상한은 \(2C\)개 근처임을 알 수 있다. \((C+1,C+1)\)이 나를 이길 수 없기 때문. 이제 문제는 \((C,C+1)\)이나 \((C+1,C)\)가 된다.

\(C(C+1) \ge AB\)인 경우는 \(A < C < B\)가 성립한다. 첫 대회에서 \(C\)등 이하, 두 번째 대회에서 \(C+1\)등 이하의 성적을 기록한 경우는 나를 이길 수 없고, 남는 \(2C-1\)번째 후보 중 한 명은 반드시 나이므로 답은 최대 \(2C-2\)개 이하로 좁혀진다. 실례를 만들 때는 \(A < C < B\)임을 생각하며 \((A-i, B+i) \ (1 \le i \le A-1)\), \(k,2C-k) \ (k = A+1 \cdots 2C-1)\)으로 잡아주면 된다. \(C < \sqrt{AB} < \frac{A+B}{2}\)가 성립함에 주목하자.

\(C(C+1) < AB\)인 경우 마찬가지로 답이 \(2C\)개 이하로 좁혀지는데 그 중 한 명은 나다. 따라서 상한은 \(2C-1\). 실례도 비슷한 꼴로 잡아주면 된다.