나의블로그

문제https://www.acmicpc.net/problem/2302풀이간단화: VIP가 없는 경우x ~ y - 1(1 입장권은 max(1,x-1) ~ min(N,y)이 배분될 수 있다.x = 1로 고정한다면 좌석 1 ~ y-1의 입장권은 1 ~ min(N, y)이 배분될 수 있다.y-1번 좌석은 입장권 y-2,y-1,y가 배분될 수 있고 y번 좌석은 입장권 y-1,y,y+1이 배분될 수 있다.계획y-1번과 y번 좌석에 배분 가능한 입장권이 일부 겹친다. 따라서 어떤 경우가 안되는지, 어떤 경우가 되는지 케이스 처리를 해줘야한다.y번 좌석은 y-1 ~ y+1번 입장권에 관심있지 y-2 ~ 1번 입장권에 배분이 관심이 없다. 따라서 1~y-1번 좌석에 입장권을 잘 배분하고 케이스 처리를 해주면 y번 좌석에..

문제https://www.acmicpc.net/problem/14705개요매우 단순화하면 게임은 다음 프로세스의 반복이다.지목권 A 가진 사람이 A 양도지목권 B 가진 사람이 B 양도분석1n번째에 A 지목권이 오간다면 n+2번째에 다시 A 지목권이 오간다. 이는 B 지목권에도 동일하게 적용된다.n번째에 어떤 지목권으로 지목했다면 n + 4k(k >= 0인 정수)에 같은 사람이 같은 지목권으로 지목받을 수 있다.얍샙이 플레이를 하는 두 사람(x, y)이 있다. x가 n번째에 어떤 지목권으로 y를 지목했을 때 y가 n+2번째에 x를 같은 지목권으로 지목할 수 있다. x는 다시 n + 4번째 지목에 같은 지목권으로 y를 지목 가능하다.즉 x는 n + 4k(k >= 0인 정수)번째 지목에 같은 지목권을 다시 사..

문제https://www.acmicpc.net/problem/7806 풀이1. GCD를 구하는 것은 유클리드 호제법으로 log 복잡도로 구할 수 있으나, 저 거대한 팩토리얼을 다룰 도리는 안보인다.다른 방법(정확히는 더 고전적인 방법)으로 GCD를 구할 수 있다.N의 소인수의 집합을 A, M의 소인수의 집합을 B라고 하자.I = A ∩ B, e ∈ I 라고 하자 (사실 A 또는 B 둘중 하나에 대해서 수행해도 된다.)cnt(num,x)는 소인수 x가 num에 몇개 포함돼있는지(num을 x로 몇번 나누어 떨어지게 나눌 수 있는지) 리턴하는 함수라 하자.# pythonGCD = 1for e in I: for i in range(min(cnt(N,e),cnt(M,e))): GCD = GCD ..

https://www.acmicpc.net/problem/13723 풀이양의 정수 X,Y이므로 부호에 따른 조건과 정수꼴로 나타내지는 조건(특정한 수로 나누는 것과 같은 조건)이 필요함을 추측할 수 있다1/N! = (X + Y)/XY양변에 N!XY를 곱해주자 XY = N!(X+Y)어떤 특정한 두 수를 곱하는 것으로 생각해볼 수도 있고 X와 Y의 관계로 나타내 볼 수 있다후자가 더 쉬워보이므로 후자를 해본다N!X + N!Y - XY = 0N!X + Y(N!-X) = 0N!X = Y(X-N!)N!X/(X-N!) = Y양의 정수만을 다루므로 해당 과정이 성립한다.X > N!이므로 X를 N!+k으로 생각할 수 있다. (k는 양의 정수(식을 정리해보자.X = N! + k 라면 Y = N!(N!+k)/k 이다.X는..

문제https://www.acmicpc.net/problem/1633 풀이1000C30은 매우 큰 수이다. 게다가 적절한 30명을 구했다 해도 30C15는 상당히 큰 수이다. 따라서 브루트 포싱은 통하지 않는다.새로운 플레이어가 후보로 들어왔다고 하자. 현재 백은 x명, 흑은 y명이 선출했다.후보가 백이 된다면 백은 x+1, 흑은 y명이 될테고, 후보가 흑이 된다면 백은 x, 흑은 y+1명이 될 것이다.새로운 점수는 (백 x명, 흑 y명으로 구성 했을 때 점수) + 후보의 백 능력치 or (백 x명, 흑 y명으로 구성했을 때 점수) + 후보의 흑 능력치후보의 능력치와 관계없이 백 x명, 흑 y명으로 구성했을 때 점수는 최대가 되는 것이 최적이다. 그렇게 새로운 후보가 들어와도 결과적으로 적절한 팀을 구성..

