백준14958 Rock Paper Scissors

작성일 | In

문제 링크

  • http://icpc.me/14958

문제 출처

  • 2017 대전 리저널 H번

사용 알고리즘

  • FFT

풀이

가위를 냈을 때의 최대 승리횟수, 바위를 냈을 때의 최대 승리횟수, 보를 냈을 때의 최대 승리횟수는 fft를 이용해 구할 수 있습니다.
위 3가지 케이스 중 최댓값을 선택하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

typedef complex<double> cpx;
typedef vector<cpx> vec;

void fft(vec &a, bool inv){
    int n = a.size();
    for(int i=1, j=0; i<n; i++){
        int bit = n >> 1;
        for(; bit<=j; bit>>=1) j -= bit;
        j += bit;
        if(i < j) swap(a[i],a[j]);
    }
    for(int len=2; len<=n; len<<=1){
        double ang = 2 * M_PI / len;
        if(inv) ang = -ang;
        cpx w(cos(ang), sin(ang));
        for(int i=0; i<n; i+=len){
            cpx wp(1, 0);
            for(int j=0; j<len/2; j++){
                cpx u = a[i + j], v = a[i + j + len/2] * wp;
                a[i + j] = u + v;
                a[i + j + len/2] = u - v;
                wp *= w;
            }
        }
    }
    if(inv){
        for(int i=0;i<n;i++) a[i] /= n;
    }
}

vector<int> mul(const vector<int> &a,const vector<int> &b){
    vector <cpx> aa(a.begin(), a.end()), bb(b.begin(), b.end());
    int n = 1;
    while(n < a.size() || n < b.size()) n <<= 1;
    aa.resize(n); bb.resize(n);
    fft(aa, 0); fft(bb, 0);
    for(int i=0; i<n; i++) aa[i] *= bb[i];
    fft(aa, 1);
    vector<int> res(n);
    for(int i=0;i<n;i++) res[i] = int(aa[i].real() + (aa[i].real()>0 ? 0.5 : -0.5));
    return res;
}

int conv[111];
int n, m;
string _a, _b;
vector<int> a, b;
int res[202020];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    conv['R'] = 0, conv['P'] = 1, conv['S'] = 2;
    cin >> n >> m >> _a >> _b;
    a.resize(n); b.resize(m);
    for(int i=0; i<n; i++) a[i] = (conv[_a[i]] + 1) % 3;
    for(int i=0; i<m; i++) b[i] = conv[_b[i]];
    for(int i=0; i<3; i++){
        vector<int> u(n + m), v(m);
        for(int j=0; j<n; j++) u[j] = a[j] == i;
        for(int j=0; j<m; j++) v[j] = b[m-j-1] == i;
        vector<int> ret = mul(u, v);
        for(int j=0; j<n+m; j++) res[j] += ret[j];
    }
    cout << *max_element(res+m-1, res+n+m);
}