[JOI 2014] Secret

문제 링크

https://oj.uz/problem/view/JOI14_secret

문제 요약

어떤 연산자 ★이 있다.

얘가 결합법칙은 성립한다. 즉, (x★y)★z = x★(y★z)가 성립한다.

이 때, 주어진 배열 A에서, 우리는 구간 L,R이 주어질 때,

A[L] ★ A[L+1] ★ A[L+2].... ★ A[R]의 값을 알아내라.

함수형

우리는 Secret란 함수를 통해서 x와 y의 ★의 값을 알 수 있다,

우리가 구현해야하는 함수는 2개이다.

두 함수는 다음과 같다.

1) Init(int N,int A[])

N은 배열에 들어가있는 숫자의 개수이고, A는 배열을 나타낸다.

초기화 단계로, 100점을 맞기 위해서는 Secret 함수를 최대 8000번 불러내야한다. (N<=1000)

만약 답은 맞으나 Secret 함수를 8000번 이상 호출했을 경우엔, 6점을 받게 된다.

2) Query(int x, int y)

A[x]~A[y] 까지의 ★을 처리한 쿼리를 구한다.

100점을 맞기 위해서는 Secret 함수를 최대 1번 불러내야한다.

만약 각 쿼리당 2번 이상 20번 이하를 불러낼 경우, 30점을 받게 된다.

21번 이상 불러낼 경우, 6점을 받게 된다.

풀이

일단, 무식하게 naive 하게 돌려버리면 6점 맞고 뚝배기 뚝딱 당해버린다.

30점 풀이는 각 쿼리를 세그먼트 트리로 관리하는 것인데, 난 안해봤다

바로 100점 풀이로 넘어가자.

100점 풀이에 접근 하기 위해서는 우리는 "결합법칙"이라는 연산에 주목해야한다.

결합법칙이 성립하기 때문에, 서로서로 연산한다음에 붙여주는 식으로 결합이 가능하다.

예를 들어, [1,2,3,4,5,6,7]의 배열을 ★ 연산하는 경우엔 [1,2]★[3,4,5,6,7] 이렇게 연산이 가능하다는 것이다.

이걸 활용해보자

[L,R]의 쿼리를 ★ 처리할 때, 차례대로 처리하는 것이 아니라 결합법칙을 이용하여 처리해보자.

결합법칙을 사용하기 위해 자르는 부분은, L과 R의 중심 부분이다.

즉, [L,R] = [L,M] ★ [M+1,R]이 된다. 여기서, M은 (L+R)/2다.

따라서, 우리는 초기화 하는 과정에서 L,M까지의 ★ 연산한 값을 다 해놓고, M+1에서 R까지의 ★ 한 값을 차례대로 저장해놓는다.

값을 저장해놓는 배열을 ans[MAX][MAX}라고 해놓으면,

ans[M][M]=A[M]

ans[M+1][M+1]=A[M+1]

ans[i][M] = Secret(A[i],ans[i+1][M]),

ans[M+1][i]=Secret(ans[M+1][i-1],A[i])가 된다.

식은 하나라도 변형하면 안된다. 변형하게 되면, 이 식은 교환법칙이 성립한다는 보장이 없기 때문에 틀렸다라고 한다.(30번 틀림 ^^)

이렇게 초기화 하는 과정에선, 총 N(log N - 2)번을 하게 된다.

마지막에 -2가 들어가는 이유는

크기가 1,2인것들을 다 제외해서이다

다 제외하면 log N-2개이고, 각 단계마다 O(N)씩이기 때문에

O(N(log N-2))가 된다.

N이 1000일 때 대략 7965이기 때문에 성공적으로 돌아간다.

이제 Query를 처리해보자

쿼리를 처리해볼때, 세그먼트 트리와 비슷하게 처리해준다.

하지만, 특징이 있다면 우리는 중간점마다의 모든 값을 가지고 있고, 각 쿼리에서 우리가 Init 과정에서 처리해줬던 중간점들의 리스트 중 하나를 이용하여 표현할 수 있다.

중간들 점의 리스트 중 하나를 M이라고 하자.

1) M<L

M이 L보다 작은 순간 답도 없다.

우리는 M을 중심으로 값을 가지고 있는 것이지, L을 기준으로 가지고 있는 것이 아니다.

M에서 R까지의 값과 M에서 L까지의 값을 추정할 수는 있겠으나, 이 두개로 L과 R의 값을 확신할 수 없다.

2) R<M+1

M<L일 떄와 동일

3) M>=L && M+1<=R

[L,R]의 쿼리를 [L,M]과 [M+1,R]의 값들을 ★처리해준다.

각 쿼리당 이런 M을 찾는 경우에선 Secret의 처리가 안들어가기 때문에, 각 쿼리당 Secret를 부르는 최대 횟수는 한번이다.

따라서, 100점 조건을 만족한다.

코드

https://oj.uz/submission/53188