180921 ARC CD밀기 #003

편 ㅡ 안

---

이번에 푼 문제 (4 / Total 20) #기존에 풀어둔 ARC문제를 이번에 포함시킴

포스팅하는 문제만 볼드.

ARC099D Snuke numbers

ARC097D Equals

ARC095D Binomial Coefficients

ARC093D Grid Components

고민중인 문제

ARC099E. Independence

ARC101E. Ribbons on Tree

---

ARC099D. Snuke Numbers

자릿수합 함수 \(S(n)\)에 대해서, \(\forall m > n \frac{m}{S(m)} < \frac{n}{S(n)}\)을 만족시키는 \(n\)을 Snuke number라고 한다. 최소 \(K\)개의 Snuke Number를 찾아야 하고, \(K\)번째 Snuke Number가 \(10^{15}\)보다 작음이 보장되어 있다.

\(f(N)\)을 \(N\)이상의 수 중 조건을 만족하는 최소의 수라고 하자.

\(N = 1\)에서 시작해서 \(N \leftarrow f(N+1)\)을 계속 반복하면 된다.

이제 \(f(N)\)의 후보를 줄여보자.

\(N\)을 \(a_{1}a_{2}\cdots a_{k}\) (자릿수) 라고 할 때, \(999\cdots 9\)는 무조건 Snuke Number가 된다.

또 무조건 \(n \ge S(n)\)이고, \(a > b\)인 경우 \(\frac{a}{b} > \frac{a+1}{b+1}\)이 성립하므로 Snuke number의 후보는 \(a_{1}a_{2}\cdots a_{j}99\cdots 9\)로 제한된다. 따라서 많아야 \(\log N\)개 정도의 후보가 생기고, 결국 전체 복잡도 \(K \log (10^{15})\) 정도 안에 문제를 풀 수 있다.

---

ARC097D. Equals

길이 \(N\)의 순열 \(p\)가 주어져 있다. \(M\)개의 pair를 각각 원하는 횟수만큼 swap할 수 있을 때, \(p_i = i\)인 \(i\)의 개수를 최대화시켜야 한다.

swap-able한 pair들을 그래프의 간선으로 생각하자. 이 때 그래프의 connected component 안에서는 자유롭게 점을 이동시킬 수 있음을 알 수 있다. 즉, connected component 안에서 고정점은 다 '고정'시킬 수 있다.

따라서 union-find로 connected component를 구하고, \(i\)번째 정점과 숫자 \(i\)가 적힌 정점이 같은 component에 있는지 보면 된다. 시간복잡도는 \(M\alpha (N)\).

---

ARC093D. Grid Components

최대 \(100 \times 100\) 그리드를 black-white로 칠한다. black-component가 \(A\)개. white-component가 \(B\)개가 되게 해야 한다. \(A, B \le 500\).

뚜벤한테 힌트를 받고 풀었다.

그리드의 왼쪽 절반을 black, 오른쪽 절반을 white로 칠하자. black으로 칠한 부분에 row, column 모두 2씩 띄어 가면서 white를 \(A-1\)개 칠하고, white에는 똑같이 \(B-1\)개 칠하면 된다.