PS | CP

[2731] 1379와 세제곱

2731번: 1379와 세제곱 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 www.acmicpc.net 뭔가 허무하게 풀리는 정수론 문제. 우선 문제에서 준 네 수 1, 3, 7, 9를 살펴보자면, $1^3\equiv 1\bmod 10$ $3^3\equiv 7\bmod 10$ $7^3\equiv 3\bmod 10$ $9^3\equiv 9\bmod 10$ 이다. 따라서 $S \bmod 10$의 값으로 찾아야 하는 수 $x$의 첫째 자릿수를 구할 수 있다. ($x_1$) 이제 한 자리씩 $x$의 왼쪽에 붙이면서 수를 찾으면 되는데, 방법은 다음과 같다. ${..

Codeforces 민트 달성!

%2022. 1. 31. 12:11에 작성된 글입니다% 어제 있었던 Codeforces Round # 769 (Div. 2)에서 빠른 3솔을 하고 83점을 얻어 민트로 올라왔다. 27일에 있었던 div2 # 768에서는 잠을 못 잔 채로 풀어서 실수투성이 2솔밖에 못 했는데 이번에는 괜찮게 나와줘서 다행이다. 이제 딥2는 4솔을, 레이팅은 블루를 목표로 달려 보자... 기초 알고리즘 DP나 그래프 탐색같은거 연습 좀 해야 할 듯.

오랜만에 Codeforces

%2022. 1. 4. 12:19에 작성된 글입니다% 원래 CF를 잘 안 했다. 시간 재면서 경쟁하는 stress 하의 상황에서 문제를 풀기보다는 천천히 고민하면서 풀기를 더 선호하기도 하고, 또 contest 열리는 시간이랑 내 시간대랑 잘 안 맞아서도 그랬고... 아무튼 오랜만에 들어가보니 Hello 2022 contest가 내일 열립니다! 하길래 이번엔 좀 참가해보자... 하고 register 해 놨다. 그리고 나서 대회 한시간 전에 interactive problem guide 문제 풀어보고 시간 맞춰서 대회 들어갔다. 결과는... 망했다. A랑 C 풀고 이상한 세그트리 짜다가 시간 다 버림. ㅠㅠ BOJ에서 시간 생각 안 하고 풀 때랑은 또 달라서 재밌었다. 당분간 코포도 좀 해야겠다. 블루나 ..

[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부터 쭉 뿌리고 가능/불가능 본 뒤에 이거 소수 반토막 아님? 해서 알았다... 머리가 나빠서 컴퓨터가 고생함 ㅋㅋ