안녕하세요~ 처음으로 올려보는 에디토리얼이네요ㅎㅎ
(회사에서 일 없어서 놀고 있었더니, 여민형이 에디토리얼 쓰라고 압박하셔서,,,)
문제 보기
X[0]~X[N-1], Y[0]~Y[N-1] 이 주어졌을 때,
X[0]*Y[0] + X[1]*Y[1] + ... + X[N-1]*Y[N-1]
X[0]*Y[1] + X[1]*Y[2] + ... + X[N-1]*Y[0]
...
X[0]*Y[N-1] + X[1]*Y[0] + ... + X[N-1]*Y[N-2]
위 N개의 식 중 최대값을 구하는 문제입니다.
[풀이]
N이 6000인데 이를 전부 계산하게 되면, N2 번의 곱셈연산이 필요하므로 시간 안에 답이 나오지 않게 됩니다.
먼저 X배열은 그대로 둔 뒤, Y 배열을 뒤집어서 생각해보면 하나의 규칙성을 발견할 수 있습니다.
(앞으로 표기되는 Y는 문제에서 주어진 Y를 reverse시킨 배열입니다.)
X[0]*Y[N-1] + X[1]*Y[N-2] + ... + X[N-1]*Y[0] → X's idx + Y's idx = N-1
X[0]*Y[N-2] + X[1]*Y[N-3] + ... + X[N-1]*Y[N-1] → X's idx + Y's idx = N-2 or N-2+N
...
X[0]*Y[0] + X[1]*Y[N-1] + ... + X[N-1]*Y[1] → X's idx + Y's idx = 0 or 0+N
예)

위의 예에서 R[4], R[0]+R[5], R[1]+R[6], R[2]+R[7], R[3]+R[8] 가 이 문제에서 비교하고자 하는 값이 됩니다.
이제 저 곱셈을 빛의 속도(?)로 하고 싶은 것이 문제일텐데요.
여기서 소개할 방법은 Karatsuba_algorithm에 바탕을 둔 방법입니다.
먼저 배열의 절반을 뚝 잘라, 빨간색 부분과 파란색 부분을 따로 계산할 수 있다는 것은 눈에 들어올 것입니다.
그리고 남은 보라색 부분은 빨간색 윗부분과 파란색 아랫부분의 곱, 빨간색 아랫부분과 파란색 윗부분의 곱들임을 알 수 있습니다.
그럼 이 보라색 부분은 어떻게 계산할 수 있을까요? 바로, 빨간 부분과 파란 부분을 겹친 다음 식
X[0]+X[2] X[1]+X[3] X[4]
Y[0]+Y[2] Y[1]+Y[3] Y[4]
을 같은 방법으로 곱한 결과에서 빨간색결과와 파란색결과를 적절히 빼주면 보라색 부분이 나오게 됩니다.
왜 그런지는 식을 직접 풀어보면 되는데요ㅎ
예를 들어, (X[0]+X[2])*(Y[1]+Y[3]) 에서는 X[0]*Y[1]과 X[2]*Y[3]가 빠지고 필요한 X[0]*Y[3], X[2]*Y[1]만 남게 됩니다.
사실, 이 부분은 소스를 보시는게 가장 빠를 것 같습니다. (무책임..._-;)
대회 때는 Petr가 위의 아이디어를 사용하여 풀었습니다.
sin, cos이 등장하는 FFT보다는 간결해서 좋네요ㅎㅎ
[소스]

#define REP(i, n) for(int i=0; i<(n); i++)
typedef long long ll;
typedef vector<int> VI;
VI multi(VI X, VI Y)
{
    int N = X.size();
    VI R(2*N, 0);
    if(N>100) {
        int N2 = N/2;
        VI X2(X.begin()+N2, X.end());
        VI Y2(Y.begin()+N2, Y.end());
        X.resize(N2); Y.resize(N2);
        VI Red = multi(X, Y);
        VI Blue = multi(X2, Y2);
        REP(i, N2)    X2[i] += X[i], Y2[i] += Y[i];
        VI Purple = multi(X2, Y2);
        REP(i, Red.size())        R[i]+=Red[i],        Purple[i]-=Red[i];
        REP(i, Blue.size())        R[i+2*N2]+=Blue[i],    Purple[i]-=Blue[i];
        REP(i, Purple.size())    R[i+N2]+=Purple[i];
    }
    else {
        REP(i, N) REP(j, N)
            R[i+j] += X[i]*Y[j];
    }
    return R;
}
class CircularShifts { 
public: 
    int maxScore(int N, ll Z0, int A, int B, int M) {
        VI X(N), Y(N);
        REP(i, 2*N) {
            Z0 %= M;
            if(i<N)    X[i] = Z0%100;
            else    Y[i-N] = Z0%100;
            Z0 = Z0*A + B;
        }
        reverse(Y.begin(), Y.end());
        VI R = multi(X, Y);
        int sol = 0;
        REP(i, N)    sol = max(sol, R[i]+R[i+N]);
        return sol;
    }
}