PS 일지 (7)

마지막 수정 시각: 2023-04-29 19:21:23

BOJ 10922

일단 업데이트 쿼리가 없다고 생각하고 풀어보자. 어떤 연도 \(i\)에 말을 팔지 않으면, 그 말은 \(j\)번 해(\(i \lt j\))에 \(x_{i+1} \cdot x_{i+2} \cdot \dots \cdot x_{j}\) 마리로 불어난다. 이 때 팔면 여기에 \(y_j\) 만큼을 곱한 돈을 받게 된다. 즉, \(i \lt j\) 인 모든 해 중에서 이 값이 가장 큰 것과 \(y_j\) 중 더 큰 값이 해당 시점에서 말 한마리의 가격이라고 생각해도 상관이 없다. 따라서 말을 여러번 나눠서 팔 필요는 없다.

그렇다면 주어진 문제를 어떤 \(i\)에 대해 \(x_1 \cdot x_2 \cdot \dots \cdot x_i \cdot y_i\) 중 가장 큰 값을 찾는 문제로 바꿔 생각할 수 있다. 업데이트 쿼리가 없다면 이 과정은 \(O(N)\)에 수행 가능하다. 여기서 수의 크기가 아주 커질 수 있다는 문제가 있다. 최댓값을 \(10^9+7\)로 나눠야하기 때문에 정확한 대소 비교가 필요한데, 이 과정은 다음과 같이 처리하면 큰 수 구현이 없어도 64비트 정수로 처리가 가능하다.

기존에 최댓값인 위치 \(i\)를 구해둔다.
\(i \lt j\)인 어떤 \(j\)번 위치와 비교할 때, \(x_1 \cdot \dots \cdot x_i\) 까지는 일치하기 때문에 이 부분을 곱해서 계산할 필요가 없다. 즉, \(y_i\)와 \(x_{i+1} \cdot \dots \cdot x_{j} \cdot y_j\) 중 무엇이 더 큰지만 비교하면 된다. 이 과정을 반복하면 64비트 정수만으로도 구현할 수 있다.

이제 쿼리를 통해 \(x, y\) 배열에 갱신이 일어날 때 어떤 식으로 이 과정을 빨리 수행할 수 있는지 생각해보자.

일단, 기존에 \(x\) 배열에서 값이 1인 위치는 그다지 중요하지 않다(곱한 값을 유지하기 때문), 또 값이 2 이상인 위치는 최대 맨 끝 30개 위치만 고려해주어도 충분하다. \(2^{30} \gt 10^9\) 이므로, 이 경우 맨 끝 30개 보다 더 앞에 있는 위치가 최댓값이 될 수는 없기 때문이다. 정확히는, 맨 끝에서부터 \(X\)를 곱한 값이 \(10^9\)를 넘는 시점까지만 봐주어도 충분하다.

이제, 이렇게 관리하는 마지막 위치들에 대해서는 뒤의 모든 \(x\)값을 곱한것을 해당 위치의 \(x\) 값처럼 생각해보자. 여기에 다음 \(x\)값 사이의 구간에 대해서 \(y\)의 최대를 구해서 곱해준 것이 해당 위치에서의 \(x\)에 대응되는 최댓값이 된다.

\(y\)배열의 경우 세그먼트 트리를 이용하면 쉽게 최댓값을 관리할 수 있고, \(x\)값의 경우 값이 2보다 큰 제일 끝 30개 위치만 들고 가주면 매 쿼리당 \(O(logN)\) 시간이면 충분해진다. 즉, \(O(NlogN + MlogN)\) 시간에 문제를 해결할 수 있다.

BOJ 20079

바로 해결하기 어려워보이니 서브태스크부터 고민해보자.

서브태스크 1의 경우, v가 최대 2종류만 주어진다. 이 경우, 이분탐색을 통해 문제를 해결할 수 있다. 임의의 지점 \(x\)를 찍었을 때 쿼리는 좌,우에서 \(v=1\)인 경우의 개수를 반환하므로, 이게 있는 위치를 좁혀나가면 최대 \(O(logN)\) 번의 쿼리만으로 답을 찾을 수 있다.

이제 서브태스크 2를 생각해보자.

일단, 문제의 조건으로 인해 \(1 + 2 + 5 + 26 + 677 + 458330 \ge 200000\) 이므로, 가능한 \(v\) 값 경우의 수가 많아야 5가지라는 점은 알 수 있다. 그리고, \(1\)부터 \(v-1\)까지의 개수를 다 합친 것이 \(v\)의 개수보다 적다는 것도 알 수 있다. 즉 대부분의 쿼리는 \(v\)가 가장 큰 것이 나오게 된다. 또, 쿼리했을 때 나오는 값으로부터 해당 위치의 값이 무엇인지는 바로 파악할 수 있음도 알 수 있다.

좀 더 정확히 바운드를 생각해보면, \(N=200000\)일 때, 총 6개의 \(v\)값이 있고 이중에서 두번째로 큰 것의 개수가 \(500\)개만 되어도 제곱을 하면 \(200000\)을 넘으므로, 두번째로 큰 것까지 개수를 다 합친게 많아야 \(1000\)개를 넘지 않는다는 것을 알 수 있다. 이러한 위치를 전부 다 방문해보아도 쿼리 개수는 \(1000\)회 정도밖에 되지 않으니 이걸 다 확인해보는게 좋을 것 같다.

