Codeforces Round #747 (Div. 2)

Dashboard - Codeforces Round #747 (Div. 2) - Codeforces

 

:(

 

나름 성공적인 코포 복귀전이었지만... 아쉬움이 너무 많이 남아, 할 일을 다 제쳐두고 후기를 쓰고 있다.

 

Prob. A

$\sum_{1-n}^{n-1}=0$ 임을 이용하면 $l=1-n$, $r=n$.

 

Prob. B

$k$를 2진법으로 나타냈을 때 켜진 비트에 대해서 $n$의 거듭제곱을 더한다.

 

Prob. C

답은 $0$또는 $1$또는 $2$이다. $0$일 때를 $O(N)$에, $1$일 때를 $O(NlogN)$에 판별해준다.

 

Prob. D

$i$와 $j$는 $c$가 $imposter$일 때 다른 팀, $crewmate$일 때 같은 팀이다. $dfs$를 돌면서 컴포넌트 별로 묶어주고, 각 컴포넌트를 이분그래프로 만들었을 때 크기가 더 큰 쪽의 크기를 더한 것이 답이다.

 

Prob. E1

$ans = 6*4^{2^{k}-2}$. D를 풀고 있는데 E1의 솔브 수가 급격하게 올라가는 것을 목격했다. 그때는 이렇게 쉬운 줄 몰랐는데, 그냥 D를 중간에 끊고 E1을 시도했어야 했다. $k$의 범위가 작아서 $2^{k}$를 그냥 계산해줘도 되는데 그것도 모르고 페르마 소정리 들고 와서 뇌절했다.

 

Prob. F

E2는 내가 싫어하는 유형이라서 바로 F로 넘어왔다. 잘 생각해보면, $ideal$ 의 여부는 $s$와 $n$ 각각에 대해서 단조적이고 이 중 $s$에 대한 단조성을 이용한다. 자연수 $n$개의 구간 합이 $k$가 되지 않게 하는 자연수들의 합의 최소를 구하면 문제가 해결된다. 그런데, 이는 매우 간단하게 구할 수 있다. $1, 1, \cdots 1, 1, k+1, 1, 1, \cdots 1, 1, k+1, 1, 1, \cdots 1, 1$ 이런 식으로 만들면 된다.

솔직히 F 치고 풀이가 너무 쉽게 나와서 내가 틀렸을 거라는 확신을 강하게 가지고 제출을 했다. 식의 형태를 조금씩 바꿔가며 제출해도 계속 pretest 13 에서 막히길래 당연히 내 논리가 틀린 줄 알고 포기했다. 그런데 대회가 끝나고 보니 맞은 사람들 풀이가 나랑 거의 비슷했고, 다들 예외 처리를 열심히 하길래 $s==k$ 일 때 항상 "YES"가 출력되게끔 해줬더니 AC.. 진짜 노트북 뿌시고 싶었다. div. 2 F를 풀 절호의 기회였는데 또 내 손으로 날리고 말았다.

 

 

7문제 중 5문제가 수학이어서 다행히 살았다. 하지만 스코어보드를 따라가지 않고 D를 고집한 점, E1에서 범위를 유심히 보지 않고 시간을 낭비한 점, 그리고 단순한 예외 처리를 하지 않고 문제를 날려버린 점 등의 크고 작은 실수가 발목을 잡았다.