PS 일지

11/21 ~ 11/30에 푼 문제들입니다.문제의 풀이가 포함되어있으니 유의하세요. 11/22BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)Platinum 4 #dfs #sweeping 깊이를 기준으로 스위핑을 하면 된다.$0 \le i \le j \le \log_2{N}$인 $i, j$에 대해, 깊이 $i$ 이상 $j$ 이하의 모든 점을 탐색하며 최대 연속합을 구하자.이 스위핑+탐색이 문제에서 요구하는 직사각형을 그려보는 것에 해당한다.연속합은 트리를 inorder 순서로 펴서 구해도 되는데, 본인은 금광 테크닉으로 구했다.BOJ 16877 - 핌버Platinum 3 #sprague_grundy 스프라그-그런디 정리로 해결하면 된다.m..

Codeforces Round 910 (Div. 2)에 참가했다.예상했던 것보다 훨씬 어려워서 놀랐다. 풀다가 벽에 막힌 느낌이 강하게 들었고, 문제도 얼마 풀지 못해서 처음으로 레이팅이 떨어질까 걱정했다. A - Milica and String00:05 AC 항상 1회 이하의 연산으로 가능하다.B의 개수를 세서 $k$보다 클 때, 같을 때, 작을 때로 분류해서 처리하면 된다. B - Milena and Admirer00:23 AC 어떤 수를 쪼갤 때, 어떻게 해야 최적인지의 여부는 뒤에 존재하는 수들에 따라 달라진다. 따라서, 뒤에서부터 본다는 접근은 자연스럽다.$a_i > a_{i+1}$인 $i$에 대해, $a_i$를 모두 $a_{i+1}$이하인 수들로 나눠야 한다.이 때 수행해야 하는 연산 횟..