페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8412

가위발굽보 하나 빼기 일 3s 1024MB

문제

"가위발굽보 하나 빼기 일"는 가위바위보 게임의 변형입니다.

  • Bessie와 Elsie는 각각 N개의 심볼(가위, 발굽, 보 등과 유사하게) 중 두 개를 골라, 왼발과 오른발에 각각 하나씩 심볼을 냅니다.

  • 각 게임에서 두 플레이어는 총 4개의 심볼을 내고, 그중 본인이 낸 두 심볼 중 하나를 선택하여 대결합니다.

  • 대결의 승패는 주어진 심볼 간의 상호작용 표에 따라 결정됩니다:

    • W: 이긴다 (Wins)

    • L: 진다 (Loses)

    • D: 비긴다 (Draws)

당신은 Bessie의 전략을 도와야 합니다.
Elsie가 M개의 게임에서 사용할 두 개의 심볼 조합이 주어질 때,
Bessie가 어떤 두 개의 심볼 (L, R) 조합을 내더라도 반드시 이길 수 있는 조합의 수를 계산해야 합니다.

주의: 반드시 이겨야 합니다. 즉, Elsie가 어떤 선택을 하더라도 Bessie가 선택 가능한 심볼로 반드시 승리할 수 있어야 합니다.


입력

첫 줄: 두 정수 N과 M (1 \leq N, M \leq 3000)

다음 N개의 줄: 상호작용 결과를 나타내는 문자표

  • i번째 줄에는 i개의 문자 a_{i,1}, ..., a_{i,i}가 주어짐

  • a_{i,j} \in {D, W, L}

  • a_{i,i} = D

  • 이 표는 대칭을 이루며, a_{j,i}는 a_{i,j}의 반대 결과이다.

다음 M개의 줄: Elsie가 내는 두 심볼 (s_1, s_2) (1 \le s_1, s_2 \le N)


출력

M줄에 걸쳐 각 게임마다 Bessie가 반드시 이길 수 있는 심볼 쌍 (L, R)의 개수를 출력하라.

  • 각 조합은 순서쌍이며, (L, R)과 (R, L)은 서로 다른 경우로 간주된다.


예제 

3 3
D
WD
LWD
1 2
2 3
1 1
0
0
5

이 예시에서 이는 원래의 '발굽 보 가위'에 해당하며, '발굽=1', '보'=2, '가위=3'으로 설정할 수 있습니다.

보가 발굽을 이기고, 발굽이 가위를 이기고, 가위가 보를 이깁니다.

베시가 발굽+보 또는 보+가위 조합에 대해 승리를 보장할 방법은 없습니다.

그러나 엘시가 발굽+발굽을 내면 베시는 다음 조합 중 하나로 반격할 수 있습니다.

  • 종이+종이

  • 종이+가위

  • 종이+발굽

  • 발굽+종이

  • 가위+종이

베시가 이 조합 중 하나라도 내면, 종이를 내어 승리를 보장할 수 있습니다.



출처

USACO 2025 US Open Bronze
로그인해야 코드를 작성할 수 있어요.