Codeforces Round #735 (Div. 2)-B. Cobb

문제 설명

정수 $n$개 $a_1, a_2,..., a_n$ 와 정수 $k$가 주어졌을 때 $1 \le i < j \le n$ 를 만족하는 정수 쌍 $(i, j)$에 대해서 $i \cdot j - k \cdot (a_i|a_j)$ 의 최대값을 구하라. $|$이 기호는 비트 OR연산자이다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10000)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 두 정수 $n (2 \le n \le 10^5)$와 $k (1 \le k \le min(n, 100))$이 주어진다.

각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (0 \le a_i \le n)$ 가 주어진다.

Output
각 테스트케이스마다 주어진 수식의 최대값을 나타내는 정수를 출력한다.

Example
input
4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

output
-1
-4
3
12

문제 접근

사용한 알고리즘: 비트마스크, 그리디 알고리즘, 수학, 완전탐색
걸린 시간 : 00:20
ㅋㅋㅋㅋㅋㅋㅋㅋ 너무나도 어려운 문제가 B번에 걸려있어서 매우매우매우 당황한 문제이다. 그렇다고 C번을 넘어가니까 더 어려운 문제 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ. 그렇게 A번만을 풀고 이번 virtual contest를 종료했다. 대회를 끝나고 문제 난이도를 봤더니 *1700이더라 그냥 리뷰 들어가보자.

$n$의 상한값이 $100000$이기 때문에 $O(n^2)$ 인 완전탐색으로는 당연히 시간초과가 난다. 그렇기 때문에 다른 방법을 찾아야 하는데, 코드포스식 범위 구하기가 여기서 나온다.

일단 이 식을 유심히 관찰해보자. $i \cdot j - k \cdot (a_i|a_j)$
이 식을 최대로 만들기 위해서는 $i \cdot j$가 최대가 되거나, $k \cdot (a_i|a_j)$가 최소가 되어야 한다. 일단 $i \cdot j$가 최대가 되려면 간단하다. $i = n - 1, j = n$이 되면 된다. 그렇다면 $k \cdot (a_i|a_j)$가 최소가 되기 위해서는 어떻게 해야할까? $k$는 0이 될수 없으므로, $(a_i|a_j)$가 0이 되어야 하고, $a_i, a_j$모두 0이 되어야 할 것이다.

그래서 어쩌라고? 라는 생각이 들지도 모른다. 하지만 조금만 기다려 보면 왜 저식을 관찰해야만 하는지 이유가 나올 것이다.
$i = n - 1, j = n$이면 위의 식은 다음과 같이 변한다. $(n - 1) \cdot n - k \cdot (a_i|a_j)$ 이 식에서 나올 수 있는 최소 값은 무엇일까? $(a_i|a_j)$가 최대가 되야 한다. 여기서 알아야할 OR연산자의 성질이 등장한다. $a_i|a_j < 2 \cdot max(a_i, a_j)$ 라는 식이 반드시 성립한다. 이 식이 이 문제를 푸는 키 포인트 중 하나이다. 저 식에 따르면 $a_i$와 $a_j$모두 최대값이 $n$이므로 $a_i|a_j < 2n$이다. 즉 $a_i|a_j$의 최대값은 $2n - 1$이다. 그렇다면 최소값은 $(n - 1) \cdot n - k \cdot (2n - 1)$이다.

$a_i, a_j$가 모두 0이 되면 위의 식은 다음과 같이 변한다. $i \cdot j$ 여기서 구할 수 있는 최대값은 무엇일까? $n \cdot (n - 1)$일 것이다. 그렇다면 한 수가 $i$일 때, 구할 수 있는 최대값은 무엇일까? $j = n$으로 고정하고, 나머지를 $i$라고 하면 된다. 즉 $i \cdot n$이 최대값일것이다.

이제 다왔다. 가장 최대값이 될 수 있는 경우의 최소값보다 $i \cdot n$이 작다면 그 $i$는 볼 필요가 없다. 즉 $i$가 $i \cdot n \ge (n - 1) \cdot n - k \cdot (2n - 1)$ 를 만족해야 최대값에 영향을 준다는 뜻이다. 이 부분이 바로 2번째 키 포인트이다.

저 식을 만족하는 $i$를 구하고 그 다음 완전탐색을 돌리면 무난하게 문제를 풀 수 있다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        int arr[n + 1];
        for(int i = 1; i <= n; i++) cin >> arr[i];
        int p = max(1, n - 1 - k * 2 + k / n);
        long long ans = -1e12;
        for(int i = p; i <= n; i++){
            for(int j = i + 1; j <= n; j++) ans = max(ans, i * 1LL * j * 1LL - k * 1LL * (arr[i] | arr[j]));
        }
        cout << ans << "\n";
    }
    return 0;
}