분류 전체보기

[14346] Radioactive Islands (Small)

14346번: Radioactive Islands (Small) The first line of the input gives the number of test cases, T; T test cases follow. Each test cases consists of two lines. The first line of a test case consists of three values: an integer N, and two floating-point numbers A and B, as described in www.acmicpc.net 일단 배의 궤적은 함수로 나타낼 수 있다. 말인즉슨, 궤적은 \(x\) 좌표 하나에 한 개의 점만 대응된다는 뜻이다. 만약 \(x\)좌표 하나에 여러개의 점이 대응된다고 해보..

[16136] 준하의 정수론 과제 (Divmaster)

%2021. 12. 6. 05:11에 작성된 글입니다% 16136번: 준하의 정수론 과제 (Divmaster) 준하는 3학년 2학기 때 들으려고 했던 정수론을 수강신청을 잘못하는 바람에 2학년 1학기 때 신청하고 말았다! 사악한 정수론 선생님은 자연수의 약수의 개수를 구하는 문제를 던지고, 이 문제 www.acmicpc.net Divmaster가 무슨 뜻일까? 해당 div에서 가장 어려운 문제였다는 말일까? 아무튼 쿼리 처리하는 문제다. 쿼리 모양새를 보니 세그트리를 쓰면 좋을 것 같다. 일단 에라토스테네스의 체를 약간 응용해서 \(1\)~\(10^6\)까지 약수의 개수를 구할 수 있다. 이거 어디 담아놓고서 나중에 필요할 때 꺼내먹으면 된다. 노드는 구간의 합과 died라는 이름의 bool 변수를 갖게..

[4357] 이산 로그

%2021. 12. 5. 23:18에 작성된 글입니다% 4357번: 이산 로그 소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으 www.acmicpc.net \(B^L\equiv N\mod P\)​ 를 만족시키는 \(L\)을 찾자. Babystep Giantstep으로도 알려진 Shanks’ Algorithm을 사용하면 된다. \(L=ax+b\)​ \(B^{ax+b}\equiv N\mod P\)​ \(B^{ax}\equiv B^{-b}N\mod P\)​ 페르마의 소정리에 따라 \(B^{-1}\equiv B^{P-2}\m..

[2261] 가장 가까운 두 점

%2021. 12. 3. 10:13에 작성된 글입니다% 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 분할 정복의 대표적인 예제로 많이 쓰이는 문제인 것 같던데 스위핑으로 푸는 게 아이디어 잡기도 구현도 훨씬 나은 듯. 약간의 데이터 처리와 이분 탐색 스위핑으로 그냥 풀린다. 분할 정복으로 풀면 P2-P1일지도 모르겠는데 스위핑으로 풀면 P2-P1 수준까지는 아닌듯... 내가 스위핑으로 풀었으니까 여기에는 스위핑 풀이 적음 ​ 전반적인 흐름: x 값이 작은 점부터 큰 점까지 ..

[2595] 배수

%2021. 12. 1. 22:47에 작성된 글입니다% 2595번: 배수 N은 30,000이하의 자연수이다. www.acmicpc.net 05KOI 지역본선 고등부 5번이랜다... 뻘짓을 좀 하긴 했는데 여튼 푸는 데만 거의 3시간을 갖다 박았으니 아직 KOI 지역 수준에도 못 미치는 것이다. 안타깝다. ​ 문제를 푸는 데 중요한 사실은, 조건을 만족하는 출력은 모두 숫자의 종류의 수(이하 cnt(x)로 씀)가 1 혹은 2라는 것이다. 증명은 모르겠다. ​ 1인 경우에는 당연히 1111, 33333333, 77777 따위의 수가 될 것이고, 2는 3333300000000, 44444440, 20220222220, 2882828, 5555555550 뭐 이런 식의 형태이다. ​ 1. 수에 10의 배수가 있..

[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\)를 받아낼 수 있으리라... 분명 근사가 가능할 것 같..