백준 14958 / C++

https://www.acmicpc.net/problem/14958

14958번: Rock Paper Scissors

 

[ 풀이 ]

매번 옮겨가면서 계산하면 O(mn)이다. FFT로 합성곱 구하는 과정을 NlogN에 해주자.

합성곱은 컨볼루션 형태로 ck=ai*bk-i와 같이 인덱스합이 일정하므로 인덱스를 맞춰서 더하려면

역순으로 뒤집은다음 곱해주면 된다. 

이기는 조합은 (R,P), (S,R), (P, S) 이므로, 문자열 2개에 대해 위에 R이 있다면 1, 아래에 P가 있다면 1을 

써서 합성곱해준다. 나머지 2개 쌍도 마찬가지로 이기는 조합을 만들어놓고 계산해주면 된다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using cpx = complex<double>;
using vec = vector<cpx>;
const double PI = acos(-1);
string s, t;
int win[200002];

// fft 
void FFT(vec& f, bool inv) {
    int n = f.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        while (!((j ^= bit) & bit)) bit >>= 1;
        if (i < j) swap(f[i], f[j]);
    }
    for (int i = 1; i < n; i <<= 1) {
        double x = inv ? PI / i : -PI / i;
        cpx w = cpx(cos(x), sin(x));
        for (int j = 0; j < n; j += i << 1) {
            cpx p = cpx(1, 0);
            for (int k = 0; k < i; k++) {
                cpx tmp = f[i + j + k] * p;
                f[i + j + k] = f[j + k] - tmp;
                f[j + k] += tmp;
                p *= w;
            }
        }
    }
    if (inv) {
        for (int i = 0; i < n; i++) {
            f[i] /= n;
        }
    }
}

// h=f*g
vec mul(vec& f, vec& g) {
    vec pf(f.begin(), f.end()), pg(g.begin(), g.end());
    int n = 1;
    while (n < max(pf.size(), pg.size())) n <<= 1;
    n <<= 1;
    pf.resize(n), pg.resize(n);
    FFT(pf, 0); FFT(pg, 0);
    vec h(n);
    for (int i = 0; i < n; i++) h[i] = pf[i] * pg[i];
    FFT(h, 1);
    for (int i = 0; i < n; i++) {
        h[i] = cpx(round(h[i].real()), 0);
    }
    return h;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m; cin >> n >> m;
    cin >> s >> t;
    vec a1(n), b1(m), a2(n), b2(m), a3(n), b3(m);
    // reverse
    reverse(t.begin(), t.end());
    // 1:(S<R) 2:(R<P) 3:(P<S)
    for (int i = 0; i < n; i++) {
        if (s[i] == 'S') a1[i] = 1;
        if (s[i] == 'R') a2[i] = 1;
        if (s[i] == 'P') a3[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        if (t[i] == 'R') b1[i] = 1;
        if (t[i] == 'P') b2[i] = 1;
        if (t[i] == 'S') b3[i] = 1;
    }
    vec r1 = mul(a1, b1);
    vec r2 = mul(a2, b2);
    vec r3 = mul(a3, b3);
    int ans = 0;
    // 시작 a0.... an-1 과 b0 ... bm-1 곱: c(m-1)
    // 끝  .... an-1 과 b0 .... bm-1 곱 c(m+n-2)
    for (int i = m - 1; i < m + n - 1; i++) {
        win[i] = r1[i].real() + r2[i].real() + r3[i].real();
        ans = max(ans, win[i]);
    }
    cout << ans;
}