[editorial] SRM 436 Div1 Hard - CircularShifts

  • Kamin
    Kamin

    안녕하세요~ 처음으로 올려보는 에디토리얼이네요ㅎㅎ
    (회사에서 일 없어서 놀고 있었더니, 여민형이 에디토리얼 쓰라고 압박하셔서,,,)
    문제 보기
    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
    예)
    multiply.png
    위의 예에서 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;
        }
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    12년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    오옷 간지 ㅋㅋㅋㅋㅋㅋㅋㅋ 에디토리얼 멋있어용~ ㅋㅋㅋ


    12년 전 link
  • Kamin
    Kamin

    흐흐 영광이네요+ _+


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.