Codeforces Round #736

대회 링크 : Div2 / Div1

총평 : 수학을 좀만 더 잘 했으면 좋았겠다.. 싶은 대회. 적당한 퀄리티의 Mathforces였다.

Virtual (Div 1) 후기

3644점, 실제 대회 기준으로 100등에 해당하는 점수이다.

A번이 처음에 너무 어려워보여서 당황했으나, 다행히도 금방 생각이 나서 풀었다.

B번은 여기저기서 많이 본 테크닉을 짬뽕한 문제인데, 풀이는 금방 나왔지만 구현에서 이상하게 삽질을 해서 2번이나 틀렸다. 수열에서 인접한 값 차이 갖고 노는 문제에서 n=1인 케이스는 왜 주는건지..

C번을 처음에 봤는데 진짜 너무 어려워서, 한 30분동안 아무 것도 못 했다. 원래 한 5~10분 보고 잘 모르겠으면 D로 넘어가는 게 맞지만, 코포 버추얼을 너무 오랜만에 해서 그런지 괜히 오기가 생겨서 시간만 버렸다.

정신을 차리고 D1을 까 보니까 오히려 풀이가 훨씬 쉽게 나왔다.. 나의 어리석음을 깨닫는 순간이었다. D2는 D1보다 훨씬 어려운 거 같아서 일단 접고, E도 한 5분 보고 접고, 다시 C로 갔다.

또 한 20분 뻘짓하다가, 갑자기 점화식이 딱 생각이 나서 드디어 C를 풀었다. 역시 풀고 나니까 쉬워서 힘이 쭉 빠졌다.. D2랑 E는 남은 시간 안에 절대 못 풀 거 같아서 놀러갔다.

 

Div1 A

P가 5 이상이므로 P는 홀수이다. 따라서, P % 2 = 1이고 P % (P-1) % 1 이다. 2랑 (P-1)을 출력해 주면 된다.

코드 : http://codeforces.com/contest/1549/submission/126598597

 

Div1 B

왼쪽부터 차례대로 내 폰을 맨 윗줄 어디에 주차시킬지 생각해 보자. 왼쪽에서 i번째 자리에 폰이 있을 경우,
- 맨 윗 줄 i번째 자리에 폰이 없으면 거기 갖다놓기
- 맨 윗 줄 i-1번째 또는 i+1번째 자리에 상대 폰이 있으면 거기 갖다놓기
의 두 가지 경우가 가능하다.
약간 생각을 해 보면, 주차가 가능할 경우 일단 해서 손해 볼 것이 없고, 이 때 가능한 한 왼쪽에다 갖다놓는 것이 가장 이득임을 알 수 있다.

코드 : http://codeforces.com/contest/1549/submission/126598885

 

Div2 C / Div1 A

power가 낮은 사람에서 높은 사람 쪽으로 각 간선에 방향을 줘 보자. 내가 언젠가 제거되는지 여부는 "나한테서 나가는 정점이 있다"와 같음을 알 수 있다. 각 정점의 outdegree를 세 주면서 값이 0인 정점의 개수를 같이 갱신해 주면 O(N+Q).

코드 : http://codeforces.com/contest/1548/submission/126425331

 

Div2 D / Div1 B

A[i] mod M = A[i+1] mod M은 (A[i] - A[i + 1]) mod M = 0 과 같은 식이므로, 문제에서 주어진 조건은 결국 (A[i] - A[i + 1]) mod M = (A[i + 1] - A[i + 2]) mod M = ... = (A[j - 1] - A[j]) mod M = 0 과 같다.
B[i] = A[i] - A[i + 1]인 배열 B를 생각해 보면 B[i], ..., B[j - 1]을 모두 나누는 M > 1이 존재해야 하므로, (gcd(B[i], ..., B[j]) > 1인 가장 긴 구간 길이) + 1이 답이 된다.

