📝 문제 정보#
번역#
문제#
가위바위보(RPS) 기계가 있으며, 이 기계는 가위, 바위, 보 중 하나를 무작위로 생성한다. 당신도 비슷한 소형 가위바위보 기계를 가지고 있다. 게임 전에, RPS 기계는 길이 $n$의 가위바위보 선택 목록을 생성하고, 당신의 기계도 길이 $m$의 선택 목록을 생성한다. 즉, RPS 기계의 전체 선택 목록과 당신의 기계의 선택 목록을 모두 알고 있다. 물론, 각 기계의 선택은 세 가지 옵션(가위, 바위, 보) 중 하나이다.
이제 가위바위보 게임을 시작한다. 매 대결에서 RPS 기계의 선택 목록과 당신의 기계의 선택 목록을 순서대로 비교하여 어느 쪽이 이기는지 판정한다. 단, 당신은 가장 많은 승리 횟수를 얻기 위해 RPS 기계의 선택 일부를 건너뛸 수 있다. 대결을 시작하기로 결정한 후에는 대결이 끝날 때까지 건너뛸 수 없다. R은 바위, P는 보, S는 가위를 나타낸다.
예를 들어, RPS 기계의 목록이 “RSPPSSSRRPPR“이고 당신의 기계의 목록이 “RRRR“라고 하자. 최대 승리 횟수를 얻으려면, RPS 기계의 선택을 3개 또는 4개 건너뛴 후 대결을 시작해야 한다. (Figure H.1 참조.) 그러면 3번 승리할 수 있다. 무승부는 고려하지 않는다.
Figure H.1. $n = 12$, $m = 4$일 때 RPS 기계를 상대로 최대 승리를 얻는 위치.
RPS 기계의 선택 목록과 당신의 선택 목록이 주어질 때, 최대 승리 횟수를 얻을 수 있는 위치를 구하시오.
입력#
표준 입력으로 읽는다. 첫째 줄에 두 양의 정수 $n$과 $m$이 주어진다 ($1 \le m < n \le 100{,}000$). $n$은 RPS 기계의 문자열 길이이고, $m$은 당신의 기계의 문자열 길이이다. 다음 줄에는 RPS 기계의 선택 목록이, 그다음 줄에는 당신의 기계의 선택 목록이 주어진다.
출력#
표준 출력으로 출력한다. 첫째 줄에 최대 승리 횟수를 나타내는 정수를 출력한다.
🧐 관찰 및 접근#
- 약간 밀어서 합성곱을 최대화 하는 맛..
- BOJ 25456 궁금한 시프트랑 비슷해보인다!
- 그런데 0/1이 아니라 RSP인데…
- 근데 그냥 RSP 따로 해서 FFT를 3번 돌리면 되지 않을까?
- 최대 승리를 위한 위치가 아니라 최대 승리 횟수 자체만 승리하면 된다! 쉽네
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
string S, T; cin >> S >> T;
vector<int> ans(N+M);
string RPS = "RPS";
int sz = 1;
while(sz < N+M) sz <<= 1;
rep(i, 0, 3){
vector<cd> A(sz), B(sz);
rep(j, 0, N) A[j] = S[j] == RPS[i];
rep(j, 0, M) B[M-1-j] = T[j] == RPS[(i+1)%3];
FFT::fft(A);
FFT::fft(B);
rep(j, 0, sz) A[j] *= B[j];
FFT::fft(A, true);
rep(j, 0, N+M-1) ans[j] += round(A[j].real());
}
int mx = -1;
rep(i, M-1, N+M-1) mx = max(mx, ans[i]);
cout << mx;
}