CP diary/AtCoder (3) 썸네일형 리스트형 AtCoder Educational DP Contest J - Sushi 분석 https://atcoder.jp/contests/dp/tasks/dp_j J - Sushi AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 앳코더에는 Educational DP Contest라고 PS에서 자주 출몰하는 26가지 유형을 정리한 DP 문제집이 제공되고 있다. 그중에서도 J는 기댓값을 다루는데 어떻게 푸는지 본인의 시행착오를 덧붙여 분석하고자 한다. 먼저 삼소멤 블로그에서는 다음과 같이 설명하고 있다. 다 좋은데 기댓값이 $\frac{N - (i + j + k)}{i + j + k}$ 라고 한다. 하지만 기하.. AtCoder Regular Contest 137 (ARC 137) 후기 소수 정리의 존재를 알 수 있었던 아마도 유익한 콘테스트였다. AtCoder Beginner Contest 243 (ABC 243) 후기 성적 1827등으로 조금 아쉬운 성적이다. C에서 구현 실수가 있었고 D에서는 무지성으로 제출을 해서 도합 10분의 페널티를 받았는데 두 페널티가 없었다면 레이팅이 올랐을 것이다. 아는 선에서 설명하는 해설 A: ABC A치고 조금 당황스러운 문제긴 했는데 샴푸가 바닥날 때까지 러시안룰렛을 돌리면 된다. B: 시키는 대로 naive하게 하면 $O(N^{2})$의 시간 복잡도로 정답을 받을 수 있다. C: 오른쪽으로 이동하는 좌표, 왼쪽으로 이동하는 좌표를 따로 관리한다. 단순한 구현을 위해 map 을 사용했는데 각 좌표에 대해 lower_bound로 반대방향으로 이동하는 점과 충돌하는지 검사하면 된다. D: 일종의 오프라인 쿼리로 볼 수 있다. 주어진 스트링에 대해 온라인으로 계산하지 말고 깊이의 변화,.. 이전 1 다음