문제https://www.acmicpc.net/problem/11834 풀이짝수와 홀수가 반복되는 것을 하나로 묶고 각각의 그룹을 레이어라 하자.레이어1: 1레이어2: 2 4레이어3: 5 7 9...문제의 정의대로 각 레이어에 공차가 2인 등차 수열이 들어있다.레이어 i와 i+1의 관계를 알아보자.레이어 i의 시작을 s(i), 레이어 i+1의 시작을 s(i+1)라고 하자.해당 관계가 성립한다.s(i) + 2*(i-1) + 1 = s(i) + 2i - 1 = s(i+1)따라서 s(i+1) - s(i) = 2i - 1그럼 각 레이어의 시작을 구할 수 있다.s(1) = 1s(i) = s(1) + (1 + 3 + 5 + ... + 2(i-1)-1) = 1 + (i-1)^2N이 어떤 레이어 L에 속하는지 알려면,..

문제 https://www.acmicpc.net/problem/31741 풀이 쉬운 문제 가정 2개만을 이용해 구간을 덮는 문제의 풀이 선분을 2개로 나눈다. a. 시작점이 S이하인 선분을 담는 배열 A b. 끝점이 E이상인 선분을 담는 배열 B A를 순회하며 B에서 이분 탐색으로 다음을 찾는다. 이분 탐색을 위해 B를 시작점을 기준으로 정렬한다. B의 시작점이 A의 끝점 이하인 선분 중 시작점이 제일 큰 선분 = B에서 시작점이 A 초과인 선분의 바로 전 인덱스 선분 찾기 이를 통해 오차의 최솟 값을 구할 수 있다. 이는 B를 순회하며 A에서 이분 탐색으로 A의 끝점이 B의 시작점 이상인 선분 중 끝점이 제일 작은 선분을 찾는 것으로도 풀 수 있다. 원래 문제로 돌아가기 추가적인 선분 분류를 만든다. ..

문제 https://www.acmicpc.net/problem/20500 풀이 나머지 연산은 곱과 합이 성립한다. N자리 모든 수들의 나머지는 0~14이다. number(n)을 어떤 1과 5로만 이루어진 n자리 자릿수 중 하나라고 하자. 숫자가 1과 5만 올 수 있다는 것은 10^(n) + number(n) (1을 맨 앞에 붙힘) 5*10^(n) + number(n) (5을 맨 앞에 붙힘) n + 1 자릿수는 이 두개의 수가 올 수 있다는 것이다. 나머지 연산은 곱과 합이 성립한다. 따라서 두 수의 나머지는 10^(n) % 15 + number(n) % 15 5*10^(n) % 15 + number(n) % 15 해당 성질에 의해 dp로 문제를 풀 수 있다. dp(i,j) = dp(i,j) + dp(i-..

문제 https://www.acmicpc.net/problem/2381 풀이 두 점 사이의 최대 맨하탄 거리를 구하는 문제이다. 맨하탄 거리는 유클리드 거리에 비해 식이 간단하다(?) 따라서 절대값에 따라 식을 정리할 수 있다. 두 점 (x1,y1),(x2,y2)의 맨하탄 거리는 |x1-x2| + |y1-y2|이다. x1 - x2 + y1 - y2 = (x1+y1) - (x2+y2) x1 - x2 - y1 + y2 = (x1-y1) - (x2-y2) -x1 + x2 + y1 - y2 = -(x1-y1) + (x2-y2) -x1 + x2 - y1 + y2 = -(x1+y1) + (x2+y2) 위 네개의 케이스의 최댓값을 구하기 위해 x,y의 합과 차가 필요하고, 그것을 기준으로 정렬하면 된다. 결론적으로,..

문제 https://www.acmicpc.net/problem/31478 31478번: 포니 양은 놀고 싶어! 첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$) www.acmicpc.net 풀이 1. 분할정복 거듭제곱을 알아야한다. x^y % R을 구할때 log(y)복잡도로 구할 수 있다. 2. 모듈러 역원을 알아야한다. R이 소수일때 x^(R-2) % R = x^(-1) % R 이다. 이 두개만으로 후자는 구할 수 있다. (B^C % R * A^(7-2) % R) % R 이다. 7은 소수기때문에 모듈러역원을 적용가..