여기서 서브태스크 1에서의 접근과 유사하게 이분탐색을 해보자. 가장 왼쪽에 있는 \(x \lt v\) 인 모든 \(x\)가 있는 위치들을 다 방문해볼 것이다.

먼저 정 중앙 위치에 쿼리를 찍는다. 여기서 값이 \(v\)인 위치가 찍히지 않았다면, \(v\)인 위치가 나올 때까지 한칸씩 옮기면서 모두 쿼리해준다. \(v\)가 아닌 위치들은 찍을 때마다 따로 저장해준다.
\(v\)인 위치를 찍었을 때, 그 위치의 왼쪽에 \(x \lt v\)인 애들이 몇 개가 있는지를 확인할 수 있다. 이 값이 내가 왼쪽에서 체크한 \(v\) 가 아닌 위치의 개수와 동일하다면, 더 이상 왼쪽은 볼 필요가 없다. 왼쪽 구간을 전부 버리고 오른쪽 구간을 확인한다.
그렇지 않다면, 왼쪽 구간에 대해 다시 위의 과정을 동일하게 반복하면서 기록해준다. 이를 반복하면 모든 \(v\)가 아닌 위치를 방문할 수 있다.

하지만 실제로 이 내용을 그대로 구현해보면 쿼리 횟수가 10000번을 살짝 넘는 정도가 나와서 틀린다.

여기서, 사실 0을 발견하는 순간 끝을 내면 되고 모든 구간을 한 번에 볼 필요가 없으므로, 전체 구간을 적당히 4~500개 크기로 잘라서 셔플한 다음 버킷 내부에서만 이분탐색을 하면서 0을 발견하면 종료하게 만들 경우 시간복잡도는 같지만 종료 타이밍을 빨리 앞당길 수 있어서 조금 최적화할 수 있다. 이 방식을 적용할 경우 대충 ~7000번 정도의 쿼리 내로 처리되어 90점을 받는다.

(100점은 고민중)

Prompt412 Round 192

오랜만에 8개 다 풀었다. 중간에 이상한 코딩 미스 너무 많이하고 문제를 잘못 읽고 하면서 꽤 헤맸는데 어쨌든 전체적으로 빨리 풀었고 마지막 문제까지 다 풀어서 기분이 좋았다.

A. BOJ 27160

map 등을 이용해서 정확히 개수가 5개가 되는 문자열이 있는지 판별해주면 된다.

B. BOJ 25426

결국 \(a\) 값이 제일 큰 것에 \(x\)가 제일 큰걸 매핑해주는게 이득이므로, 정렬해서 이 순서대로 \(x\)값을 할당해주고 수식을 계산하면 문제를 해결할 수 있다.

C. BOJ 18249

그림을 그려서 정리해보면, 답이 피보나치 수열과 같다는 것을 알 수 있다. 그대로 구현해주면 풀린다.

D. BOJ 12919

문자열이 생길 수 있는 형태를 생각해보자. 원본 문자열 \(S\)에 대해, \(S\)를 뒤집은 것을 \(R\) 이라고 하면, 연산을 통해 만들어질 수 있는 형태가 \(SA*\), \(BA*RA*\), \(BA*SA*BA*\), 꼴임을 알 수 있다.

따라서, \(T\) 중간 지점에서 \(S\) 혹은 \(R\)을 찾은 다음에 그 위치의 왼쪽, 오른쪽의 \(B\) 개수 및 맨 처음에 \(B\)로 시작하는지 여부를 통해 \(S\)에서 \(T\)를 만들 수 있는지 판별이 가능하다. 이 식을 구현해주면 해결할 수 있다. 일일히 substring으로 다 체크해주어도 길이 제한이 50밖에 안 되어서 구현은 넉넉하게 해도 된다.

E. BOJ 10517

점 세 개 주어졌을 때 그 삼각형의 외접원 구하는 문제인데, 수식을 잘 찾아서 구현해도 되겠지만 너무 귀찮아서 최소 외접원 휴리스틱으로 구하는 코드 예전에 짰던거 그냥 복사붙여넣기해서 풀었다. 오버킬이긴 한데 이런 자잘한 기하 구현 너무 귀찮고 재미없다..

F. BOJ 2066

각 그룹의 카드 상태는 0~4까지 5개의 수로 표현할 수 있다. 이런 그룹이 9개이므로 \(5^9\)가지 상태가 존재하고, 각 상태마다 최대 9*8=72가지의 다음 상태를 봐야 한다. 모두 곱하면 1억을 좀 넘는 정도로, 충분히 시간안에 들어가는 크기임을 알 수 있다. 따라서 DP로 문제를 해결 가능하다. 다만 상태를 vector 등으로 관리하면 DP로 쓰기 어려우므로 상태를 5진법으로 잘 관리하는 구현 디테일이 필요하다.

G. BOJ 18320

