(1)에서 많이 써서 쓸게 별로 없다. BOJ Random Defense 돌린거 풀이 정리할 생각도 해봤는데 양이 너무 많다.. 그것과는 별개로 저거 너무 좋아요 꼭 써봐야함
1. 2024 SW-IT Contest 개인 Virtual
사정이 있어서 원래 3시간 대회인데 2시간만 잡고 풀었다.
A (BOJ 32399. 햄버거 정렬) 0:01
가능한 경우의 수가 3! = 6이므로 6가지 경우에 대해서 머리로 풀면 된다.
B (BOJ 32400. 다트판) 0:04
본문에 주어진대로 구현하면 된다. 실수(real number)는 안 쓸수록 좋으니 60을 곱한 후 비교
C (BOJ 32401. ANA는 회문이야) 0:07
문제를 잘못 읽고 부분 문자열이 아니라 부분 수열인 줄 알았다.
부분 문자열인 원본 문제의 경우, N <= 100이므로 O(N^3)에 A, N, A 위치를 잡아줘도 무방하다.
추가로 부분 수열인 경우도 알아보자면 A 위치를 2개 고정하고 그 사이의 N 개수가 N이 아닌 문자의 개수를 센 후 N을 하나 고르고 나머지 문자열은 2^(개수)만큼 곱하면 된다.
D (BOJ 32402. TPS) 0:17
구현 문제이다. W D S A 순서대로 0~3을 넘버링해주면 +1이 시계방향, -1이 반시계방향이므로 mod 연산을 이용하면 그나마 편하게 구현할 수 있다.
E (BOJ 32403. 전구 주기 맞추기) 0:26, +1
제한이 너무 애매해서 의심스러웠는데 그냥 dp로 풀었다.
F (BOJ 32404. 일이 커졌어) 0:36
확신이 안들어서 O(N!) 코드로 규칙 찾았다. 홀수는 오름차순, 짝수는 내림차순으로 놓되 홀수는 N/2+1~N, 짝수는 1~N/2로 구성하면 된다.
G (BOJ 32405. 배틀 로얄) 0:45, +1
한명씩 지워주는데 이미 지워진 사람은 빠르게 넘기기 위해 union-find를 썼다. 근데 누적 공격이 100만 넘으면 볼필요가 없어서 더 쉽게 풀 수 있다고 한다.
H (BOJ 32406. 의좋은 형제) 0:57
한쪽 관점에서 자신을 최대화하거나, 최소화하고 싶다고 생각할 수 있다. 같은 열에 있으면 동시에 다른 행으로 옮겨가는 연산이므로 a[i] -= b[i], b[i] := 0으로 바꿔주고 a[i]의 양수/음수 여부에 따라 최대화하고 싶으면 음수를 다 상대쪽으로, 최소화하고 싶으면 양수를 다 옮겨줄 수 있다. 단 연산의 특성상 a[n-2]는 반드시 b로, a[n-1]은 반드시 a로 간다.
I (BOJ 32407. 식물 기르기) 1:06
원래 거의 자명해보이는 pq + 파라메트릭 풀이가 먼저 떠올랐는데 2^k만 주는 이유가 있지 않을까 생각되어 좀 더 쉬운 풀이를 생각해봤다. 2^0에게 물을 다 주고나면 문제 크기를 정확히 절반으로 줄이고(=x를 정확히 2배 늘리고) 2^1을 2^0으로 취급할 수 있다. 이렇게 재귀적으로 x가 가능한지 O(16)에 판별할 수 있고 O(N+16logN)에 문제를 풀 수 있다.
J (BOJ 32408. 대전 도시철도 2호선) 1:13
1 - N path 위의 정점을 쭉 지우고 나머지 컴포넌트 크기를 구하면 끝난다.
K (BOJ 32409. 멜로디) 1:28
보자마자 이 문제와 거의 똑같다는 느낌이 왔다. 실제로 내 풀이도 거의 똑같다. 최소 음은 연결되는게 윗음밖에 없어서 최소 음 기준으로 보는게 편하다. 1번 음을 다 쓰려면 2번 음이 그 개수만큼 커버를 해줘야 한다. 그게 안되면 -1이고 커버가 되면 2번 음 -= 1번 음 하고 계속 반복해주면 된다.
L (BOJ 32410. 용감한 용사 수호) 1:40
쉽지 않아보이는데, p, q <= 300이라서 공격력/체력이 300 넘으면 볼 필요가 없다. 이걸 고려해서 dp table을 짜보자.
dp[i][j][k] := i번 장비까지 j개를 골랐고 그래서 공격력이 k만큼 올랐을 때, 체력은 최대 얼마나 오를 수 있는가?
이렇게 하면 O(300NM)에 table을 채우고 2D prefix sum으로 최종 dp값에 대해 커버하는 점의 개수를 셀 수 있다.
지문이 변경된 게 아쉽다. 원래 지문이 궁금하면 이 글을 읽자
M (BOJ 32411. 계단 수열과 쿼리) upsolved, +6
시간이 20분밖에 안 남아서 10분 만에 짜서 냈는데 틀렸다. 풀이는 맞았는데 구조체를 잘못 짜서 그랬다.
지문이 무서울 때는 제한을 보자. 1 <= k <= 10이다. 각 k마다 세그를 만들어서 구간의 최대 계단 수열 길이를 관리하게 하자. 이걸 위해서는 노드에 다음과 같은 정보들을 저장하면 된다.
pre(이 구간의 가장 왼쪽 값을 포함하는 가장 긴 계단 수열의 길이)
suf(이 구간의 가장 오른쪽 값을 포함하는 가장 긴 계단 수열의 길이)
mx(이 구간의 가장 긴 계단 수열의 길이)
st(이 구간의 가장 왼쪽 값)
ed(이 구간의 가장 오른쪽 값)
siz(이 구간의 길이)
이렇게 값을 지정하고, 노드 2개를 합칠 때는 정의에 따라 합쳐주는데, 이 때 |왼쪽 노드.st - 오른쪽.ed| = k일때만 경계를 넘을 수 있도록 해주면 된다.
N (BOJ 32412. 카드 뒤집기 1) upsolved, +2
i번째 카드를 기준으로 i 뒤가 뒤집혔는지 여부는 영향을 주지 않으므로, 앞을 기준으로 어떻게 변화하는지 관찰하자.
중간에 안 뒤집히고 0이 되고 해서 좀 까다롭다. 이걸 없애기 위해서 잘 생각해보면, i 앞에서 "결과가 0보다 크고 A[i]보다 작은 가장 오른쪽 위치"를 찾고 j라고 하자. 이제 j를 지나게 되면 i는 반드시 A[i](앞면)이다. 그 전에 앞면이었다면 변화가 없고, 그 전에 뒷면(0)이었다면 0보다 큰 수였기 때문에 뒤집히기 때문이다. 또한 j+1~i-1 사이에는 결과가 0 또는 A[i]보다 큰 수밖에 없게 되는데, 여기서 0는 상태에 영향을 주지 못하므로 결국 A[i]보다 큰 수의 개수만큼 상태가 뒤집힌다. 따라서 이 개수를 세주면 되고 이건 prefix sum을 관리하면서 0이 아닌 수 개수를 세주면 된다.
O (BOJ 32413. 카드 뒤집기 2) upsolved, +1
카드 뒤집기 1을 위 풀이로 풀었다면 카드 뒤집기 2로 확장하는 것은 어렵지 않다. 뒷면이 0이 아니라 B[i]가 되었을 뿐이므로, B[i] <= A[i]라 하면 B[i]+1~A[i] 사이에 있는 가장 오른쪽 위치를 j라고 하면 같은 논리로 풀 수 있다. 대신 여기서는 "어떤 구간에서 k보다 큰 수"를 직접 구해줘야 하므로 pst 등을 이용해야 한다. B[i] > A[i]도 약간 처리만 해주면 된다.
2. 이것저것 풀이
같은 수에 연산은 최대 m번까지만 하면 된다. 그리고 i번 인덱스에 연산을 x번 했을 때 최솟값을 f(i,x)라 하면 자명하게 f(i,x)는 단조감소하며, convex하다(즉, 감소량이 점점 작아진다). convex하기 때문에 그냥 감소량 큰 연산 k번 해주는 그리디가 먹힌다.
여유 시간은 연속적으로 잡는 것이 좋다. 숙제에 순서를 배정했다면, t 이전에 할 숙제와 이후에 할(해도 되는) 숙제를 나눌 수 있다. 이전에 할 숙제는 앞에 몽땅 하고 남은 시간 동안 에피소드를 최대한 보면 된다. 숙제 순서는 그냥 d 기준으로 정렬하고, t 이후에 해도 되는 숙제는 다 옮기면 되니까 반드시 t 이전에 해야 할 숙제를 빨리 찾아야 하고 이건 전처리해주면 된다. 이러면 쿼리는 이분탐색으로 O(logN)에 된다.
결국 관리해야 하는 연속적인 구간이 3개 이하이다. 그냥 naive하게 늘려주면 된다.
CF 2048E. Kevin And Bipartite Graph
정점은 2n+m개이고 간선은 총 2nm개이며, n개 색 각각에 대해 그 색깔의 간선만 남겼을 때 사이클이 없으면 된다.
n개 색 각각에 대해 간선을 고르게 배정하면 2m개이다. 사이클이 없어야 하므로 최대 트리이며, 이때 2m < 2n+m이므로 m < 2n이어야 한다. 이제 m = 2n-1로 가정하고 문제를 풀어보자. 각 그룹의 정점이 2n, 2n-1개이다. 각 그룹을 A, B라고 하면 A1-B1-A2-B2-...-B(2n-1)-A(2n) 꼴의 매칭을 고려할 수 있다. 이제 A 그룹의 i번 정점을 (i+2) mod 2n번으로 다시 넘버링해준 후 다음 색깔에서 똑같이 매칭하는 과정을 n번 반복하면 된다.
N!=1이면 적당히 N으로 나눠서 N=1로 바꿀 수 있다. 이제 2D+2 이상의 층을 갈 수 없다는 사실을 관찰하자.(2D+2의 가장 큰 진약수가 D+1이고 차이가 D 초과) 그러면 답은 2D+1 또는 2D이다. (1~D+1은 갈 수 있으며, 2D는 1->D->2D로 가면 됨) 2D+1이 되는지는 소인수분해하면서 판별할 수 있다. 만약 2D+1이 n에 bound된다면 답은 n 또는 n-1이기 때문에 똑같이 해줄 수 있다.
자명?하게도 연산은 2번 이하로 해야 한다. 연산이 겹치는 경우와 겹치지 않는 경우를 나눠서 최적으로 해주면 된다.
행과 열에 대한 visited를 비트마스킹으로 관리한다고 생각하면 O(2^(2n)*n^2) dp를 짤 수 있다. 보통 비트마스킹 dp는 시복에 비해 상수가 빨라서 믿음을 가지고 내면 된다.
정점을 하나 지워서 사이클이 없는지 보면 된다. 이건 결국 각 정점 v에 대해서,
(1) v 자식 서브트리 중 내부에서 끝나는 back edge가 없고,
(2) v 위에서 내부에서 끝나는 back edge가 없고,
(3) v를 포함하지 않으면서 v를 지나는 back edge 경로가 1개 이하
이면 된다.
(1), (2)는 dfs하면서 전처리 가능하다.
(3)은 back edge 리스트를 정렬되게 관리하면서 이분 탐색 + 오일러 투어로 어떻게 하면 된다.
아무래도 더 쉬운 풀이가 있는 것으로 보인다.
이 아래는 solved.ac 마라톤이다.
JOI cyclic shift
이왜골5
제한을 보면 별 생각이 다 든다. 처음엔 2번 이하로 옮겨서 되는줄 알고 하나 짰다가 틀렸다.
지금까지 1에서 도달 가능한 집합을 관리하면서, 이 집합을 채워주면 되는데 이걸 naive하게 봐주면 TLE이므로 unvisited 집합을 set 등으로 관리해주면 된다. 되게 간단한데 생각하기 어려웠다.
문제는 어렵게 써놨지만 결국 20억 범위에서 Y에 대한 prefix sum을 구하면 된다. 이건 prefix sum을 그냥 map으로 관리한다고 생각하면 다를 게 없다.
일단 전체가 m의 배수여야 하므로 처음에 분할 가능한 지점은 prefix만 봤을 때 mod m = 0인 지점이다. 근데 분할을 하든 안하든 분할 가능한 지점을 지나면 mod m = 0이 되므로 처음에 분할 가능한 지점이 그 이후에도 분할 가능한 유일한 지점이다. 이러한 지점이 k개라면 답은 2^k mod 10^9+7.
Function sol(n):
if n == 0: return
sol(n - 1)
print n
sol(n - 1)이런 문제를 Gray Code라고 한다고 한다.
문제는 최단경로지만 어차피 최단거리는 |x[i]-y[i]| 합이다. 이제 각 자릿수를 높이고 내리는 것을 연산으로 취급하면, 그에 따라 우선순위를 매길 수 있다. 그 우선순위는 다음과 같다.
1. 자릿수를 낮추는 연산이 우선
1-1. 뒷자리를 낮추는 연산이 우선
2. 앞자리를 높이는 연산이 우선
이렇게 하고 우선순위에 따라 연산에 번호를 매기면 x->y까지 가는 상황을 일종의 sequence로 나타낼 수 있다. 이 중 사전순 k번째를 찾아서 추적해주면 된다. 다항 계수를 계산해야 하는데, 이걸 dp로 하는법을 몰라서 int128 때리고 36!/(9!)^4이 int128 안에 들어오길래 적당히 오버플로 안나도록 나눠줬다.
i번째 문자가 뭔지 알수 있다면 그걸 20번만 구하면 된다.
f(x)를 x번 수까지 끝날때 총 문자열의 길이로 정의하자. i에 대충 맞도록 x를 이분탐색을 돌려주면 문제를 풀 수 있을 것 같다. 따라서 f(x)만 구해주면 된다.
f(x)는 결국 [1..x] 범위에서
(1) 3,5 배수를 제외한 각 숫자의 자릿수 합
(2) 3의 배수 개수 / 5의 배수 개수 / 15의 배수 개수
를 빠르게 구할 수 있으면 된다. (1)은 자릿수별로 맞춰주면서 구할 수 있고 (2)는 쉽다.
순서 관계만 만족하면 되니까 순서대로 간선 이어주는게 최소로 만족시키는 방법이다.
이제 이상태로 파라메트릭 서치를 하자. i번 조건까지 남겼을 때 모순이 없는가? 를 확인하면 되고 이건 사이클 판별을 해주면 된다.
그렇게 최대 i를 구하면 그 그래프에서 사전순 최소 위상 정렬을 해주면 되고, 이건 pq로 풀 수 있음이 잘 알려져 있다.
이 아래는 SciOI A~E이다. A는 대회 때 풀었고 설날 때 어쩌다가 C를 풀어버려서 A~E를 다 풀었다.
i번 앞까지 소등된 방의 개수 범위를 구하면 된다.
a를 고정하고 같은 a값에 대한 b를 다 지운 뒤 multiset 등으로 찾으면 된다.
b(선택한 P합) - a(선택한 C합) >= aC-bP이다. 쿼리로는 우변만 주어지는 것과 같으므로 좌변을 미리 최적화하자.
dp[i][j] := i까지 P합 = j일 때 C합의 최솟값 으로 정의하면 O(500N^2)에 식을 풀 수 있고 최종 dp값에 대하여 b(P합) - a(C합)을 의미있는 원소만 관리하는 형태로 남기면 쿼리를 이분탐색으로 풀 수 있다.
쿼리에 대한 세그먼트 트리를 관리하면 된다. 일반성을 잃지 않고 행이라고 하면, 이 행이 마지막으로 통째로 바뀐 순간부터 열이 업데이트될 때마다 값을 바꿔준다는 느낌으로 생각하면 그 변경된 값을 구간 쿼리를 날려서 계산할 수 있다.
인접하게 묶어주면 답이 n/2 이하임을 고려할 때, 크게 나누면 무조건 손해라는 사실을 알 수 있다. 여기서의 예외는 나눈 한쪽이 0인 경우뿐이다. 따라서 dp[i] := i부터 나눌 때 최소 비용으로 정의하면, 다음 상태는 그냥 1개씩 곱하고 넘기거나(dp[i+2]), 지금 이 칸을 포함하도록 0을 잘 쪼개주는 형태를 생각할 수 있다. 이걸 쪼갤 때 가능한 다음 state가 구간을 이루므로 이상태로 dp를 lazyprop으로 최적화하면 O(NlogN)에 풀 수 있지만, 더 잘 생각해보면 무조건 매칭되는 인덱스가 작은게 이득이라서, 그러한 인덱스를 전처리해두면 O(N)에도 풀 수 있다.
각 위치 i에 대해서 각 색깔에 대해 i와 가장 가까운 거리의 합을 최소화하면 된다.
거꾸로 색깔을 고정하면, 각 위치가 최소 거리인 인덱스는 구간을 이루며 인접한 다른 색깔과의 중점까지 그 범위를 먹는다. 따라서 절댓값에 따라 거리 식을 계산한다고 생각해주면 구간에 특정 값을 더해주는 연산만 쓰기 때문에 imos(difference array)로 구할 수 있다.
처음 보면 별 생각이 다 들지만, 그림자가 나무에 막히지 않는다고 생각해보면 결국 (나무 길이 합) - (그림자가 커버하는 구간 합집합 길이)이다. 일단 좌표압축을 해주면 합집합 길이는 화성세그로 구할 수 있다. 근데 화성세그는 짤 때마다 항상 버그가 많았어서 min counting 세그로 구해줬다. (0 개수를 세는 것과 같음)
'일기' 카테고리의 다른 글
| 2월 PS (1) (0) | 2025.02.08 |
|---|---|
| 2025 국제정보올림피아드 대표학생 선발고사 1차 후기 (2) | 2025.01.27 |
| 1월 PS (1) (4) | 2025.01.25 |
| solved.ac Ruby V (2) | 2025.01.19 |
| 재미있는 문제 (0) | 2025.01.13 |