이 문제를 푸는 방법은 여러 가지가 있겠지만, 분할 정복을 이용하면 간단하게 해결할 수 있다. [L, R] 구간을 절반으로 나눠서 [L, M] / [M+1, R] 에서 재귀적으로 답을 구했다 치면, 이제 고려할 것은 A[M]과 A[M+1]을 모두 포함하는 구간뿐이다.
A[M]에서 시작해서 왼쪽으로 쭉 누적 gcd를 구하고, A[M+1]에서 시작해서 오른쪽으로 쭉 누적 gcd를 구했다고 하자. 각각에서 누적 gcd가 변하는 지점은 log(10^18)번 이내로 나타나기 때문에 (gcd가 변했다면 적어도 1/2배 이하로 줄어들기 때문) gcd가 변하기 직전 지점들만 모아놓고 이중 for문으로 답을 갱신하면 된다. 코드를 참고하면 좋을 듯.

코드 : http://codeforces.com/contest/1548/submission/126427021

 

Div2 E / Div1 C

n을 고정한 상태에서, 쿼리로 주어지는 x에 대해 \( \binom{3}{x} + \binom{6}{x} + \cdots + \binom{3n}{x} \) 의 값을 빨리 구하면 된다. 별 거 아닌 것 처럼 생긴 식인데, 식을 막 갖고 놀다 보면 의외로 까다롭다..

풀이의 핵심은 \( \Sigma \binom{3k-2}{x} \), \( \Sigma \binom{3k-1}{x} \), \( \Sigma \binom{3k}{x} \) 를 각각 A[x], B[x], C[x] 라고 정의해서 세 값을 동시에 점화식을 통해 구하는 것이다. 참고로 우리가 구하고 싶은 값은 C[x]이다. 식을 열심히 가지고 놀다 보면 아래와 같은 점화식을 얻는다.

A[x] = B[x + 1] - A[x + 1]
B[x] = C[x + 1] - B[x + 1]
C[x] = \( \binom{3n+1}{x+1} \) - C[x + 1] + A[x + 1]

이항계수는 O(n) 전처리 후에 O(1)에 구할 수 있으므로, 위 점화식을 x = 3n부터 x = 1까지 쭉 계산해 놓으면 모든 x에 대한 C[x] 값을 구할 수 있다.

코드 : http://codeforces.com/contest/1548/submission/126434651

 

Div2 F1 / Div1 D1

픽의 정리라는 엄청 유명한 정리가 있다. 모든 꼭짓점이 격자점인 단순다각형 (볼록, 오목 상관 x) 에 대해, S = a + b/2 - 1 (S : 넓이, a : 도형 내부에 있는 격자점 개수, b : 도형 경계(변 or 꼭짓점)에 있는 격자점 개수) 라는 식이 성립한다는 정리이다. 모르면 못 푸는 문제가 꽤 있으니 알아두면 좋다.

D1은 "모든 격자점 x, y좌표 짝수"라는 조건이 붙어 있어서 넓이는 무조건 짝수인 정수임을 알 수 있다. 이제 문제에서 요구하는 조건은 "a가 홀수이다"인데, 보통 b를 계산하는 것이 a를 계산하는 것보다 쉽기 때문에 "b/2가 짝수이다"로 바꿔서 생각하자.
"b가 4의 배수이다"를 판단하려면 좀 어려운데, (사실 이걸 풀면 D2도 풀 수 있다 ㅋㅋ) 다행히도 "모든 격자점 x, y좌표가 짝수"라는 조건 덕분에 모든 좌표를 2로 나눠 준 다음에 거기서 b를 구하면 원래 입력에서 b/2의 값과 똑같음을 알 수 있다!
b의 홀짝성은 각 좌표의 홀짝성만 가지고 결정할 수 있기 때문에 모든 가능한 (2^2)^3 (3개의 점에 대해 x, y좌표 홀/짝) 가지 경우에 대해 b가 짝수가 될 때만 그 경우에 해당하는 조합 가짓수를 세서 더해 주면 된다. 시간복잡도는 O(N)이다. (상수 64가 붙긴 함)

코드 : http://codeforces.com/contest/1548/submission/126431290

 

Div2 F2 / Div1 D2

추가예정..?

 

Div1 E

추가예정..?