PS | CP

[17477] 수열과 쿼리 29

%2021. 11. 30. 18:38에 작성된 글입니다% https://www.acmicpc.net/problem/17477 17477번: 수열과 쿼리 29 길이가 N인 수열 A1, A2, ..., AN이 주어지고, Bi = 0를 만족하는 길이가 N인 수열 B가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = Ai + X를 적용한 www.acmicpc.net 한 9개월 전에 도전하다 때려치우고 오늘 다시 잡은 문제인데 결국 풀었다. 쿼리 꼴을 보아하니 '그들만의 웰노운' 세그비츠를 써야 할 것 같다. \(max, min, smax, smin, cmax, cmin\)과 함께 즐거운 세그트리를 짜자. 수열 B를 어떻게 할까 고민을 좀 했다...

[12728] n제곱 계산

%2021. 11. 20. 04:01에 작성된 글입니다% https://www.acmicpc.net/problem/12728 12728번: n제곱 계산 이 문제에서 숫자 (3 + √5)n 에 대한 소수점 앞에 마지막 세 자리를 찾아야합니다. 예를 들어, n = 5 일 때 (3 + √5)5 = 3935.73982 ... 이므로 답은 935입니다. n = 2 인 경우 (3 + √5)2 = 27.4164079 … 이므로, www.acmicpc.net 깡계산은 어림도 없다. 일단 \(3+\sqrt 5\)의 모양을 보아 하니 \(3-\sqrt 5\)도 같이 딸려나와야 뭐가 될 것 같아 보인다. 이차방정식 켤레근? 뭐 이런 느낌으로 탁 튀어나올 수 있기야 있겠다만서도 사실 처음부터 이걸 잡고 가야겠다는 생각이 바로..

[1196] 잭 바우어

%2021. 11. 11. 19:53에 작성된 글입니다% https://www.acmicpc.net/problem/1196 1196번: 잭 바우어 첫째 줄에 N과 K가 주어진다. N은 1018보다 작거나 같은 자연수이고, K는 N보다 작거나 같은 자연수이다. www.acmicpc.net \(H_n=\sum _{k=1}^n\frac{1}{k}\)​ \(f\left(n,\ k\right)=N\left(H_n-H_{n-k}\right)\)​ \(f(n, k)\)가 문제를 풀기 위해 코딩해야 하는 함수인데... naive하게 구현하면 시복도 \(O(N)\)이 나올 것이고 \(N\)의 범위는 \(10^{18}\) 이하 자연수니까 무리 없이 \(T\ L\ E\)를 받아낼 수 있으리라... 분명 근사가 가능할 것 같..

[16282] Black Chain

%2021. 11. 11. 16:04에 작성된 글입니다% https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 1. 고리를 \(n\)번 분리하면 \(w=1\)인 고리가 \(n\)개 생긴다. 2. \(w=1\)인 고리 뭉탱이로 만들 수 있는 최대 무게는 \(n\)이다. 3. 따라서 \(n+1\)짜리 고리가 있어야 그보다 더 무거운 무게를 구성할 수 있다. 4. \(w=n+1\)짜리 고리와 \(w=1\)인 고리를 모두 선택하면 무게..

[10436] 무한 유리수 트리

%2021. 11. 10. 01:32에 작성된 글입니다% https://www.acmicpc.net/problem/10436 10436번: 무한 유리수 트리 무한 유리수 트리는 완전 이진 트리이며, 다음과 같이 정의된다. 루트는 1/1이다. p/q의 왼쪽 자식은 p/(p+q)이다. p/q의 오른쪽 자식은 (p+q)/q이다. 트리의 첫 세 층은 아래와 같이 구성된다. 이 무한 www.acmicpc.net 루트까지 올라갔다 내려와서 편하게 해결 보려는 생각은 꿈도 꾸지 말자. \(O(N)\)이라도 범위가 2147483647인지라... 주어진 값에서 바로 해결을 봐야 한다. 대단한 알고리즘은 없고 그냥 어디 종이 가지고 와서 트리 죽 적어본 뒤에 규칙을 찾으면 된다. 대부분의 경우에 간단하게 해결이 되고, 주..

[13705] Ax+Bsin(x)=C

일단 태그에서부터 임의 정밀도/큰 수 연산이 붙어 있으니 고생 좀 해야 하겠다... 만! 이런 끔찍한 문제들은 보통 python의 Decimal로 해결한다. ​ c/cpp로 구현하는 것도 불가능한 건 아니고 실제로 적잖은 AC가 있긴 하다... 언제 따로 cpp bigint를 따로 구현해봐야겠다. ​ 꽤 높은 수준의 정밀도를 요구하는 문제기 때문에 기본적으로 지원하는 sin함수를 써서는 안 된다. 테일러 전개를 활용해 새로 함수를 짜야 한다. 파이 값도 중요해서 인터넷에서 몇백자리 긁어다 Decimal에 때려박았다. $Ax+B\sin x\ (A \geq B)$는 미분해서 보면 전체 구간에서 증가함을 알 수 있으므로 이분 탐색을 쓸 수 있다. Decimal로 잡고 st en mid 돌려가며 구했다. ​ 이..

[19577] 수학은 재밌어

%2021. 11. 9. 00:30에 작성된 글입니다% https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 오일러 피 함수라는 걸 여기서 처음 봤다. 대충 위키에서 본 내용에 따르면 이 함수는 아래의 성질을 갖는다고 한다. \(\gcd \left(a,b\right)=1\)일 때, \(\phi \left(ab\right)=\phi \left(a\right)\phi \left(b\right)\)​ \(\phi \left(p^n\right)=p^n\left(1-\frac{1}{p}\right)=p^{n-1}\left(p-1\right)\..

[1007] 벡터 매칭

%2021. 11. 5. 14:39에 작성된 글입니다% https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 풀어보려고 전부터 꽤 노력했는데 결국 고등학교 기하를 배우고 나서야 풀 수 있었다. 벡터의 성질을 맨바닥에서 끄집어낼 수준의 머리는 안 되는 모양이다. 주어진 점을 각각 \(P_1, P_2, P_3... P_n\)이라고 하자. 임의의 점 P를 하나 잡고, \(\overrightarrow{PP_1}, \overrightarrow{PP_..