https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다 사실 테크닉에 감탄해서 복기하는거긴 한..
https://atcoder.jp/contests/abc362/tasks/abc362_c C - Sum = 0AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n개의 구간 (Li,Ri)가 주어질때, 이 구간들 각각에서 정수 Xi를 하나 골라 n개 합쳐서 0을 만들 수 있는지? 그렇다면 그러한 정수 배열을 하나 찾는 문제 먼저 그러한 정수 배열이 존재하는지 알 수 있을까? 이것부터 어렵더라고 근데 생각보다 간단했다 $$L_{1} $$L_{2} ... $$L_{n} 이들을 합해도 부등식이 유지되므로, $$\sum_{i =..
28828번: Упражнения в умножении (acmicpc.net) $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2) 곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..
https://atcoder.jp/contests/abc363/tasks/abc363_d D - Palindromic NumberAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n이 최대 10^18까지라서 보통의 방법으로는 찾을 수 없다는 것이 느껴진다 그래서 일단 가능한 팰린드롬 수를 차례대로 나열해본다 0,1,2,3,4,5,6,7,8,9 >>> 10개 11,22,33,44,55,66,77,88,99 >>> 9개 101, 111, 121, 131, 141, ... ,191202,212,222,232,..., 292303..
D - Another Sigma Problem (atcoder.jp) D - Another Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 배열 A의 모든 순서쌍 (A[i],A[j])에 대하여 f(A[i],A[j])를 A[i]A[j]라고 정의 예를 들어 f(10,1) = 101이고 f(3,14) = 314 i 예를 들어 3 14 15라면 (3,14), (3,15), (14,15) 3개의 순서쌍에 대해 314, 315, 1415가 있고 이들의 합은 2044 모든 순서쌍을 찾는 것은 기본적으로 $O(..
C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp f(x,y) = x + y를 $10^{8}$로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i 예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
