9월의 문제 풀이 - (2)
9/21 ~ 9/30에 푼 문제들입니다.
문제의 풀이에 대한 스포일러가 포함되어 있습니다.
잘못된 풀이가 있다면 지적해주세요.
9/21
Platinum 1
#tree #lca
경로 $a$-$b$와 $c$-$d$가 두 점 이상을 공유하는 지 판별하자. 여러 lca를 구해서 경우를 따져보면 된다.
BOJ 30155 - Crazy Malvika discovers Crazy Fibonacci function
Silver 3
#math
주어진 수열은 첫 6개의 항이 계속 반복되는 형태이다.
9/23
백준에 올라온 ZOAC 대회 문제들을 풀었다. 처음으로 대회 문제 출제진으로 참여했다. 문제 만들기도 어려웠지만, 다른 사람들이 만든 문제를 풀고 검수하는 게 훨씬 힘들었다.
Bronze 4
#string
주어진 문자열 내에 특정 문자열이 존재하는 지 확인한다. substr 함수를 써도 되고, 직접 비교연산을 해도 된다.
Silver 3
#case_work
출제 의도는 case_work로, 여러 가지 경우를 나눠서 각각의 경우에 논리적으로 조건을 만족할 수 있는지 확인하는 것이다. 하지만 검수 과정에서 완전 탐색 풀이가 나왔고, 이게 좀 더 생각하기 쉬운 풀이인 것 같다.
Silver 1
#stack
처음 풀 때는 재귀함수 f, g를 직접 짜서 풀었지만 정해는 스택이다.
Gold 1
#dp #prefix_sum
길이가 N, 평가값이 E인 함수 문자열이 생성되는 경우를 모두 따져보면 된다. 길이가 1이 아니면 무조건 f 또는 g로 시작해야 함을 이용하자.
Gold 4
#implementation
처음에 정보들이 주어진 후에 영업왕의 수가 변하려면 반드시 쿼리에 의해 새로운 사람이 해당 가게에서 매출 1등을 달성하는 경우밖에 없다. 또한, 각 직원별 누적 매출액은 항상 서로 다르므로 각 가게의 매출 1등은 언제나 단 한 명이다. 이 사실을 이용해 적절히 구현만 하면 된다.
Gold 3
#map
1번 쿼리의 $a$와 $b$의 조건의 의미는 각 정점 $i$의 깊이는 절대 $\lfloor \log_{2}{i} \rfloor$보다 깊어질 수 없다는 뜻이다. 따라서 map으로 각 정점의 부모 정점을 관리하고, 2번 쿼리에서의 경로는 naive하게 구해주면 된다.
Platinum 4
#math
$P$를 뒤집어서 생각하면, 2진수가 1씩 증가하는 형태임을 알 수 있다. 그렇기 때문에 대략 60번째 자리 이후부터는 경우가 매우 단순해진다. 60 이전에 대해서는 수학으로 잘 구하면 된다.
Silver 2
#math
가운데에 가장 작은 수($\frac{N}{2} + \frac{M}{2}$)의 최초 직사각형이 존재하고 변을 따라 1씩 증가하며 사각형이 확대되는 형태가 된다. D 미만의 칸의 개수를 세주면 된다.
Gold 1
#prefix_sum #binary_search
인부들의 위치 배열에서 홀수 항, 짝수 항에 대하여 각각 누적 합 배열을 생성한다. 나무의 범위 내에 존재하는 첫 인부가 짝수 번째인지 홀수 번째인지 보고 적절히 식을 세워 값을 구해준다.
Gold 4
#sorting #queue
문제에서 주어진 우선순위에 따라 사람을 한 명씩 뽑아주면 된다. 구현이 어려워서 큐 하나와 우선순위 큐 하나를 써서 풀었다.
Platinum 2
#segtree #lazyprop #binary_search
배열 $X$를 색상 별로 압축해서 $A,B,C$ 세 개의 구간 합 세그먼트 트리를 구성한다. 일반적인 구간 합 세그먼트 트리 + lazy propagation와 비슷하지만 2번 쿼리를 해결하기 위해 배열 $C$가 $C-(A+B)$의 값을 들고 있도록 유지한다. 이렇게 하면 2번 쿼리는 단순히 $C$를 0으로 만드는 쿼리로 해결이 가능하다.
9/24
Silver 2
#implementation
문제에 써있는 그대로 구현하면 된다.
Silver 2
#ad_hoc
$K$가 1 이상일 때 모든 칸을 방문할 수 있으려면, 한 번씩 방문했을 때 다시 출발점으로 돌아올 수 있어야 한다.
Gold 4
#parametric_search #binary_search
휴게소가 없는 구간의 최댓값을 G라고 하자. 배열을 돌며 M개의 휴게소만으로 G가 가능한 경우인지 판별하고 이분 탐색으로 G의 최솟값을 구하면 된다.
9/25
Gold 3
#math #prefix_sum
쿼리 $l, r$에 대해 직접 식을 써보면 매우 아름답게 정리가 된다. 일반 누적 합과 제곱의 누적 합을 구해 해결하자.
Gold 1
#greedy #backtracking
머리로 생각했을 땐 쉽게 답이 나오지만 코드로 옮겨 적는 것이 매우 힘들었다. 각 단어가 처음 나오게 되는 수열을 $A$라 하면, $A$의 합이 $N$이 되는 것 중 사전 순으로 가장 뒤에 오는 것을 택하면 된다.
Gold 3
#greedy #sorting
아파트 정보를 정렬하여 학교 기준으로 가장 먼 곳에 있는 학생부터 차례대로 만석을 만들어 태우면 된다.
Gold 1
#math #greedy #case_work
두 연산 중 하나를 선택할 때, 값이 더 커지는 연산을 선택하면 된다. 어떠한 경우라도 $K$값이 $3 \times 10^{15}+7$를 초과하게 되면 쿼리에 의해 곱하기 0이 수행되지 않는 이상 절대 $10^{9}+7$아래로 내려가지 않는다는 사실을 이용하자. 더하기와 곱하기가 주어졌을 때 우선순위를 판별하기 쉬워진다. overflow에 주의하며 구현하자.
BOJ 11449 - Icelandic Motorclubs
Gold 3
#prefix_sum
$g-d$의 합이 0 이상이면 항상 가능하다. 시작점은 누적 합이 0미만이 되는 가장 마지막 장소이다. 그런 곳이 없다면 어디에서 시작해도 상관 없다.
Gold 2
#disjoint_set
$V[i]$를 $i$의 원수들의 집합이라고 하자. $V[i]$에 속한 원소들끼리 모두 친구로 만들어주면 된다. 팀은 분리 집합으로 구현하자.
9/26
Silver 3
#majority_vote
처음에 map으로 풀었는데 Boyer-Moore majority vote에 대한 문제라고 해서 공부한 뒤 다시 풀어봤다.
Gold 4
#dp #graph
$dp[i][j]$를 $i$번 도시까지 $j$개의 도시를 거쳐 이동하는 경로들의 최대 비용이라고 정의하고 문제를 풀면 된다.
Silver 1
#tree
첫 번째 주어지는 점은 무조건 루트가 된다. 그 이후에는, $i$가 주어지면 $i$의 부모가 있는지 확인하고 없으면 직전의 값이 부모가 된다.
Gold 4
#math
$x$에 대한 식을 배열로 계수를 저장해서 관리하면 편하게 구현할 수 있다.
Bronze 1
#implementation
직접 세주면 된다.
9/28
Gold 4
#segtree
정해가 뭔지 도저히 모르겠다. 어쩔세그를 써서 풀긴 했지만 찝찝하다.
9/29
Gold 4