180921 ARC CD밀기 #003

2018. 9. 21. 12:17알고리즘 문풀/AtCoder 연습


편 ㅡ 안



이번에 푼 문제 (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\)개 칠하면 된다.

 


'알고리즘 문풀 > AtCoder 연습' 카테고리의 다른 글

ARC098 E. Range Minimum Queries  (3) 2018.10.15
ARC100 E. Or Plus Max  (0) 2018.10.04
ARC099 E Independence & 재밌는 완전그래프 문제들  (2) 2018.09.29
180921 ARC CD밀기 #003  (0) 2018.09.21
180919 ARC CD밀기 #002  (0) 2018.09.19
180914 ARC CD밀기 #001  (0) 2018.09.15