10월 말~11월 1주차에 푼 문제 풀이이다.
풀이
티어는 Platinum III.
f(S)는 S를 두 부분으로 나눴을 때 각각이 모두 팰린드롬인 경우가 몇 번인지를 의미한다.
S = A(prefix) + X이고 이게 f(S)의 조건을 만족하는 최소 i(즉 A 길이가 최소)인 경우라고 하자. 정의상 A와 X는 팰린드롬이고 A는 최소 길이이므로 A의 부분 prefix 혹은 suffix가 팰린드롬인 경우는 없다. 이제 S = C + Y이고 이게 A 다음으로 prefix 길이가 최소인 분할이라고 하자. C = A + B + A꼴일 수밖에 없다. 그런데 S = A + X = C + Y = A + B + A + Y이므로 X = B + A + Y이다. X는 팰린드롬이므로 X = B + A + ... + A + B꼴이고 Y도 팰린드롬임을 이용하면 이와 같은 논리를 쭉 적용하여 결국 S = A + B + A + B + ... + A + B 꼴이어야 한다는 사실을 알 수 있다. 이때 f(S) = k이려면 (i)A,B가 각각 k번 나오거나, (ii)B가 빈 문자열이고 A가 k+1번 반복되면 된다. (i)은 k|n인 경우에 A = "a", B = "bb..bb", |B| = n/k-1로 가능함을, (ii)는 k+1|n인 경우에 A = "ab..ba", |A| = n/(k+1)로 가능함을 알 수 있다. k=0, k=n-1, n/(k+1) = 2(A가 길이 2인 경우인데, 정의상 불가능함)인 경우에는 예외 처리가 필요하다.
BOJ 27452 (재밌고 웃기고 센스있고 깔끔한 제목)
풀이
티어는 Platinum V.
먼저 O(n) 풀이를 생각하자. S[n]의 길이 |S[n]|을 dp로 구해놓으면 k번째 문자가 S[n] = ( S[n-2] S[n-1] ) 에서 (, S[n-2], S[n-1], ) 중 어디에 속하는지 알 수 있다. 이를 이용해 타고 내려가면서 풀면 n이 1 또는 2씩 감소하므로 O(n)에 풀 수 있다.
위 풀이에서 관찰해야 할 사실은 n이 85 정도 되는 위치에서 S[n]이 10^18보다 커진다는 것이다. k <= 10^18이므로 n > 87이면 반드시 |S[n-2]| >= 10^18이 되어 k가 여기에 속하게 되고, 반드시 n이 2씩 감소한다. 이를 이용하면 O(1)에 87보다 큰 n을 홀짝성에 따라 86 또는 87로 보내버릴 수 있고 따라서 O(87T) 정도에 문제를 해결할 수 있다.
티어는 Silver I.
간단한 시뮬레이션 문제이다. 구현은 격자 그래프에서 인접한 영역 보듯이 하면 된다.
티어는 Silver I.
분수에서의 gcd를 구하는 문제이다. lcm(1~40)을 봤을 때 long long 안에 충분히 들어오는 범위이므로 분모의 lcm을 곱해준 뒤 gcd를 구하고 다시 분모의 lcm으로 나눠주면 된다.
티어는 Silver I.
x = kq + r(q,r은 정수, 0 <= r < k)일 때 x+1 = kq + (r+1) = k(q+1)이어야 하므로 k는 x+1의 약수이다. k <= x여야 하므로 x+1의 진약수를 출력하면 된다.
티어는 Diamond V.
a=0/b=0/s=0은 예외처리를 하고 시작하자. (은근 중요하다)
두 연산으로 s를 만들 수 있는 것과 ax + by = s이고 gcd(x,y) = 1, x>=0, y>=0인 x, y가 존재하는지가 동치이다. 확장 유클리드 하듯이 보이면 된다. ax+by=s는 확장 유클리드 쓰면 되는데 문제는 뒤에 조건들이다. y = (s-ax)/b이고 s,a,b,x 모두 음이 아닌 정수이므로 x가 최소일 때 y가 최대이다. 즉 최소인 x를 잡고 x+=b/g, y-=a/g 하면서 y<=0이기 전에 gcd(x,y)=1인지 보면 된다. 이게 왜 TLE가 아닌지는 본인도 이해하지 못했다. rkm0959님 블로그에 증명이 있긴 하다.
티어는 Gold I.
A=B일 때 답은 자명하게 1이다.
gcd(A+N,B+N) = gcd(A+N,B-A)이므로 gcd는 B-A의 약수이다. 즉 gcd로 가능한 후보가 O(sqrt(N))개이다.
lcm(A+N,B+N) = (A+N)(B+N)/gcd(A+N,B+N)에서 gcd가 같다면 N이 작을수록 이득이므로 각 gcd가 되는 최소의 N을 구해서 답을 갱신하면 된다.
티어는 Platinum V.
n에 비해 수의 크기가 작음을 관찰하자. gcd = k(1<=k<=100)로 고정하면 배열의 원소를 k의 배수인 경우와 아닌 경우로 나눌 수 있다. 각 원소가 k의 배수면 1, 아니면 0이라 하자. 이 때 모든 연속한 1을 maximal하게 봤을 때 gcd가 k면 k는 가능한 것이고 아니라면 불가능한 것이다. tc당 O(100Nlog100) 정도에 풀 수 있다.
티어는 Platinum III.
(i,j)를 좌표평면에 찍어보자. 그럼 (1,1)~(n,m)의 직사각형에서 (1,1)에서 출발하여 45도로 레이저를 쐈을 때 지나는 격자점의 개수를 구하는 것과 같다는 것을 알 수 있다. 몇 개를 그려보면 다양한 관찰을 할 수 있다.
1. 중복해서 세는 걸 허용할 때 지나는 격자점의 개수는 lcm(n-1,m-1) + 1이다.
2. gcd(n-1,m-1) = 1일 때 중복되는 점 개수는 (a-1)/2 * (b-1)/2 + (a-2)/2 * (b-2)/2이다. (나눗셈은 내림)
3. gcd(n-1,m-1) = g > 1이면 (n-1)/g, (m-1)/g인 경우와 중복되는 점 개수가 같다. 즉 서로소가 아니면 서로소로 만들고 중복되는 점 개수를 세준다.
이제 a=b, a=1 or b=1만 따로 처리해주면 된다.
티어는 Platinum III.
위의 BOJ 9497 - 피라미드 수열 과 완벽하게 동일한 문제이다. 풀이는 위를 참고하자.
BOJ 11635 - Wipe Your Whiteboards
풀이
티어는 Platinum IV.
먼저 확장 유클리드 호제법을 이용해 정수해를 찾는다. y = (Q-R*x)/S이고 R>=2,S<=-2,Q>=1임을 이용하면 x를 최소의 양수로 만든 다음 y가 양수가 될 때까지 적절히 올려주면 됨을 알 수 있다.
티어는 Platinum II.
점과 직선 사이의 거리 식을 잘 풀다 보면 확장 유클리드 형태가 나온다. 근데 이걸 못해서 풀이를 봤다.
티어는 Bronze III.
열심히 구현하면 된다.
티어는 Gold III.
범위가 작아서 dp로 왼손, 오른손 엄지 위치와 턴을 어떻게든 표현하면 된다.
티어는 Gold II.
케이스를 몇 개 나누자.
(i)n=k이면 n이 홀수일 때만 가능하다.
(ii)k=1이면 불가능하다.
(iii)k가 짝수이면 그냥 1부터 순서대로 채우면 된다. 1부터 k까지 합이 k(k+1)/2이기 때문에 k가 짝수면 2랑 약분되서 가능하다.
(iiii)k가 홀수이면 (iii)과 같은 논리가 불가능하다. 아래의 서술에서는 어떤 수를 k로 나눈 나머지만 서술한다. 예를 들어 1은 1, k+1, 2k+1, ... 중 하나를 나타낸다.
(1) n이 짝수라면 0 0 2 3 ... k-1 / 1 1 2 3 ... k-1 / ...과 같이 배치하면 된다.
(2) n이 홀수라면 n/k-2번째 줄까지는 (1)과 같이 하다가 마지막 두 줄을 2 0 2 ... k-1 / 0 1 0 ... k-1로 배치하면 된다.
티어는 Gold I.
가능한 문자열 쌍끼리 문자가 다른 위치를 찾고 문자열의 순서관계를 방향 그래프로 나타낸 후 위상 정렬 결과가 유일한지 보면 된다. 혹시 몰라서 문자열 비교는 해싱으로 해줬다.
BOJ 5780 - Uncle Tom’s Inherited Land
풀이
티어는 Platinum III.
체스판 색칠을 해주면 인접한 검정색 한칸과 흰색 한칸을 묶어주는 것으로 생각할 수 있고 이를 격자 그래프로 생각하면 이분 그래프에서의 최대 매칭이 답이 된다. 일반적인 이분 매칭을 구현해주면 된다.
티어는 Platinum III.
루트가 1일 때의 답을 구하는 방법을 생각해보자. lca(a,b) = i일 때 a와 b는 i의 서브트리에 속하며 i의 자식의 서브트리에 같이 속하면 안된다. sz[i]를 i의 서브트리 크기, A[i]를 i의 자식들의 sz 합, S[i]를 i의 자식들의 sz*sz 합이라 하면 ((sz[i]-1)*A[i] - S[i])/2 + sz[i]-1이 된다. (그냥 시그마를 푼 것이다.) 이제 오프라인으로 쿼리를 처리한다고 생각하고 rerooting dp를 해주면서 sz, A, S를 변경하면서 답을 구하면 된다.
티어는 Platinum II.
(L,R) pair 기준으로 정렬하자. 먼저 관찰해야하는 사실은 i<j이면 L[i]<L[j], R[i]<R[j]라고 가정해도 된다. 그렇지 않고 한 직선에 포함되는 직선을 고를 이유가 없기 때문이다. 그러면 dp[i][j] := i번 직선까지 j개를 골랐을 때 최대 합집합 으로 정의하면 dp 식이 이전 직선과 겹치는지 여부에 따라 갈리는데 식 하나는 그냥 최댓값을 관리해주고 하나는 덱을 이용해서 구간 최댓값을 관리해주면 선형에 풀 수 있게 나온다.
티어는 Platinum III.
x xor x = 0임을 이용하면 몇가지 케이스를 나눠서 trie로 xor 최댓값을 구해주면 됨을 알 수 있다. 디테일은 기억 안나서 생략
티어는 Diamond IV.
일단 브릿지(단절선)를 찾아야 한다. dfs spanning tree에서 자식이 현재 이상으로 올라올 수 있는지를 보면 된다. 이제 bridge가 아닌 간선만 남겼을 때 컴포넌트를 하나의 정점으로 생각하면 bridge를 간선으로 하는 압축된 하나의 트리가 나온다. 여기서 BOJ 30028을 풀어주면 된다. 이 문제의 풀이는 이전에 블로그에 작성한 적 있지만 이보다 훨씬 깔끔한 풀이를 찾아 여기선 이 풀이를 서술하겠다.
리프의 개수를 L이라 하자. 리프가 아닌 정점을 루트로 잡고 리프를 dfs ordering 순서로 놓은 다음 i번 리프와 i+ceil(L/2)번 리프를 이어주면 된다. (i < ceil(L/2)) 이게 가능한 이유는 은근 간단한데, i와 i+ceil(L/2)을 이었으므로 그 사이 정점들도 같이 속하게 되고 그 사이 정점들도 ceil(L/2)칸씩 떨어진 리프를 가지고 있으므로 결국 모든 정점들이 엮이게 되기 때문이다. 외워두면 언젠가 쓸만한 내용이라고 생각한다.
티어는 Gold I.
다익스트라를 돌리는데 (x,y,방향)을 state로 잡고 하면 된다. 회전은 빡구현하면 된다.
BOJ 28146 - Broken Minimum Spanning Tree
풀이
티어는 Platinum IV.
앞에 n-1개의 간선에 우선순위를 두고(가중치가 같으면 이걸 먼저 사용) 크루스칼을 돌리자. 이제 열심히 구현해서 연결성을 유지하면서 간선을 대체하도록 하면 된다. 연결성 증명이 쉽지 않아 보이는데 대회 환경에서는 일단 직관이 최선인 것 같다.
티어는 Platinum IV.
배열을 뒤집어서 생각하자. dp[i] : i에서 끊기 시작할 때 최소 페이지 수 정도로 정의하면 끊는 것이 가능한 위치를 찾기만 하면 세그먼트 트리로 최적화 가능한 식이 나온다. 즉 뒤에 연속한 k개의 0이 있는 위치를 구해놓고 dp를 하면 된다.
BOJ 3413 - The Dragon and the knights
풀이
티어는 Platinum II.
핵심은 직선 기준으로 점이 위에 있는지 밑에 있는지 보는 것이다. x=a꼴이 아닐 때는 y가 더 크면 직선보다 위에 있다고 하고(U), x=a 꼴일때는 x가 더 작으면 직선보다 위에 있다고 하자(U). 아니면 아래에 있다고 하자(D). 이제 모든 점은 U와 D로 이루어진 문자열로 나타낼 수 있다. 이 때 서로 다른 문자열의 종류가 직선에 의해 나누어진 구간의 개수와 같은지 보면 된다. 직선에 의해 나누어진 구간의 개수는 (직선의 개수) + (직선끼리의 교점의 개수) + 1이고 따로 구해주면 된다.
BOJ 15589 - Lifeguards (Silver)
풀이
티어는 Gold I.
먼저 선분 합집합부터 구하자.
만약 한 선분에 완전히 포함되는 선분이 있으면 그냥 걔를 지우면 된다. 아니면 어떤 선분을 지웠을 때 합집합이 얼마나 감소하는지를 구하면 되고, 인접한 직선끼리만 봐주면 되서 쉽게 구할 수 있다.
티어는 Platinum II.
일단 최대인 경우를 생각해보자. 아마 A = {1,2,3,...N}이고 B = {N,N-1,...,1}이면 가능할 것이라고 직관적으로 생각할 수 있고 실제로도 그렇다. 엄밀하게 하고 싶으면 exchange argument 같은 걸로 대충 보이면 된다.
그럼 이거 말고도 또 가능한 경우를 생각해보자. 결론부터 말하면 이는 N/2를 경계로 나뉜다. 일단 N이 짝수라고 생각하고 N/2 이하의 수들을 0으로, N/2보다 큰 수들을 1로 생각하자. A = {1,2,3,...N}이고 B = {N,N-1,...,1} 이 매칭에서 0끼리 swap해도, 1끼리 swap해도 답이 바뀌지 않음을 알 수 있다. 따라서 결국 A의 상태를 0과 1로 이루어진 문자열로 생각했을 때 B를 반전시켜서 나타내는 데에 드는 최소 이동 횟수를 구하는 문제이다. 이건 O(NlogN)에 세그로 풀어도 되고 조금만 더 생각해보면 O(N)에도 간단하게 풀 수 있다.
N이 홀수면 중앙값이 0인 경우와 1인 경우 모두 계산해서 작은걸로 하면 된다.
티어는 Gold I.
그냥 시키는 대로 하면 된다. 근데 번역이 좀 애매해서 영어 지문을 보는 것을 추천한다.
티어는 Gold I.
역으로 X에서 행과 열을 swap했을 때 어떤 성질이 있는지 생각해보자.
1. 행과 열에 있는 X의 개수는 swap해도 바뀌지 않으므로 X와 동일하게 2...212...2로 유지되어야 한다.
2. 행 단위/열 단위를 하나의 문자열로 봤을 때, X가 1개 있는 문자열을 제외하고 똑같이 생긴 다른 문자열이 반드시 존재한다.
이 둘만 만족하면 된다. 뭔가 당연한거 같긴 한데 증명은 잘 모르겠다.
티어는 Gold I.
a[i]->b[i]에 가중치 p[i]인 간선으로 생각하면 순열 사이클 여러개가 나오고 사이클마다 문제를 독립적으로 해결하면 된다. 모든 정점의 degree가 1 이상은 되도록 간선을 최소 비용으로 선택하는 문제라고 할 수 있고, 원형 dp를 이용해 해결할 수 있다.
티어는 Platinum I.
저 위에 있는 BOJ 10806 - 공중 도시 에서 압축한 후 트리 파트만 남긴 문제이다. 풀이는 위를 참고.
티어는 Platinum IV.
남학생-여학생 그룹으로 나누고 조건을 만족하는 간선끼리 이어주면 이분 그래프에서의 최대 매칭과 동치가 된다. 일반적인 이분 매칭을 구현하면 된다.
BOJ 14477 - Assembly Required
풀이
티어는 Platinum IV.
dp[i][j] : i까지 합이 j인 경우의 수 라고 정의하자. j가 작은 k개만 남긴다고 생각하면서 dp를 전이해주면 쉽게 풀 수 있다.
BOJ 24659 - Game with Balls and Boxes
풀이
티어는 Platinum III.
i->P[i]를 간선으로 하는 그래프를 생각해보면 순열 사이클이 되고 각 사이클마다 문제를 독립적으로 해결하면 된다. 첫 라운드를 A, 둘째 라운드를 B라 하면 B에서만 열 정점들을 고정했다고 생각했을 때 그 정점 바로 앞의 정점이 A였다면 B에서도 열어야 함을 알 수 있으므로 이를 이용해 dp식을 세우면 된다.
'일기' 카테고리의 다른 글
| 재미있는 문제 (0) | 2025.01.13 |
|---|---|
| 11월 PS (2) (0) | 2024.11.17 |
| 간단한 nypc 후기 (1) | 2024.10.27 |
| 그냥 오렌지 보내줘 (2) | 2024.08.21 |
| 문제를 별해로 푸는 능력 (2) | 2024.07.14 |
