APIO 2015 Bali's sculptrues

Codeforces에서 열렸던 Avito 대회에서 나온 D랑 비트 크기 55로 바꾸고, Bitwise OR 연산에서 AND 연산으로 바꾸기만 하면 완전히 동치이다.

참고로 역대 APIO 문제들 중에서 가장 쉬웠던 문제들 중 하나라고 한다.... 난이도 실화?

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

코드포스 D문제는 맨 끝에 올려놓을테니 완전히 이해되면 한번 풀어보길 바란다.

문제 요약

주어진 배열 A를 K개의 그룹으로 분할하려고 한다. 각 그룹에 들어가있는 수들의 합을 구하여 전부다 Bitwise OR 연산을 수행하였을 때 최대값을 구하여라.

풀이

일단 우리는 Bitwise OR 연산이라는 것에 주목해야 한다. Bitwise 계산이고, 최대 들어오는 값이 10억(대략 2의 40제곱)이긴 하지만, 안전빵으로 2^43의 비트까지 잡아두도록 하자. 

또한, 일반적인 dp처럼 생각하면 안된다는 것을 알아채야한다. 그 이유는, 그 전까지 띠고 있는 최대값을 구하는 방식으로 정답까지 구할 수 있다는 보장이 없기 때문이다. 

또한, 최소값을 구하기 때문에, 큰거부터 시작해서 최대한 우리는 비트 수를 줄여야 함을 알 수 있다. 큰거부터 시작한 이유는 간단하다. 비트 연산에서, i번째 밑에 있는 비트들로 만들 수 있는 최대의 숫자는 i번째 하나만 켜졌을 때의 값보다 항상 작기 때문이다. 

위 세가지에 근거하여 문제를 해결해보도록 하자.

또한, 서브태스크를 보면 개같이 A=1일 때랑 A가 1이 아닐때 구간이 다르다

그 이유는, A가 1일때랑 아닐떄랑 구하는 방식이 다르기 때문에, 시간복잡도가 달라지기 때문이다.

A=1일때가 더 쉬우니, A=1일때부터 알아보고, 이를 확장하여 A가 1이 아닐때를 알아보자.

기본적인 베이스는 "T번째의 비트가 없을 경우, 조각상을 많아봤자 K개의 그룹으로 분할할 수 있는가?" 이다

만약 K개의 그룹으로 분할할 수 없다면, T번째의 비트는 무조건적으로 있어야 하는 비트이므로, 켜주고, 그 외에는 꺼준다.(최소값을 만족하기 위해서)

A=1

A=1일때는 간단하다.

dp[i] :  i번째 조각상까지 만들 수 있는 최소의 그룹수

이렇게 되면, dp[i]는 다음과 같이 정의된다.

(단, (partsum[i]-partsum[j])|val == val를 만족하는 j의 값)

여기서 val은 현재까지 누적된 최소의 Bitwise OR 값에서 T번쨰의 비트가 꺼진 값이다.

partsum은 부분합을 저장해놓은 배열이고, 두개의 차이와 val의 Bitwise OR값이 val이란 것과 동일하다의 의미는 partsum[i]-partsum[j]에서 현재 비트 T를 가지고 있지 않다를 의미한다. 따라서, 조각상을 분해할 수 있는 것이다.

이 dp에서 i를 1부터 n까지 돌려준다. 다 돌리고 나서, dp[n]값을 봤을 때 K보다 작거나 같으면 없어도 되므로 꺼주고, 그 외에는 켜준다.

시간복잡도는 이고, N이 2000보다 작으므로 1초 씹어먹고 남는다.

이를 바탕으로 A가 1이 아닐때로 확장해보자

A !=1

A가 1이 아닐때에는 복잡하다. 

다음과 같은 dp배열을 선언하자.

dp[i][j] : i번째 조각상까지 j개의 분할로 만들 수 있는가?

i번째 조각상을 0개로 분할하는 것은 불가능하므로, dp[i][0]=false

0번째 조각상을 i개로 분할하는 것은 불가능하므로, dp[0][i]=false

이렇게 되면, dp[i][j]는 다음과 같이 정의할 수 있다.

val의 정의는 앞과 동일하다.

이 dp를 j는 K까지, 그리고 j까지 돌려준 반복문을 i를 기반으로 해서 N까지 돌려준다.

다 돌리고 난 후에, dp[N][A]에서 dp[N][B]까지 돌려보면서 만약 하나라도 true가 되면 분할할 수 있다는 것이므로 꺼주고, 그 외에는 켜준다.

시간복잡도는 이고, K는 최대 N이기 때문에 최악일때의 시간 복잡도는  이다. 이것도 씹어먹음

이렇게 해서 비트값을 관리해주고, 마지막엔 비트값이 켜져있으면 더해주고 꺼져있으면 지나가면 된다.

답이 int범위를 넘어갈 수도 있기 때문에, 혹시나 모르니 long long으로 선언하고 하자. 정신건강에 해롭지 않기 위해...^^

코드포스 D도 내가보기엔 소스 코드 4줄~5줄 정도 바꾸면 바로 AC이다. 어제 어디선가 많이 풀어봤는데... 하면서 대회하다가 끝나자마자 앗 발리~~~ 인생;;; 하면서 땅을 치고 후회했던 기억이 있다. 

소스

https://oj.uz/submission/49403

참고

http://codeforces.com/contest/981/problem/D