전체 글

[20500] Ezreal 여눈부터 가네 ㅈㅈ

%2022. 2. 3. 21:40에 작성된 글입니다% 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제 ​ 15의 배수이려면 5의 배수이면서 3의 배수여야 한다. 어떤 자연수 \(N\)에 대하여, \(5\mid N \iff N\mod 10 = 0\ or\ 5\), \(3\mid N \iff 3\mid DigitSum(N)\) 만들어야 하는 수는 1과 5로만 구성되어야 하므로 첫째 자리는 무조건 5다. 이후에는 DP 배열을 만들어서 채워나가는데, \(DP[N][m]\) = 길이가 \(N\)이고 (모든 자리의 수의 합) \(\equiv m\mod 3\)인 수들의 갯수로 두어 1 혹은 5를 더해나가면 ..

[22901] ko_orange

%2022. 2. 2 17:36에 작성된 글입니다% 22901번: ko_orange 당신의 출력을 즉각적으로 채점 프로그램에 전달하기 위해, 당신은 모든 출력 뒤에 출력 버퍼를 비워야 한다. 언어별로 출력 버퍼를 비우는 방법은 아래와 같다. C: fflush(stdout); C++: std::cout.flush(); www.acmicpc.net 우선 거짓 응답이 들어오지 않는다고 가정하면 \(\lceil \log_2 300\rceil = 9\)회 탐색을 진행하면 된다. \(q=18\)의 경우 응답이 \(1\)일 때 한번 더 요청을 넣어줘서 확인하면 된다. \(2399\)의 경우에는 전부 \(1\)이니까 \(18\)번 나온다. 그 후에 관찰을 열심히 하면 발견할 수 있는 것들은: 1. 일단 응답 \(0\)..

[2014] 소수의 곱

%2021. 1. 26. 20:02에 작성된 글입니다% 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 1. priority queue로 \(N \log N\)컷. 2. 해가 \(2^{31}-1\)보다 작음이 보장됨. 3. 2 => 10 / 5 => 10. 중복 제거를 해야 함. 애초에 값을 넣을 때 중복되지 않도록 넣는 방법이 없을까?

[10908] Phibonacci

\({\phi }^2={\phi }+1\)​ \(-1={\phi }-{\phi }^2\)​ \(P_n=F_n{\phi }+F_{n-1}\) \(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^n{\phi }}{\sqrt{5}}+\frac{{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\) \(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^{n-1}\left({\phi }-{\phi }^2\right)+{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\) \(=\large{\frac{{\phi }^{n+1}+\left(1-..

[5615] 아파트 임대

%2022. 1. 12. 01:05에 작성된 글입니다% 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 1. \(S = 2xy + x + y\) \(2S + 1 = ?\) 2. \(N = 100,000\)이고 시간 제한 1초. \(\log\) 수준의 시복도를 갖는 소수판정법 필요. 밀러-라빈! 남들은 인수분해 척척 했던 것 같은데 나는 S를 1부터 쭉 뿌리고 가능/불가능 본 뒤에 이거 소수 반토막 아님? 해서 알았다... 머리가 나빠서 컴퓨터가 고생함 ㅋㅋ

[18507] One Root

%2022. 1. 10. 21:27에 작성된 글입니다% 18507번: One Root The only line of input contains two integers n and m (1 ≤ n, m ≤ 106, n ≥ 2). www.acmicpc.net \(x^n=ax+b\)​ 주어지는 2 이상의 \(n\)에 대하여, 방정식의 해가 오직 하나가 되도록 하는 abs가 \(m\) 이하인 정수 \(a, b\) 쌍을 모두 구하는 문제다. 고등학교 3년 동안 지겹도록 본 꼴이라 접근은 어렵지 않았다. 우선 \(n\)이 짝수일 때와 홀수일 때로 나누어야 한다. 그래프 개형이 달라지기 때문. --- 만약 \(n\)이 짝수라면, 방정식의 해가 오직 하나가 되기 위해서는 \(ax+b\)가 \(x^n\)에 접해야 한다. ..

[23894] 합성함수와 쿼리 2

%2022. 1. 9. 00:06에 작성된 글입니다% 23894번: 합성함수와 쿼리 2 함수 $f : \{1, 2, \cdots, N\} → \{1, 2, \cdots, N\}$의 각각의 함숫값 $f(1), f(2), \cdots, f(N)$이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x : $f(1)$의 값을 $x$로 변경한다. 2 m x : $f^m (x www.acmicpc.net 여행 갔을 때 호텔에서 풀려고 잡았던 문제. 취한 상태였기 때문에 WA만 잔뜩 내고 집에 돌아와서 마저 풀었다. 쿼리 꼴 보면 sparse table 생각이 난다. 2번 쿼리는 어지간하면 \(O(\log m)\)으로 처리 가능하다는 얘기인데, 문제는 1번 쿼리. 1번 쿼리는 \(f(1)\)을 제..

[14347] Radioactive Islands (Large)

https://blog.safespot.dev/entry/14346-Radioactive-Islands-Small의 후속 문제. 거의 모든 해설은 저기 다 있고, 일단 N 상한만 2로 늘어난 상황이기 때문에 N=2인 경우에 대해서 식을 세우면 $\displaystyle \int _{-10}^{10}\left(1+\frac{1}{x^2+\left\{y\left(x\right)-c_1\right\}^2}+\frac{1}{x^2+\left\{y\left(x\right)-c_2\right\}^2}\right)\sqrt{1+\left\{y^{\prime}\left(x\right)\right\}^2}dx$ 를 최소화해야 하는 상황. 똑같이 범함수 만들면 $\displaystyle f\left(y,\ y^{\prim..