https://codeforces.com/contest/1933
총평: 그냥저냥 쉬웠네요 역시 Div3
A: 그냥 단순히 정렬하면 음수와 양수들을 뭉쳐놓을 수 있고, 그러면 한번의 연산으로 모든 음수를 양수로 바꿀 수 있습니다.
그러므로 그냥 모든 값의 절대값의 합이 답. 이것이 최대라는 것도 자명하죠.
B: 만약 처음부터 모든 수의 합이 3의 배수라면 답은 0입니다.
그것이 아니라면, 3으로 나눈 나머지가 1인 숫자가 있거나 전체 합이 3k+2꼴이라면 답은 1입니다.
만약 3으로 나눈 나머지가 1인 수가 있다면 그 수를 지우면 전체 합이 3의 배수가 되며,
전체 합이 3k+2꼴이라면 아무 수에 1을 추가해주면 전체 합이 3의 배수가 됩니다.
이 이외에는 무조건 답이 2가 됩니다. 위의 조건에서 걸러진 숫자는 무조건 전체 합이 3k+1꼴이여야 하는데,
그러면 아무 숫자에 1을 더해주는 연산을 2번 해주면 2번만에 전체 합을 3의 배수로 만들 수 있기 때문입니다.
C: L이 10^6 이하며, a와 b가 2이상이기 때문에, 고려해야하는 a^x, b^y는 최대 log_2(10^6), 즉 약 20개입니다.
그러므로 각 TC마다 x 최대 20개, y 최대 20개, 총 400개를 전탐색으로 고려해주고 L = k a^x b^y가 되는 k가 직접 존재하는지 찾으면 됩니다.
각 TC마다 약 400번의 연산이면 충분하며, TC 개수는 10000개니까 5초안에 충분히 돌아갑니다.
D: 여기서부터 어려워지기 시작합니다.
숫자들을 전부 정렬해두었다고 가정합시다. 즉, a1 <= a2 <= ... <= an이라고 가정합니다.
만약 i>=2인 i에 대해서 ai % a1 > 0인 숫자가 있다면, 존재합니다.
(b1,b2,...,bn) = (ai,a1,a2,a3,...)으로 두면 됩니다. 나머지의 성질에 의하여 ai%a1은 a1보다 무조건 작고, a1이 전체 수중의 최소이기 때문에
(ai%a1) mod aj는 항상 ai%a1이 되어, 전체 연산값은 ai%a1이 됩니다. 이게 0보다 크다는게 가정이므로 무조건 조건에 맞습니다.
만약 ai % a1 == 0이 모든 i에 대해서 성립한다면, a1 != a2인지 확인합니다. 만약, a1 != a2라면, a1
a1 mod aj = a1이 항상 성립합니다. ai>=1이 입력에서 보장되므로 (b1,b2..,bn) (a1,..,an)으로 두면 됩니다.
만약, a1 == a2라면, 어떻게 하든 성립하게 만들 수 없어서 답은 NO가 됩니다.
중간에 어떻게 연산하든 a1의 배수가 튀어나오며(모든 ai가 a1의 배수므로), 그러면 뒤에 존재하는 a2의 존재 때문에 (a1의 배수) % a2라는 연산이 무조건 발생하게 됩니다. 이러면 결과는 0이 나오며, 이 이후엔 어떻게 하든 결과가 0으로 고정되어 원하는 수열을 절대 만들 수 없습니다.
E: 누적합 배열을 만들어서 잘 판단해주면 됩니다.
부분 문자열의 길이가 a_i들의 합과 같아지도록 지점을 찾고, 거기서 왼쪽으로 i칸, 오른쪽으로 i칸 가는것이 결과가 같기 때문에
적당한 i를 찾고, 그 i에 대해서 왼쪽/오른쪽 어느게 우선되는지 잘 찾으면 됩니다.
F: 엄청 어려운 시뮬레이션처럼 보이나 이는 낚시며, 상대속도 개념을 생각하면 쉽게 시뮬레이션이 가능합니다.
돌이 위로 계속 올라가는게 시뮬레이션을 어렵게 하는데, "매초마다 돌이 1칸 위로 올라간다"로 보지 말고, "매초마다 사람이 1칸 아래로 내려간다"로 생각해도 무방합니다. 상대속도를 생각하면요.
그러면, 이 문제는 각 돌의 위치가 고정되어 있고 사람이 (x,y)에 있을때, (x,y) 가만히 있기 / (x+1,y+1)로 이동하기 / (x,y+2)로 이동하기
세가지가 가능한 문제로 볼 수 있습니다. 이제 최단거리 문제를 풀면 되는데 칸이 꽤 넓어서 그대로 다익스트라를 적용하면 시간초과를 받게 될것입니다.
다행히 "(x,y) 가만히 있기"옵션이 있기 때문에, 최단거리 문제를 DP문제로 바꿀 수 있고, DP를 풀어서 최단거리를 구하면 됩니다.
G: 유명한 문제입니다. 조건을 만족하는 배열은 무조건 "1x2모양 타일들을 연결하는것"이 됩니다.
예를 들어,
ㅁㅁㅇㅇ
ㅇㅇㅁㅁ
이라던가
ㅇㅁ
ㅁㅇ
ㅁㅇ
ㅇㅁ
같은게 가능합니다.
가로로 1x2로 되어 있는것 4개, 세로로 2x1로 되어 있는것 4개, 총 8가지만 가능하며, 998244353으로 나눈 나머지를 출력하라 했지만 사실 답은 항상 8이하임이 보장됩니다.
8가지 다해보면서 되는것들 개수 세주면 됩니다.
P.S. 밀린 후기 허겁지겁씁니다 헠헠
