CP diary (5) 썸네일형 리스트형 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}$ 라고 한다. 하지만 기하.. CLion PS용으로 설정하기(파일 입출력, 다중 main) ICPC에서도 공식적으로 지원하는 IDE인 CLion은 많은 부분이 편하지만 표준 입출력을 리눅스처럼 파일을 줄 수 없다던가 프로젝트 단위로 지원해서 파일 하나하나에 main 함수를 넣을 수 없다던가 하는 문제가 존재한다. 이 포스트에서는 적절한 설정을 통해 CLion을 PS 환경에서 쓰기 편하게 하는 법을 알아본다. 파일 입출력 에디터에서 빨간 동그라미에 해당하는 메뉴에 프로젝트 명 뒤 옵션이 Debug로 되어있는지 확인한다. 그렇지 눌러서 Debug로 바꿔주자. 그리고 Edit Configuration 메뉴에 들어간다. Working Directory에 입출력 파일이 들어갈 폴더를 지정한다. 이러면 프로젝트에서 외부 파일 IO를 할 수 있는 root directory가 설정된다. 그 다음 CMakeL.. 앳코더 민트 후기, 민트 가는 법 (앳코더 공부법) 1300 정도 되면 해당 색깔에 안착했다 판단하고 글을 쓰려고 했는데 대박이 터져서 지금 쓰게 되었다. 왜 써요? 인터넷에 검색하면 코드포스 블루 가는 법은 인기가 많은데 앳코더 민트 가는 법은 글 자체가 없어서 쓴다. 앳코더 민트도 충분히 가기 어렵다... 여기 통계에 따르면 앳코더 민트는 코드포스 블루와 동동하다고 여긴다. 그래서 앳코더를 널리 추천하고 싶기도 하고 나처럼 코드포스가 아니라 앳코더를 목표로 공부하는 사람들에게 도움이 되라는 뜻으로 부족하지만 글을 쓴다. 물론 코포 퍼플이나 앳코더 블루 이상이신 분들은 코웃음 치면서 넘기면 된다. 민트를 어떻게 달았는가? 사실 본인은 민트를 허무하게 찍었다. AtCoder Beginner Contest 258을 보면 등수가 418로 확 튄 것을 볼 수 .. 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 다음
