Codeforces Round #785 (Div. 2)
https://codeforces.com/contest/1673
평소보다 조금 어려웠고, E에서 수학적 센스가 부족했다.
A. Subtle Substring Subtraction
Alice는 짝수 길이의 최대 substring을 챙길 것이고 Bob는 나머지를 먹을 것이다.
-> 전체 길이가 짝수면 다 먹고, 홀수라면 맨 앞 혹은 맨 뒤는 버린게 Alice의 점수
B. A Perfectly Balanced String?
일반성을 잃지않고 적당히 a, b, c ... (ㄱ)이 s에 존재한다고 가정하자
그렇다면 두 개의 같은 알파벳 (ㄴ) ... (ㄴ) 형태의 substring이 있다면, 이 사이에 a, b, ... (ㄱ)이 모두 존재하여야 한다.
만일 (ㄴ) .... (ㄴ) 사이에 (ㄷ)이 존재하지 않는다면, triplet((ㄴ) ... (ㄴ) , (ㄴ), (ㄷ))를 선택할 수 있기 때문이다.
C. Palindrome Basis
어차피 Palindrome은 그렇게 많지 않다.
모든 palindrome에 대해서 냅색을 해주면 된다. (밑에 풀이 참고)
https://codeforces.com/contest/1673/submission/155445485
D. Lost Arithmetic Progression
1) C가 B에 속하는지 체크 -> 아니라면 0
2) C의 제일 작은 항을 sC (small C), 제일 큰 항을 bC (big C)라 하자. 똑같이 sB, bB 정의 가능
만일 sC - d3 < sB 거나 bC + d3 > bB라면 무한히 많은 A가 존재할 수 있다.
-> (A의 최소값이 한없이 작아지거나 최댓값이 한없이 커짐)
3) 이제 각각의 가능한 A의 공차 d1에 대해서 조건을 만족하는 A의 개수를 세면 된다.
(d1의 조건 : lcm(d1, d2) = d3) 이므로 d3의 약수 중에서 d1을 찾아내면 된다.
-> 이때 만족하는 A의 개수는 왼쪽 끝의 개수가 d3 / d1 오른쪽 끝의 개수가 d3 / d1이니 이 둘을 곱하면 된다.
https://codeforces.com/contest/1673/submission/155446162
E. Power or XOR
적당히 j개의 항들을 power로 묶어버린 다음에 그런 항이 몇 번 등장하는지 세주면 된다.
-> 이때 20개가 넘는 항들이 power로 묶이지 않기 때문에 그런 항의 수는 20 * n 개 정도이다.
-> b[i], ... b[i + j - 1]이 power로 묶였다고 하고 그 값은 1 << bit라 하자. (단, bit < (1 << 20))
-> 그러면 b[i] 왼쪽과 b[i + j - 1] 오른쪽은 반드시 XOR 기호가 존재한다.
-> 따라서 총 남은 XOR의 개수는 k - 2이고, XOR이 들어갈 수 있는 자리는 n - 2 - j이다. (양끝은 예외처리)
-> 편의상 남은 개수를 left, 자리를 seat라 한다면 C(seat, left) + C(seat, left + 1) ... C(seat, seat) = S번 등장한다.
-> 어차피 마지막에 모든 값들을 XOR해주기에 이 값의 홀짝성만 중요하다.
-> 이때 C(n, r) = C(n - 1, r - 1) + C(n - 1, r)이므로 이를 적용한다면
-> S = C(seat, 0) + C(seat, 1) + C(seat , 2) +...+ C(seat, seat - left)
= C(seat - 1, 0) + C(seat - 1, 0) + C(seat - 1, 1) + C(seat - 1, 1) + C(seat - 1, 2) + ...+ C(seat - 1, seat - left)
= C(seat - 1, seat - left) -> 이 값이 홀수일 때 답의 bit를 뒤집어주면 된다.
-> C(n, r)의 홀짝성은 lucas theorem으로 인해 (n | r) == n이면 1이고 그게 아니라면 0이다.
https://codeforces.com/contest/1673/submission/155443468
F. Anti-Theft Road Planning
F를 업솔빙해보았는데 확실히 쉽다는 생각이 들었다.
일단 기본적인 아이디어는 32 x 32 판에 (board[32][32]) 0, 1, ... 1023의 숫자를 부여하면 된다.
-> 예를 들어 이전의 위치가 prev이고 tester가 숫자 x를 주면 나중의 위치를 (prev ^ x)이라고 대답해주면 된다.
다만, board[i][j]의 값으로 naive하게 i * 32 + j를 부여하면 모든 경로의 길이가 48000을 넘어간다.
그렇기에 '적당한 방법'으로 경로의 길이를 줄여주면 된다.
-> 효율적인 방법으로 1, 2, 4, 8, 16 ..., 512를 전체 칸의 절반에 부여하면 된다.
0 0 0 ... 0 0
0 0 0 ... 0 0
...
512 512 512 ... 512 512
512 512 512 ... 512 512 의 방법으로 배치하면 512가 있는 숫자와 512가 없는 숫자가 인접한 횟수를 최소로 할 수 있다.
0 0 0 0 0
...
128 128 128 128 128
128 128 128 128 128
...
0 0 0 0 0 의 방법으로 128을 배치하면 또다시 128의 사용량을 최소로 줄일 수 있다.
0 0 0 0 0
...
32 32 32 32 32
...
0 0 0 0 0
...
32 32 32 32 32
...
0 0 0 0 0 의 방법으로 32를 또 배치할 수 있다.
-> 현재는 이를 가로만 고려해주었지만 세로에서 다시 256, 64, 16...을 배치하면 1024개의 칸을 모두 구분할 수 있다.
-> 이때 경로의 합은 47616으로 48000보다 작기에 문제 의도에 부합한다.
https://codeforces.com/contest/1673/submission/155471315