PS (5) 썸네일형 리스트형 /<30326> Heap Structure - TOPC 2023 주간이 아닌 회고록에 쓰던 문제들을 문제 단위로 나눠서 올리게 될거 같습니다. 이유는 몰아서 쓰다 보니 좀 힘든 감도 있었고. 짧게라도 자주 쓰는 습관을 들이고 싶은거도 있고. 분량이 너무 긴가? 에 대한 스트레스도 안 받아도 되고. 팀 연습 하다가 만난 문제인데 셋에서 업솔빙 한 문제중 유일하게 마음에 드는 문제였네요. $k$번째로 작은 값이 들어 갈 수 있는 정점에 대해 두가지 성질을 관찰 해야 합니다. 편의를 위해 모든 값이 unique하다고 가정합시다.루트의 깊이를 $1$이라 했을 때, 깊이가 $k$이하여야 한다. (어떤 정점의 조상들에 속한 값은 전부 그 정점에 속한 값보다 작아야 하기 때문)그 정점을 루트로 하는 서브트리의 크기를 $s$라 했을때 $s - 1 \le n - k$를 만족해야 한다.. 딱히 주간은 아닌 회고록 많이 밀려버렸지만 그래도 공부를 위해 그동안 풀었던 문제들 중 인상 깊었던 문제들 위주로 정리를 해보려 합니다. / + / 팀연습 / 팀연습 더여러 조건이 복합적으로 엮여 있는 상태 전이를 다루는 DP 문제입니다. 모든 경우의 수를 한번에 고려한 하나의 점화식을 바로 만들기는 어려워 보이니 문제에 주어진 조건을 최대한 많이 상태 공간으로 옮겨서 점화식의 상태 전이를 단순하게 해봅시다. 저는 다음과 같이 나눴습니다. $ A_{i, true/false, m} = A$가 $($ $i$ 번째 문제를, $C$가 문제를 풀거나/안 풀은 상태에서, $m = A$가 푼 문제수$\mod K$ $)$ 일때, 푸는 경우의 수.$B$, $C$도 비슷하게 정의 가능합니다. 이렇게 하면 초항과 상태 전이 또한 다음과 같이 정의 .. 2023.04.20 주간 회고록 뜬금 없지만 갑자기 다시 PS에 대한 욕심이 생겼습니다. ICPC WF진행하는거 보니까 뭔가 다시 한번 제대로 해볼까 하는 생각도 들더라고요. 이 글에서는 이번 한 주 동안 풀었던 문제들을 정리하려고 합니다. 그 전에 최근에 세운 몇가지 목표들을 정리하겠습니다. solved.ac class 1~7 all solve Codeforces Purple (1900) Atcoder Blue (1600) BOJ 2000 solve 사실 뭔가 최종 목표라기 보단 어떤 목적을 이루는 과정에서 중간 체크포인트 느낌으로 세운 도전 과제라고 보는게 맞긴 하겠습니다. 결국 최종적인 목표는 대회에서 좋은 성적을 거두는거고 다른건 다 그걸 이루기 위한 연습이죠. 마침 이번에 UCPC에 같이 나가게 될 팀원들도 다 실력이 너무 뛰.. 2023.06.24 골랜디 [A] 텔레포트 3 - boj 12908번 우선 두 점 (xi, yi) 와 (xj, yj) 사이 점프로 이동해서 걸리는 시간은 | xi - xj | + | yi - yj | 입니다. 이 점을 활용해 임의의 두점 사이 걸리는 시간을 O(1)에 계산할수 있습니다. 텔레포트의 갯수가 3개로 고정되어 있기 때문에 텔레포트를 타는 모든 6C3 개의 조합에 대해 답을 계산 해주면 대충 6!=720개 정도의 조합이 나오고 각 조합에 대한 경로를 O(1)시간에 구할수 있기 때문에 충분히 빠르게 답을 구할수 있습니다. 6C3 개의 조합을 전부 돌아보는 과정은 C++의 next_permutation함수를 이용해 쉽게 구현할수 있습니다. #include using namespace std; #define endl '\n' .. 2023.06.22 양갈래 골랜디 스터디 그룹 모 양갈래를 좋아하는 디코 서버에서 방학 기간동안 매일 3문제씩 골5,4 랜디를 하자! 라는 계획을 서버장이 추진하게 되어서 시작했습니다. 할때마다 블로그에 정리하려 하는데 매일 쓰다보면 풀이 퀄리티가 떨어지는 날도 있을수 있으니 더 궁금하면 댓글로 달아주세요. [A] 유닛 이동시키기 boj - 2194번 정직하게 2차원 격자에서의 BFS를 구현해주면 됩니다. 다만 주의할점은 격자를 벗어났는지 벗어나지 않았는지 판정할때 움직이는 점의 크기가 a x b 크기이기 때문에 경계를 계산할때 조금 조심해줘야 합니다. #include using namespace std; #define endl '\n' #define PRECISION 0 #define fr first #define sc second using ll.. 이전 1 다음
