Bali Sculptures - APIO 2015

BOJ - 발리의 조각상

APIO 2015에 나온 문제이고, 몇몇은 여지껏 APIO에 나온 문제들 중 가장 쉬운 문제였다고 한다.(...)

본인은....대회 때 손도 못댔기에 할 말이 없다...(당시에 결과가 논리연산이라는걸 보고 아무런 생각도 못했다.)

지금 보면 어렵지는 않지만, 아직도 쉬운 줄은 모르겠다....ㅇㅅㅇ;;

KOI 2009 - 숫자 맞추기 (숫자 맞추기가 더 쉽다)

IOI 2008 - Linear Garden (더 어려운 듯...)

이런 느낌...

문제를 해결하기 위한 핵심은 최소의 아름다운 정도를 이진수로 나타냈을 때, 그 이진수에 2^k 꼴의 bit가 존재하는가? 를 판단해주면 된다.

가장 큰 k부터 k를 줄여나가면서 현재의 2^k에 해당하는 값이 조각상을 분할 할 때 존재하지 않아도 된다면, 무조건 현재의 2^k 값을 없애야 한다.

왜냐하면 k보다 작은 모든 i에 대해 2^i의 총 합은 2^k 보다 작기 때문이다. 즉, 현재 k번째 bit가 존재하지 않아도 된다면 무조건 최종 아름다운 정도에서도 k번째 bit는 0임이 보장된다.

모든 Yi의 합이 2^50이 안된다는 걸 이용해서 처음에는 아름다운 정도의 값을 (2^50)-1로 하고, 이후 k번째 bit가 존재하지 않아도 될 때마다 k번째 bit를 0으로 만들어주는 식으로 진행하면 된다.

본인은 A>1 일 경우 N<=100 임을 이용해서 두 경우로 나눠 짰다.

1. A==1

DP - O(N^2*50)

k를 49에서부터 1씩 감소시키면서 진행한다.

현재 아름다운 정도의 값에서 2^k를 뺀다. 이후 다음 dp를 시행한다.

dp[i] = (0<=j<i 이고 ((Yj+1~Yi의 합)|(아름다운 정도) = (아름다운 정도))를 만족하는 j들의 dp[j]의 최솟값) + 1

dp[0]을 제외한 모든 dp값은 무한대로 둔다.

위 식의 의미는 i번째 조각상까지의 분할에서 현재 아름다운 정도에 존재하지 않는 bit를 만들지 않도록 조각상을 분할하는 과정에서 사용되는 분할된 구간 수를 의미한다. A가 1이므로 우리는 가능한 최소 구간 수로 분할하는 것이 최적임을 알 수 있다.

만약, dp[N]>B 이거나 dp[N] = 무한대라면 우리는 현재 k번째 비트 없이 조각상을 분할할 수 없다는 것이 된다. 그렇다면 아름다운 정도의 k비트를 다시 1로 만들어준다. 현재 bit가 무조건 존재해야 한다는 의미. 

이 과정을 k가 음수가 아닐 때까지 진행하고 난 아름다운 정도가 최소의 아름다운 정도임이 보장된다.

2. A != 1

A가 1이 아니라면, 최소로 분할하는 것이 무조건 가능한 분할이 아니게 된다.

본인은 A>1 이면 N<=100 임을 이용해서 해결했다.

O(N^3*50)

A가 1일 때와 같이 진행해주면 된다. 하지만 dp 식을 조금 바꿔야 한다.

dp[a][i] = (0<=j<i 이고 ((Yj+1~Yi의 합)|(아름다운 정도) = (아름다운 정도))를 만족하는 j들의 dp[a-1][j])

단, dp[0][0] = 1, 나머지는 모두 0

그리고 k번째 비트를 제거해도 되는지에 대한 여부를

A<=i<=B인 dp[i][N] = 1 인 dp가 있을 경우 k번째 비트를 제거해도 되며, 그렇지 않으면 안된다.

현 dp는 i번째 조각상 까지를 a개로 분할하여 현재 아름다운 정도를 유지할 수 있는지를 판단하는 식이다. 즉, 분할하는 수도 고려해준다.

첫 방법처럼 반복하고 나면 결과적으로 나오는 아름다운 정도가 결국 최소임이 보장된다.

서술하고 나니 좀 비직관적이고 생각이 많이 필요해 보인다. (본인도 올바른 풀이를 생각해내고서 맞는지 검토하는 시간을 길게 가짐...)

어느정도는 스스로 증명하는 과정이 필요한 문제인 듯 싶다.