[코드포스] Round #806 (Div. 4)

안녕하세요 aim_higher 입니다.
코드포스 Round #806 (Div. 4) 코드리뷰 및 업솔빙입니다.
난이도 관계상 A, B번은 생략하겠습니다.

---

C. Cypher
https://codeforces.com/contest/1703/problem/C

• Implementation(구현)

 
간단히 문제를 설명하자면,
n개의 휠을 가지고 있는 자물쇠가 있습니다.
 
자물쇠의 한 휠에 대해서 2가지의 시행을 할 수 있습니다. 

• 시행 U : 휠을 한 칸 위로 돌립니다. (9 → 0)
• 시행 D : 휠을 한 칸 아래로 돌립니다. (0 → 9)

---

각 휠에 대해서 U, D의 조합으로 이루어진 시행값이 주어지는데요
이러한 시행값을 모두 수행하게 된다면 자물쇠의 결과값이 나올 겁니다.
즉, 최초 상태 → 시행값 → 최종 상태 입니다.
 
문제에서 출력해야하는 것은 최초 상태이기 때문에
시행값의 U, D를 모두 반전해주고
최종 상태 → 역시행값 → 최초 상태 순서로 찾아가면 됩니다.
 
추가적으로 U, D 시행을 진행하다보면
각 휠의 값이 0보다 작아지거나 9를 넘어가는 순간이 올텐데
0보다 작아질때는 9로 보내주고, 9를 넘어갈때는 0으로 보내주시면 됩니다.

---

D. Double Strings
https://codeforces.com/contest/1703/problem/D

• Data Structures(자료구조)

 
문자열 길이가 8을 넘지 않는 n개의 문자열들이 주어집니다.
주어진 문자열들 각각마다, 주어진 문자열들 중에 2개를 조합하여 해당 문자열로 만들 수 있는지를 판별해야 합니다.
추가적으로, 문자열 조합을 할 때 동일 문자열을 중복으로 조합해도 됩니다.

---

map<string, bool>을 선언해준 후에,
입력값을 받을 때 해당 문자열을 map에다가 저장을 해줍니다.
 
그리고 문자열 각각마다 2개로 자를 수 있는 모든 경우의 수에 대해서 map에 있는지 확인하여 판별하면 됩니다.
 
abacb라는 문자열에 대해서 슬라이싱을 한다고 예시를 들어보겠습니다.
이 문자열을 2개로 자를 수 있는 경우의 수는 다음과 같습니다.
 

a / bacb → map["a"] && map["bacb"]
ab / acb → map["ab"] && map["acb"]
aba / cb → map["aba"] && map["cb"]
abac / b → map["abac"] && map["b"]

 
위와 같이 나올 수 있는 경우의 수에 대해서 저장해뒀던 map으로 판별해주면 됩니다.
 
문자열 최대 길이를 8로 제한해줬기 때문에 시간 복잡도는 O(n)입니다.

---

E. Mirror Grid
https://codeforces.com/contest/1703/problem/E

• Implementation(구현)

0, 1로 이루어진 그리드가 주어집니다.
그리드 내의 셀에 대해서 (0 → 1), (1 → 0)과 같이 뒤집을 수 있습니다.
위 시행을 최소로 사용하여 그리드가 90도 회전을 반복해도
항상 원래의 형태를 유지하도록 만들어야 합니다.

---

그리드를 유심히 보시면 아시겠지만,
n이 홀, 짝일때 모두 (n/2) × (n/2) 단위로 이루어진 사분면을 동시에 훑어주면 됩니다.
그러니까 쉽게 말해서 그리드를 4등분으로 자르려고 노력하시면 됩니다.
 
단, n이 홀일 때는 그리드가 4등분으로 나누어 떨어지지 않으므로
가운데 십자가 모양의 셀들에 대해서 판별을 따로 해주어야 합니다.
 
사분면의 기준점 (i, j)을 제2사분면으로 잡고 생각한다면

• 제1사분면은 (j, n-1-i)
• 제3사분면은 (n-1-j, i)
• 제4사분면은 (n-1-i, n-1-j)

이 4개의 셀을 동시에 확인하여 어떤 수로 통일시키는 게 빠를지 판별해주시면 됩니다. (i는 n/2번 순회)
 
홀수의 경우에는 (n/2, i), (n/2, n-1-i), (i, n/2), (n-1-i, n/2)를 동시에 판별해주시면 됩니다. (i는 n/2번 순회)
당연하게도, 정중앙은 돌려도 항상 같기때문에 판별할 필요가 없습니다.

---

F. Yet Another Problem About Paris Satisfying an Inequality
https://codeforces.com/contest/1703/problem/F

• Math(수학) *필자의 분류입니다.

주어진 배열에 대해서 Ai < i < Aj < j 를 만족시키는 순서쌍을 구하면 됩니다.

---

먼저 Ai < i < Aj < j라는 문장을 풀어봅시다.

• (Ai < i) / (Aj < j)
• i < Aj

(Ai < i)과 (Aj < j)를 유심히 보시면 Ax < x 형태임을 알 수 있습니다.
모든 순서쌍에 대해서 (Ai < i) 그리고 (Aj < j)임을 만족시키려면,
반대로 Ax >= x 인 항을 소거시켜버리면 위의 부등식을 항상 만족시킬 수 있습니다.
 
그래서 입력값을 받을 때 입력값(Ax)이 인덱스(x)보다 크면 아예 입력 단계에서 거르시면 됩니다.
 
마지막으로 i < Aj를 만족시키는 경우를 찾아봅시다.
 
문제에서 제공하는 첫번째 테스트케이스를 예시로 들어보겠습니다.
(x, Ax) 형태로 컨테이너에 집어넣게 된다면
(1, 1) (2, 1) (3, 2) (4, 3) (5, 8) (6, 2) (7, 1) (8, 4) 이고, Ax >= x를 소거하게 되면
(2, 1) (3, 2) (4, 3) (6, 2) (7, 1) (8, 4)가 남습니다.
 
이때, j를 기준점으로 생각하여 j = 2부터 6까지 순회하게 된다면 (1 <= i < j 이므로, j = 1은 불가능)

• (3, 2) : j = 2 일 때, Aj = 2 → i < 2, 0개
• (4, 3) : j = 3 일 때, Aj = 3 → i < 3, 1개 { (2, 1) }
• (6, 2) : j = 4 일 때, Aj = 2 → i < 2, 0개
• (7,  1) : j = 5 일 때, Aj = 1 → i < 1, 0개
• (8, 4) : j = 6 일 때, Aj = 4 → i < 4, 2개 { (2, 1), (3, 2) }

그래서 나올 수 있는 순서쌍은 총 3개입니다.
이러한 로직으로 코드를 작성하시면 정답이 나옵니다.
(*필자는 long long을 선언하지 않아 틀렸다는 사실....)
 
시간 복잡도는 O(n)입니다.

---

G. Good Key, Bad Key
https://codeforces.com/contest/1703/problem/G

• 미분류

업솔빙 중입니다...