발굽 보 가위 마이너스 원

*참고: 이 문제의 시간 제한은 기본값의 1.5배인 3초이다.*

발굽 보 가위 게임에서 베시와 엘시는 \(1\dots N\)으로 번호가 매겨진 \(N\)가지(\(1 \leq N \leq 3000\)) 발굽 기호 중 하나를 낼 수 있으며, 각 기호는 서로 다른 재료에 대응한다. 서로 다른 재료들이 어떻게 상호작용하는지에 대한 복잡한 표가 있으며, 그 표에 따라 다음 중 하나가 일어난다.

• 한 기호가 이기고 다른 기호가 진다.
• 두 기호가 비긴다.

발굽 보 가위 마이너스 원도 비슷하게 진행되지만, 베시와 엘시는 각각 양쪽 발굽에 하나씩, 기호 두 개를 낼 수 있다. 넷이 낸 기호 네 개를 모두 확인한 뒤, 각자 자신의 두 기호 중 하나를 골라 낸다. 승부는 일반적인 발굽 보 가위 규칙에 따라 결정된다.

엘시가 각 게임에서 내려고 계획한 \(M\)개(\(1 \leq M \leq 3000\))의 기호 조합이 주어질 때, 베시는 엘시를 상대로 확실한 승리를 보장하는 기호 조합이 몇 가지인지 알고 싶다. 기호 조합은 순서쌍 \((L,R)\)로 정의되며, \(L\)은 소가 왼쪽 발굽으로 내는 기호, \(R\)은 오른쪽 발굽으로 내는 기호이다. 각 게임에 대해 이를 계산할 수 있는가?

Problem credits: Suhas Nagar

배점

• 입력 2-6: \(N,M\le 100\)
• 입력 7-12: 추가 제약이 없다.

Problem credits: Suhas Nagar

첫째 줄에 발굽 기호의 수와 베시와 엘시가 하는 게임의 수를 나타내는, 공백으로 구분된 두 정수 \(N\)과 \(M\)이 주어진다.

이어지는 \(N\)개의 입력 줄 중 \(i\)번째 줄은 문자 \(i\)개 \(a_{i,1}a_{i,2}\ldots a_{i,i}\)로 이루어지며, 각 \(a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}\)이다. \(a_{i,j} = \texttt D\)이면 기호 \(i\)는 기호 \(j\)와 비긴다. \(a_{i,j} = \texttt W\)이면 기호 \(i\)는 기호 \(j\)를 이긴다. \(a_{i,j} = \texttt L\)이면 기호 \(i\)는 기호 \(j\)에게 진다. \(a_{i,i} = \texttt D\)임이 보장된다.

다음 \(M\)개의 줄에 공백으로 구분된 두 정수 \(s_1\)과 \(s_2\)(\(1 \leq s_1,s_2 \leq N\))가 주어진다. 이는 그 게임에서 엘시가 내는 기호 조합을 나타낸다.

\(M\)개의 줄을 출력한다. \(i\)번째 줄에 \(i\)번째 게임에서 베시가 엘시를 이기는 것을 보장하는 기호 조합의 수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > US Open > Bronze