안녕하세요 aim_higher입니다.
Code Force Round #806(Div. 4) 코드 검토 및 해결.
난이도 때문에 A와 B는 생략합니다.
씨 암호
https://codeforces.com/contest/1703/problem/C
- 구현
문제를 간략하게 설명:
n개의 바퀴가 있는 자물쇠가 있습니다.
자물쇠의 한 바퀴에 대해 두 번의 시도가 가능합니다.
- 실험 U: 휠을 한 단계 위로 돌립니다.
(9 → 0) - 실험 D: 휠을 한 단계 아래로 내립니다.
(0 → 9)
각 휠에 대해 U와 D의 조합으로 구성된 테스트 값이 제공됩니다.
이 모든 시도를 수행하면 잠금 결과가 표시됩니다.
즉, 초기 상태 → 시가 → 최종 상태입니다.
문제에서 출력해야 하는 것은 초기 상태이기 때문에
시험 값의 U와 D를 모두 반전
최종 상태 → 반환 값 → 차례로 첫 번째 상태로 이동합니다.
또한 U와 D의 구현을 진행하면
각 바퀴의 값이 0보다 작거나 9보다 큰 순간이 있을 것입니다.
0보다 작으면 9로 보내고, 9를 넘으면 0으로 보낸다.
D. 더블 스트링
https://codeforces.com/contest/1703/problem/D
- 데이터 구조
길이가 8을 초과하지 않는 n개의 문자열이 있습니다.
주어진 문자열 각각에 대해 주어진 문자열 중 두 개를 결합하여 해당 문자열을 생성할 수 있는지 여부를 결정해야 합니다.
또한 문자열을 결합할 때 동일한 문자열을 두 번 결합할 수 있습니다.
지도 선언 후
입력 값을 받으면 해당 문자열이 맵에 저장됩니다.
그리고 각 문자열에 대해 맵에 있는지 확인하여 2로 자를 수 있는 사례 수를 결정할 수 있습니다.
문자열 abacb를 분할하는 예를 들어 보겠습니다.
이 문자열을 2로 자르는 방법의 수는 다음과 같습니다.
/ bacb → 지도(“a”) && 지도(“bacb”)
ab / acb → 지도(“ab”) && 지도(“acb”)
aba / cb → 지도(“aba”) && 지도(“cb”)
abac / b → 지도(“abac”) && 지도(“b”)
위와 같이 저장된 카드로 나올 수 있는 경우의 수를 결정할 수 있습니다.
최대 문자열 길이가 8로 제한되므로 시간 복잡도는 O(n)입니다.
E. 미러 그릴
https://codeforces.com/contest/1703/problem/E
- 구현
0과 1의 그리드가 제공됩니다.
그리드에 있는 셀의 경우 (0 → 1), (1 → 0)과 같이 뒤집을 수 있습니다.
위의 최소 시도를 사용하여 그리드가 반복적으로 90도 회전하더라도
항상 원래 모양을 유지하는 방식으로 만들어야 합니다.
그리드를 자세히 보면 알 수 있듯이
n이 홀수일 때와 짝수일 때 둘 다 (n/2) × (n/2) 단위로 구성된 사분면을 동시에 스캔하기만 하면 됩니다.
따라서 간단히 말해서 그리드를 4분의 1로 자르십시오.
그러나 n이 홀수일 때 격자는 4등분하므로,
가운데 십자 모양의 셀은 따로 구분하셔야 합니다.
사분면의 기준점(i,j)을 제2사분면으로 생각하면,
- 사분면 1은 (j,n-1-i)입니다.
- 제3사분면은 (n-1-j,i)입니다.
- 네 번째 사분면은 (n-1-i, n-1-j)입니다.
이 4개의 셀을 동시에 확인하여 어떤 숫자가 더 빨리 결합되는지 확인할 수 있습니다.
(그래요 n/2횡단)
홀수인 경우 (n/2, i), (n/2, n-1-i), (i, n/2), (n-1-i, n/2)가 동시에 결정됨 . (그래요 n/2횡단)
물론 회전을 해도 항상 같기 때문에 정확한 중심점을 정할 필요는 없다.
Q. 불평등을 만족시키는 파리의 또 다른 문제
https://codeforces.com/contest/1703/problem/F
- 수학 *이것은 나의 분류입니다.
배열이 주어지면 Ai < i < Aj < j와 같은 순서쌍을 찾으십시오.
먼저 집합 Ai < i < Aj < j를 풀어봅시다.
- (Ai < i) / (Aj < j)
- 나
(Ai < i)와 (Aj < j)를 자세히 보면, 도끼 < x 형태임을 알 수 있다
모든 순서쌍에 대해 (Ai < i) 및 (Aj < j)를 만족하려면,
반면에 축 >= x 위의 부등식은 항을 제거함으로써 항상 충족될 수 있습니다.
그래서 입력값을 받으면 입력값(도끼)는 인덱스(엑스), 입력 단계에서 필터링할 수 있습니다.
마지막으로 나만족하는 경우를 찾아보자.
태스크에서 제공하는 첫 번째 테스트 케이스를 예로 들어 보겠습니다.
(x, 도끼) 형태로 용기에 넣으면(1, 1) (2, 1) (3, 2) (4, 3) (5, 8) (6, 2) (7, 1) (8, 4) 및 축 >= x삭제하면
(2, 1) (3, 2) (4, 3) (6, 2) (7, 1) (8, 4)가 남습니다.
이때 j를 기준점으로 하여 j=2에서 6으로 이동하면(1<=i 따라서 3개의 가능한 순서쌍이 있습니다. 시간 복잡도는 O(n)입니다. G. 좋은 키, 나쁜 키 디졸브…
이 논리로 코드를 작성하면 정답이 나옵니다.
(*오래 선언하지 않아서 틀렸다는 사실…)
https://codeforces.com/contest/1703/problem/G