Educational codeforces #80 D - Minimax Problem(이분탐색, 비트마스크)

https://codeforces.com/contest/1288/problem/D

 

<문제설명>

최대 3e5개의 숫자 배열이 들어온다. 각 배열은 최대 m(m<=8)개의 숫자로 구성된다. 이 배열들 중 어떤 두 배열을 선택했을 때 각 요소의 둘 중 최대값으로 배열 b를 만든다. 이 때 배열 b의 최소값이 최대가 되는 경우 선택한 배열 i, j를 구해라

 

<풀이>

설명이 길고 복잡하지만 그림으로 한 번만 따라서 그려보면 이해가 될 것.

 

배열에 들어가는 값의 범위가 0~1e9이므로 b의 최솟값도 0~1e9사이의 값을 갖는다.

 

5 0 3 1 2

2 3 0 6 3

예를들어 위와같은 두 배열을 생각해보자. 두 배열을 3이상이면 1, 3 미만이면 0으로 바꿔보자

1 0 1 0 0  -> 20

0 1 0 1 1  -> 11

두 배열을 or했을 때 1 1 1 1 1이 되므로 b는 3이상의 최소값을 갖는다.

 

이번엔 4 이상이면 1, 4미만이면 0으로 바꿔보자

1 0 0 0 0

0 0 0 1 0

OR 연산 후에 1 1 1 1 1이 되지 않으므로 b는 4를 최소값으로 갖지 못한다

 

여기까지 생각했어도 isPossible(mid) 부분을  구현하는것이 쉽지 않다.

모든 배열에 대해 2중 for문으로 검사하면 n^2으로 시간초과다. 좀더 최적화 해보자

 

하나의 배열이 갖을 수 있는 비트값은 0 ~ (1<<m)-1이다. i번째 배열과 j번째 배열이 동일한 비트값을 갖는 경우, 우리는 i와 j중 아무거나 가져다 쓰면된다. 뭔말이냐? 어떤 비트값이 존재하냐 존재하지 않냐가 중요하다는 것.

msk[배열인덱스] = 비트값 대신

msk[비트값] = 배열인덱스로 전처리 해두면

모든 비트값에 2중 for문으로 검사하는 것으로 (1<<m) * (1<<m) 시간에 풀 수 있다.

 

msk[비트값] 을 불린타입으로 안하는 이유는 a1, a2를 초기화하기 위해서.

 

<코드>

const int MAX = 3e5 + 2;
int n, m, a[MAX][9];
int a1, a2;
bool isPossible(int k) {
	vector<int> msk(1 << m, -1);
	for (int i = 0; i < n; i++) {
		int cur = 0;
		for (int j = 0; j < m; j++)
			if (a[i][j] >= k)
				cur |= (1 << j);
		msk[cur] = i;
	}
	if (msk[(1 << m) - 1] != -1) {
		a1 = a2 = msk[(1 << m) - 1];
		return true;
	}
	for(int i=0; i<(1<<m); i++)
		for(int j=0; j<(1<<m); j++)
			if (msk[i] != -1 && msk[j] != -1 && (i | j) == (1 << m) - 1) {
				a1 = msk[i];
				a2 = msk[j];
				return true;
			}
	return false;
}

int main() {
	FAST;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> a[i][j];

	int lo = 0, hi = 1e9;
	while (lo < hi) {
		int mid = (lo + hi+1) / 2;
		if (isPossible(mid)) lo = mid;
		else hi = mid-1;
	}
	cout << a1+1 << " " << a2+1 << '\n';
}

 

<생각>

이분탐색 부분에 lo=mid+1로 했다가 한 번 틀렸다.

내 코드에서 lo는 그 값이 항상 valid해야 한다는 점을 명심하자.

 

배열[인덱스] = value를 뒤집어 배열[value] = 인덱스로 풀어도 논리에 이상이 생기지 않는 경우다. 유념하자