19849. 문제지 나르기

19849.cpp

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define R(i,n) for(int i=0; i<n; i++)
using namespace std;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, Q;
	cin>>N>>Q;
	alignas(32) long X[2048];
	memset(X, 63, 16384);
	R(k, N+Q) {
		alignas(32) long Y[2048], a[11];
		R(i, 11) cin>>a[i];
		Y[0]=0;
		R(i, 11) Y[0]-=a[i];
		R(i, 11) a[i]*=2;
		R(i, 11) R(j, 1<<i) Y[j+(1<<i)]=Y[j]+a[i];
		if(k<N) {
			R(i, 2048) X[i]=min(X[i], Y[i]);
		} else {
			long m=0;
			R(i, 2048) m=max(m, Y[i]-X[i]);
			cout<<m<<'\n';
		}
	}
}

풀이:

• 절댓값이 있는 식을 만났을 땐, 가능하면 절댓값을 떼려고 시도해보는 것이 좋다.
• dist(x, y)에서 x[i] > y[i]이면 x[i] - y[i]이고, x[i] < y[i]이면-x[i] + y[i]이므로, 상태가 정해져 있다면 x와 y를 분리해서 생각할 수 있다.
• i가 11가지밖에 안 되니, 각 i에 대해 x[i] > y[i]인 상태를 비트로 표현해서 생각하면 어떨까?
• 하지만 여전히 대소관계를 비교해야 하는 게 거슬린다. 만약 대소관계가 맞지 않을 경우 x[i]와 y[i] 모두 음수가 되어 결과적으로 관계가 맞을 때보다 거리가 감소한다. 그런데 우리는 최댓값을 구해야 하므로, 실제 대소관계를 생각할 필요가 없다!
• 따라서 각 상태의 최솟값을 저장하고, 적절히 처리해 주면 된다.

SIMD

• 코드를 제대로 짰다면 다른 부분들은 SIMD에 맞게 코드를 수정하는 것이 그리 어렵지 않으나, 비트마스크의 부분합을 구하는 부분에서 __builtin_ctz나 __builtin_clz, 혹은 i&-i를 쓰는 등 최하위/최상위 비트를 직접 구한다면 영 쉽지가 않다. 따라서, 위 코드는 아래 부분이 핵심이다.

R(i, 11) R(j, 1<<i) Y[j+(1<<i)]=Y[j]+a[i];

• 보다시피 최상위 비트인 i를 고정해놓고 i번 비트가 꺼진 곳(j)을 이용하여 켜진 곳(j+(1<<i))을 업데이트해 준다.
• 당연하지만 인덱스를 계산할 때는 |과 +이 동일한 결과를 낸다는 것이 보장되어 있을 경우, +를 사용해야 컴파일러에게 더 직접적으로 힌트를 줄 수 있다.