원 안에 원을 가득 채우는 문제?(circle packing in a circle)

20744번: Cucumber Conundrum (acmicpc.net) 반지름이 s인 원 모양의 샌드위치가 있고 반지름이 r인 원 모양의 피클이 n개 있는데  이 피클을 샌드위치 위에 최대한 많이 높고 싶다 이 때 샌드위치 면적의 최대 z%까지만 놓을 수 있고 두 피클이 서로 겹치지 않아야한다 최대 몇개의 피클을 놓을 수 있는가? 샌드위치의 면적이 $\pi * s^{2}$이고 이것의 최대 z%가 피클 x개의 넓이 $\pi * r^{2} * x$이므로  $$\pi * s^{2} * \frac{z}{100} >= \pi * r^{2} *x$$  식을 정리하면 $x  사실 이것만 만족하면 되는줄 알았는데... 아니더라고 https://en.wikipedia.org/wiki/Circle_packing_in_a_..

• format_list_bulleted 기하학
• · 2024. 7. 27.
• textsms

경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)  일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때,  어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다    N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..

• format_list_bulleted 조합론
• · 2024. 7. 26.
• textsms

n,m이 매우 클 때 (a1a2a3...an)/(b1b2b3...bm) 분수를 계산하는 마법같은 방법

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_{..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 7. 25.
• textsms

홀수 위치 자리수들과 짝수 위치 자리수들의 곱이 서로 같은 n자리 자연수 찾는 마법같은 방법(중간에서 만나기)

14108번: Umnozak (acmicpc.net) n자리 자연수중에서 짝수 위치의 자리수들의 곱과 홀수 위치의 자리수들의 곱이 서로 같게되는 그러한 자연수들의 개수를 구하는 문제 첫번째 자리는 홀수 위치라고 가정 1자리 자연수는 홀수 위치밖에 없으니 0개 2자리 자연수는? 11,22,33,44,55,66,77,88,99로 9개 3자리 자연수는? 100부터 999까지 전수조사해보는게 나을 것 같다 count = 0for i in range(100,1000): s = str(i) a = 1 b = 1 for j in range(len(s)): if j % 2 == 0: a *= int(s[j])..

• format_list_bulleted 중간에서 만나기
• · 2024. 7. 24.
• textsms

n번째로 작은 팰린드롬 수를 찾는 놀라운 방법

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..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 7. 23.
• textsms

누적 합으로 i < j < k < l을 돌아버리는 미친 다이나믹 프로그래밍 테크닉

25427번: DKSH를 찾아라 (acmicpc.net) 문자열 S가 주어질때, 인덱스 a  N이 10만이라 4중 for문으로 찾으면 당연히 시간초과 문자열이 'DDDDKKK'로 이루어질때, 만들 수 있는 'DK'의 개수는? 인덱스를 기준으로 세볼 때 (0,4), (0,5), (0,6) (1,4), (1,5), (1,6) (2,4), (2,5), (2,6) (3,4), (3,5), (3,6) K를 기준으로 본다면,  (0,4), (1,4), (2,4), (3,4) (0,5), (1,5), (2,5), (3,5) (0,6), (1,6), (2,6), (3,6) 처음에 D의 개수를 하나씩 세다가, K를 만나면 그 동안 만난 D의 개수를 누적해서 더해주면 된다  어떤 문자열이 주어지면, D의 위치 인덱스를 (..

• format_list_bulleted 누적 합 알고리즘
• · 2024. 7. 16.
• textsms