11월 2주차에 푼 문제들 풀이이다.
Zero One Algorithm Contest 2024
티어는 Bronze IV.
시키는대로 하면 된다.
티어는 Silver I.
잘 생각해보면 조건을 만족하는 수는 소수와 1이므로 구간 내의 소수 개수를 빠르게 셀 수 있으면 되고, sieve + prefix sum으로 해
결 가능하다.
티어는 Gold III.
간단한 게임 이론 dp 문제이다. 자식들 중 후공이 반드시 패배하는 상태가 있을 경우 선공이 승리하고, 그렇지 않으면 후공이 승리한다.
티어는 Gold I.
각 회원의 가장 왼쪽 응모권의 위치를 관리한다고 생각하면, 어떤 회원이 당첨되었을 때 그 뒤에 있는 응모권들의 인덱스가 당첨된 회원의 응모권 수만큼 줄어든다. 결국 다음과 같은 2가지 연산을 빠르게 지원하는 자료구조가 필요하다.
1. [a,b]에 x를 더한다
2. x번째 인덱스의 값을 구한다
이는 세그먼트 트리로 가능함이 잘 알려져 있다.
티어는 Gold I.
dist[x][y][tel] := (x,y)에서 텔레포트를 tel번 사용했을 때 최소 힘 으로 정의하고 다익스트라로 전처리 후 쿼리를 처리하면 된다.
티어는 Platinum IV.
A~B 사이의 소수를 모두 구해놓자.
dp[i][j] := i번째 소수까지 잘 사용해서 합이 j인 경우의 수로 정의하고 map에 저장하면서 dp를 돌리면 그냥 AC가 나온다. 왜냐하면 (가능한 j의 최댓값) - (가능한 j의 최솟값)이 크지 않기 때문이다.
티어는 Gold I.
dp[i][j][k] := (1,1) -> (i,j)에서 가져올 수 있는 문자 k의 최대 개수
dp2[i][j][k] := (i,j) -> (n,m)에서 가져올 수 있는 문자 k의 최대 개수
각 문자 k에 대하여 위치 (i,j)를 고정하고 (1,1) -> (i,j)까지 간 후 텔레포트를 시도한다고 하면 답은 dp[i][j] + max(dp2[x][y])가 된다. ((x,y)는 (i,j)까지 간 상태에서 텔레포트 가능한 모든 위치 중 하나) 어떤 행/열의 최대 dp2 값을 잘 관리해주면 O(4NM)에 풀 수 있다.
티어는 Silver III.
일단 정해는 브포 섞은 정수론인데 여기서는 O(sqrt(b/a)) 풀이를 소개한다.
자명하게 a|b이어야 하고 모두 a의 배수여야 하니 a를 나눴다고 생각하자. (그래놓고 마지막에 a를 곱하면 됨) 그럼 b/a의 약수가 d_i의 후보가 된다. 또한 d_i의 후보는 b/a의 약수 뿐이다. 따라서 약수를 k-1개 배치하고 마지막에 b/a를 배치하면 lcm이 b/a가 된다. (약수 개수) < k인 경우가 불가능한 경우이다.
티어는 Platinum I.
헷갈리면 안되는 것이 동시에 감염시키는게 불가능하다. 무조건 하나씩 처리해야 한다.
일단 0번 정점을 만들어서 0에서 i로 가중치 a[i]의 간선이 있다고 생각할 수 있다. 그럼 이 문제는 MST를 잘 만드는데, 여기서 0번 정점의 degree <= K라는 조건이 붙은 문제가 된다.
일단 MST를 어떻게든 만든 다음에, 0번 정점의 degree가 K보다 크면 그리디하게 1개를 제거한 다음, 최대한 비용이 적게 들도록 끊어진 컴포넌트를 다른 아무 컴포넌트와 연결시키는 방식으로 풀 수 있다. 구현이 좀 까다롭다.
p.s.)귀납적으로 보면 당연히 될 것 같은데 엄밀한 증명은 잘 모르겠다.
티어는 Bronze II.
기본적으로는 1번인데, 시작과 끝이 x축 또는 y축에 평행한 경우에 0번 또는 2번이다. 사이에 껴있는지 잘 보면 된다.
BOJ 24084 - 次の文字 (Next Character)
티어는 Bronze IV.
시키는 대로 하면 된다.
BOJ 20979 - 往復すごろく (Round Sugoroku)
티어는 Gold IV.
시작 지점 왼쪽에 있는 #와 오른쪽에 있는 #를 가까운 순서대로 넣고 거리를 잘 계산해주자. 디테일한 구현이 좀 까다로울 수 있다.
티어는 Platinum V.
N<=13과 주어지는 문자열의 길이가 모두 같다는 점에 주목하자. 가능한 모든 문자열의 개수가 3^13 정도로 적다. 쿼리로 주어진 문자열을 싹 다 받은 다음 정렬하고 multisource bfs로 최소 operation 횟수를 구하면 된다.
BOJ 20981 - イベント巡り (Event Hopping)
티어는 Platinum III.
dp[i][j] := S[i]+1번 시각에 j번 마을에 있을 때 최대 방문 횟수로 정의하면 단조성을 이용해 O(NlogN)에 정렬하고 O(N)에 dp값을 계산할 수 있다.
BOJ 20982 - 安全点検 (Safety Inspection)
티어는 Platinum III.
어떤 목수가 갈 가장 오른쪽 위치를 고정하면 그 목수가 할 일이 자명해진다. 파라메트릭 서치로 x 안에 가능한지를 따진다고 하면 뒤에서부터 그 일을 x 안에 처리하기 위해 배치하기 위한 최소한의 목수를 정할 수 있고 남는 목수들을 앞으로 땡기면서 필요한 목수의 수가 k명 이하인지를 판별해줄 수 있다.
티어는 Gold V.
max(R개수,S개수,P개수) >= N/3임에 주목하자. 3번의 쿼리로 가장 많이 등장하는 문자가 무엇인지 찾고, 남은 두 문자를 쿼리를 날리면서 적절히 찾아주면 3 + N - N/3 <= 403번 이하의 쿼리로 문제를 해결할 수 있다.
티어는 Platinum I.
mcmf로 증명할 수 있는 그리디 문제라고 한다. 근데 그런건 잘 모르겠고 내가 푼 방법을 서술하겠다.
일단 당연히 텔레포트는 쓰는게 이득이니까 무조건 써야 한다. 그런데 텔레포트를 어떻게 써야 할까? 텔레포트를 사용하지 않고 s, l만 가지고 n개의 통로의 비용을 구했다고 하자. 그럼 그 비용을 오름차순 정렬하고 뒤에 T개를 다 0으로 만드는 것이 자명하게 최적일 것이다. 앞에 n-T개를 A그룹, 뒤에 T개를 B그룹이라고 하자. 그럼 우리의 목적은 sum(A)를 최소화하는 것이 된다. 이제 우리가 . 할 수 있는 행동은 둘 중 하나이다.
1. A 그룹에서 하나를 s->l로 변경
2. B 그룹에서 하나를 s->l로 변경
자명하게 1번 연산은 s-l이 가장 큰 것을 선택해야 한다. 2번 연산의 경우 만약 저 연산을 했는데 그대로 B그룹에 속하게 된다면 의미가 없기 때문에 2번 연산은 min(l) < max(A)일 때만 의미가 있으며 이때 A-l만큼의 이득을 본다는 사실을 알 수 있다. 두 전략 중 더 이득이 되는 행동을 취하면 된다. 둘 다 얻을 이익이 없으면 그냥 그만두면 된다.
티어는 Gold I.
bitwise OR의 성질을 잘 생각해보자. 예를 들어 i번 인덱스에 001100을 OR시켰다고 할때, 0인 위치의 경우 정확하게 다 알 수 있다. 가령 i번 인덱스의 값이 100100이었다면, 10**00까지 확실해지는 것이다. 그럼 다음에 i번 인덱스에 OR시켜야 하는 값은 **00** 형태일 것이다. 잘 생각해보면 이러한 형태가 반드시 겹치지 않게 배치 가능하다는 사실을 알 수 있다.
티어는 Platinum III.
1:1 내분점 -> 2:1 내분점 -> ... 하면서 쭉 구하면 된다. 내분점을 구할때는 이분탐색을 충분히 많이 반복해서 근사시키면 된다.
티어는 Platinum III.
그냥 무작정 작은거부터 때려박으면 조건을 만족하지 않는다. 3,5와 서로소인 수를 고려할 때 규칙을 찾다 보면 i->i*15, i*27, i*125로 나아가면 됨을 알 수 있다.
티어는 Silver IV.
같은 수가 한번이라도 나오면 true이다. 세 변의 길이가 모두 달라서 같은 변끼리 붙였을 때 삼각형이면 뒤집어서 붙이면 반드시 사각형이 된다.
티어는 Silver I.
문자열에 관계없이 답은 26*(n+1) - n이다. 간단한 경우의 수 문제이다.
티어는 Platinum III.
관찰해야 하는 사실은 min*2 > max이면 가장 작은 나무의 인덱스가 주기 n으로 계속 돈다는 것이다. 결국 min*2 <= max인 동안만 시뮬레이션을 해주면 되고 이건 세그로 열심히 해주면 된다. 구현이 매우 귀찮다.
티어는 Gold II.
인접한 수가 4개씩이니까 큰 수부터 5k-4개만 남기고 nCr 순회하면 된다. 알면 쉬운데 아니면 궁지에 몰리기 쉽다.
티어는 Gold V.
다음과 같은 2가지 사실을 관찰해야 한다.
1. 좌표 합의 parity가 유지된다. (+,-)1 (+,-)2 (+,-)3이라서 자명하다.
2. (0,0,0) -> (0,0,2)가 가능하다. 손으로 해봐도 되고 bfs 돌려도 된다.
따라서 좌표 합이 짝수인 모든 칸이 이동 가능하다.
티어는 Platinum III.
특정 알파벳만 남긴 bitset을 고려하자. bitset을 (사이 수) + 1만큼 shift시키고 bitwise and 시 1의 개수를 세면 된다.
티어는 Gold V.
그냥 구현이다. 느린 자동차는 방해를 받지 않는다는 사실을 이용하면 구현이 그나마 편하다.
티어는 Platinum I.
파라메트릭 서치로 임계값 x가 가능한지를 따진다고 하자. x 이하의 임계값을 가지면 간선으로 이어준 뒤 최대 매칭 = n인지 확인하면 된다. 이분 그래프이므로 이분 매칭을 쓰면 되는데, n이 크니 hopcroft-karp를 이용하자.
티어는 Platinum I.
한 색깔의 정점과 동전의 매칭이라고 생각해도 무방하다. 검정색 동전과 검정색 정점을 매칭시킨다고 하자. 동전과 각 정점 사이의 거리를 비용으로 간선을 이어주면 MCMF가 된다.
티어는 Diamond IV.
일단 (1,1)과 k개의 집, (n,m)만 남긴 방향 그래프를 고려하자. 이제 각 정점에서 할 수 있는 행동에 주목하자. 어떻게든 어떤 정점에 왔다고 치면 거기서 할 수 있는 행동은 갈 수 있는 다른 정점으로 가는 것이다. 그런데 만약 그 정점이 이미 골라졌다고 하면 굳이 손해를 보면서 그 정점으로 가려고 시도할 필요가 없다. (물론 가다가 더 지날수도 있지만, 그건 "우연히" 방문한 것이므로 무시한다. "의도적으로" 방문한 횟수는 1번이면 된다.) 결국 각 정점에서 갈 다음 정점을 겹치지 않게 잘 고르는 것으로 해석할 수 있다. ((n,m)이 겹치는 건 제외) 그럼 다음과 같은 그래프를 생각할 수 있다.
가중치는 간선의 비용을 나타낸 것이다. 이제 여기서 MCMF를 돌릴 것이다. (capacity는 모두 1) 그런데 이 그래프는 사실 완벽하지 않다. 이 그래프의 의미를 생각해보면, 어떻게 한 정점까지 왔을 때, 그 정점이 "의도적으로" 다음에 갈 수 있는 정점들을 나타낸 그래프이다. 그런데 이 경우 문제가 생긴다. 바로 (1,1)에서 어떤 정점으로 갔을 때의 비용을 계산할 수 없기 때문이다. 이를 보완하기 위해서는 거꾸로 "모든 정점이 (1,1)에서 이미 도달한 상태"라고 가정하고 (1,1)에서 다른 모든 집까지의 거리를 더해놓고, 그렇지 않은 경우에 (1,1)에서 그 정점까지 가는 거리를 빼주면 된다. 즉 완벽한 그래프는 아래와 같다.
플로우가 어떤 정점 x'에 도달했다는 것은 x번 정점은 (1,1)에서 오는 것이 아닌, 다른 정점에서 거쳐서 온다는 뜻이 되기 때문에 (1,1)에서 x까지 갈 때 드는 비용을 빼주는 것이다. 이제 여기서 MCMF를 돌리면 정답을 구할 수 있다.
'일기' 카테고리의 다른 글
| solved.ac Ruby V (2) | 2025.01.19 |
|---|---|
| 재미있는 문제 (0) | 2025.01.13 |
| 11월 PS (1) (0) | 2024.11.09 |
| 간단한 nypc 후기 (1) | 2024.10.27 |
| 그냥 오렌지 보내줘 (2) | 2024.08.21 |