이분탐색으로 접근해보자. \(X\)가 고정됐을 때, \(Y\)를 반복해서 지급하는 과정이 너무 긴 것이 문제이다. 하지만 \(Y\)가 감소되는 속도를 기준으로 생각해보면, \(Y\)값은 항상 \(N-G\)에 대한 \(X\)의 나눗셈 간격으로 감소하므로, 많아야 \(sqrt\) 정도만 변화한다는 것을 알 수 있다. 따라서 현재 \(Y\)값에서 다음 \(Y\)값으로 감소하는 타이밍을 수식으로 계산한다음 그 사이에는 항상 같은 \(G\)값이 유지된다고 생각하고 풀 수 있다. 이렇게 할 경우 이분탐색의 한 스텝에 걸리는 시간이 최대 \(O(sqrt(N))\) 이므로 문제를 \(O(sqrt(N)logX)\) 시간에 해결할 수 있다.

H. BOJ 13482

어떠한 방식으로든 값 1을 만들어내는 확률을 99% 정도로 수행할 수 있다면, 이로부터 2,4,8,16,32,64,128 을 만들고 2진법 덧셈 연산으로 주어진 값을 생성해낼 수 있다. 수학적으로 정확히 어떻게 도출하는지는 모르겠지만 로컬에서 주어진 문제대로의 연산식을 구현한 다음 이리저리 굴려보면 아래 코드의 k가 1을 99.89% 확률로 만든다는 것을 알 수 있다.

a = ? max ?
b = a max a
c = b max b
d = c max c
e = d max d
f = e max e
g = f max f
h = g max g
i = h max h
j = i max i
k = j / d

따라서 \(l = k + k\), \(m = l + l\), ...을 반복해서 모든 비트에 대응되는 값을 만들고 이들의 덧셈으로 주어진 수를 표현하면 모든 수를 80% 이상의 확률로 만들어낼 수 있다.

BOJ 23834

\( solve(x) \)를 \(x\) 번 움직였을 때 가능한 최대 이동 거리(중간에 이동이 정지되지 않고) 라고 하자. 이렇게 하면, \(solve(x) = max ( solve(x-1) - A_x, solve(x-2) - A_{x-1} + A_x, \dots, solve(x - m) - A_{x-m+1} + \dots + A_x ) \) 가 된다.

이렇게 정의를 하고 나면, 위 식의 값을 관리하는 세그먼트 트리를 만들어 \(solve(x)\)를 \(O(logN)\)에 계산할 수 있다. 업데이트시에는 일단 \(solve(x)\)를 계산한 후 세그먼트 트리에 \(solve(x) - 2 \cdot A_{x+1} \)을 저장하고, 다음 칸으로 넘어갈 때 세그먼트 트리의 모든 칸에 \(A_{x+1}\) 만큼을 더해주면 항상 수식이 성립하게 된다. 따라서 \(O(NlogN)\)에 문제를 해결 가능.

BOJ 17304

그래프에서 양방향 간선은 한 방향만 선택하되, 모든 정점의 indegree가 1이상이 되게 만들어야 한다.

먼저 단방향 간선은 항상 골라도 상관 없으므로 모두 골라놓고 정점의 indegree를 계산해보자. 이제 양방향 간선에 대해 다음의 세 가지 케이스가 생긴다.

두 정점 모두 indegree가 0 보다 큰 경우 : 이 경우는 어차피 조건을 만족하므로 방향을 어떻게 해도 상관없다. 따라서 무시해도 된다.
한 정점만 indegree가 0보다 크고, 하나는 0인 경우 : 이 경우는 무조건 indgree가 0보다 큰 정점에서 0인 정점으로 향하게 방향을 설정해주어야한다.
둘 다 indegree가 0 : 어느 방향으로 설정해야할지 알 수 없다.

두 번째 케이스의 경우, 방향을 설정해주고 나면 원래 세번째 케이스였다가 두번째 케이스로 바뀌는 경우가 발생한다. 이 경우도 반복해서 모두 방향을 설정해주고 나면 세 번째 케이스만 남는다. 반복 과정은 위상 정렬과 유사한 방식으로 구현할 수 있다.

이 때, 세번째 케이스의 경우 양방향 간선으로 연결된 컴포넌트가 트리라면 절대 조건을 만족할 수 없다. 따라서, 각각의 컴포넌트에 대해 간선 개수 가 정점 개수 이상인지를 모두 체크해주면 문제를 해결할 수 있다. 이 모든 과정은 그래프 탐색만으로 충분하므로 \(O(N+M)\)에 문제를 해결할 수 있다. 사실 양방향 간선 체크 등의 과정에서 로그를 붙이면 구현하기가 쉽기 때문에 실제로는 로그 붙여서 풀었다.

Prompt412 Round 193

8개 다 풀어서 만족스러웠다. 앞 문제들이 좀 전형적이고 쉬운 편이었어서 쉽게 푼 감이 있긴 한데, H번은 아이디어를 빠르게 잘 떠올린 것 같아서 기분이 좋았다. 다만 G번에서 문제를 잘못 읽은 것 때문에 엄청 말려서 시간을 낭비했는데 이런 부분을 고칠 필요는 있을 것 같다.

농 위키