본문 바로가기

Competitive Programming/Codeforces

Educational Codeforces Round 116 (Div. 2)

 

Dashboard - Educational Codeforces Round 116 (Rated for Div. 2) - Codeforces

 

codeforces.com

 

 

3주 만의 코포 복귀  &  3달 만의 퍼플 복귀  &  10달 만의 +100 이건 아니었다

 

시간이 맞지 않아 3주 동안이나 코포를 못하고 있었고 이날도 분명 힘들거라 생각했었다. 그런데 버스 기사님이 무리를 하셨는지, 도착 예정 시간이 아슬아슬하게 들어와서 지하철 안에서 노트북 세팅을 끝내 놓고 집으로 뛰어들어왔다. 이때가 대충 33분. 손만 대충 씻고 코포에 빠르게 접속하니 대회가 바로 시작... 그래서 외출 상태 그대로 코포를 쳤고, 결과는 성공적이었다.

 

Prob. A

ab, ba의 개수는 a, b 묶음이 몇 번 변하는지에 영향을 받는데, 대충 3번째 예제를 보면 끝부분만 맞춰주면 된다는 것을 알 수 있다.

 

Prob. B

풀이는 자명한데 적절한 컷팅이 필요하다. 이걸 못해서 2틀..

 

Prob. C

이왜맞? 풀이가 생각이 안 나서 일단 예제를 따라하는 코드를 짰는데 맞았다.

 

Prob. D

남은 한 시간동안 $O(NMlogN)$ 시뮬레이션을 짰는데 WA on 2.

 

Prob. E

$dp[n][x]$ 를 combination과 fast_pow를 이용해 $O(NlogX)$ 에 구할 수 있으니 전체 dp를 $O(N^2XlogX)$에 계산할 수 있다.