최종적으로 200점을 받았다. 처음 목표가 2, 3번을 풀고 1번을 긁는 것이었는데 목표는 달성해서 만족스럽다.
처음에 3번을 잡았는데, 아무리 생각해도 인덱스 트리로 log N번 연산하는 방법밖에 떠오르지 않아서 말렸다. 다른 방법을 생각하려고 해도 너무 졸려서 아무런 생각이 안 나서 잠깐 자고 일어났다.
다행히 자고 일어나니까 컨디션이 괜찮아져서 다시 풀기 시작했다. 3번을 좀 더 잡고 있다가 2번으로 갈아탔다. 2번은 풀릴 것 같은 풀이가 금방 생각나기는 했는데 예외 케이스가 있을 것 같다는 생각 때문에 풀이 검증에 시간이 걸렸다. 의사 코드로 표현하면 다음과 같고, 실제로는 리넘버링 및 인덱스 트리를 써서 구현했다.
Pinball
fill L[0 .. N] with INF
fill R[0 .. N] with INF
L[0] = 0
R[N] = 0
let res = INF
for each machine {
let costL = min L[machine.L .. machine.R]
let costR = min R[machine.L .. machine.R]
res = min(res, costL + costR + machine.D)
L[machine.C] = min(L[machine.C], costL + machine.D)
R[machine.C] = min(R[machine.C], costR + machine.D)
}
print res == INF ? -1 : res
3번은 생각을 뒤집어서, ‘이런 연산 결과를 어떻게 구할 수 있을까’가 아니라 ‘쿼리에서 한 번만 연산을 할 수 있다고 할 때 어떻게 할 것인가’로 생각을 바꾸었더니 금방 떠올랐다. 기준점들을 잡아서 기준점 좌우의 연산값을 저장해 놓은 뒤, 쿼리가 들어오면 쿼리 구간에 포함되는 기준점을 찾아 저장된 값을 이용해 합치면 되겠다는 생각을 했다.
이제 이러한 기준점들을 어떻게 잡아야 효율적으로 Init 함수에서의 쿼리 횟수를 줄일 수 있을 것인지를 생각하면 되는데, 이진 탐색의 중심점들을 이용하면 된다. 코드는 다음과 같다.
Secret
#include "secret.h"
#include <vector>
using namespace std;
const static int MAX = 1010;
static int n;
static vector < int > left[MAX], right[MAX];
void cut(int l, int r, int A[]){
if(l > r) return;
int m = (l+r)>>1;
int i, last;
last = A[m+1];
right[m].push_back(A[m+1]);
for(i = m+2; i<=r; i++){
last = Secret(last, A[i]);
right[m].push_back(last);
}
last = A[m];
left[m].push_back(A[m]);
for(i = m-1; i>=l; i--){
last = Secret(A[i], last);
left[m].push_back(last);
}
cut(l, m-1, A);
cut(m+2, r, A);
}
void Init(int N, int A[]){
n = N;
cut(0, N-1, A);
}
int Query(int L, int R){
int nowL = 0, nowR = n-1;
while(true){
int m = (nowL+nowR)>>1;
if(R == m){
return left[m][R-L];
} else if(L == m+1){
return right[m][R-L];
} else if(L <= m && m+1 <= R){
return Secret(left[m][m-L], right[m][R-m-1]);
} else {
if(m+1 < L) nowL = m+2;
else if(R < m) nowR = m-1;
}
}
}
2, 3번을 다 풀고 나니 30분쯤 남았는데 1번이 기하에 output only라 제대로 건드려보지 못하고 끝났다. 그래도 나쁘지는 않았다고 생각한다.
ps. Round 1 2위는 하츠네 미쿠(8tusne 39)였다. 나는 이 분의 정체를 안다 ㅋㅋㅋ
