대회 알림이 6개나 올라와 있길래 할 만한 게 뭐가 있을지 찾아보다가 SNUPC OC Div.2 작년 결과를 보니 대회 우승/준우승 컷이 꽤 낮아서 우승/준우승을 목표로 잡고 참가했다. 대회가 끝났는데 아직 프리즈 이후 상황이 안 나와서 2등 아니면 3등인데 높은 확률로 3등이다. 아쉬운 점은 대회에 늦게 들어온 것과 C 코드를 다 짜고 실수 몇 개 고치다가 노트북 배터리가 부족해서 카페에서 집까지 뛰어서 충전기를 가져오느라 제출이 늦어진 점이다. 또, E에서 해서는 안되는 실수를 했던 점이 아쉽다. 양방향이여서 SPFA가 아니라 dfs 한 번으로 체크하고서 다익스트라를 돌리면 되는 거였는데 착각하고 인터넷에 있는 SPFA 코드를 찾아다가 넣고서 두 번이나 틀렸다. 대회 링크 질문은 언제나 환영입니다. ..

어제 저녁에 고층 빌딩을 열어서 읽다가 잠들었다. 그래서 일어나자마자 풀고 풀이를 적었다. 글 [BOJ 1328] 고층 빌딩 요즘 학교 OJ에다가 USACO 문제들을 번역해서 하나 둘씩 올리고 있다. 어제는 해커컵 예선 A번 번역한 거에다가 TC를 추가하고 정답 코드를 재채점 돌렸다. 그런데 웬걸, 서버가 터졌다. 아침에 일어나니 다시 잘 돌아가고 있길래 재채점을 다시 돌렸다. 웬걸, 다시 터졌다. 호스팅 업체의 문제인지, OJ의 문제인지 뭔지 모르겠다. 고작 코드 2개 재채점 돌리는데 터지다니... 그래서 Mountain Climbing을 오늘 올리려고 했는데 아직도 못 올리고 있다. P2 짜리를 하나 풀었는데... 구현만 몇 시간 걸린 것 같다. 힘들다... 아무래도 깔끔하게 다시 풀어볼 필요가 있다..

멀티탭 스케줄링 문제 링크 그리디 연습 겸 풀어봤다. 풀이 더보기 전기용품을 사용하려 할 때 다음의 두 가지 선택이 있다: 이미 플러그가 꽂혀 있어서 그대로 사용한다 기존의 플러그 중 하나를 뽑고 새 플러그를 꽂아 사용한다. 2번에서 어떤 플러그를 뽑을지 선택하는 것이 관건이다. 나중에 제일 적게 등장할 플러그를 뽑을 것인가? 아니다. 가장 나중에 등장할 플러그를 뽑을 것인가? 맞는 것 같다. 이는 가장 나중에 등장하지 않는 플러그를 뽑았다고 가정했을 때, 이 보다 가장 나중에 등장하는 플러그를 뽑는 것이 항상 유리하거나 같다는 발상을 통해 확인할 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i..

문제 링크 플4치고 쉬운? 문제 풀이 더보기 2 3→2 4→3→2 5→2 6→4→3→2 7→2 8→3→2 9→2 10→3→2 주어진 수를 나누지 않는 최솟값 → 어떤 수보다 미만의 모든 수가 주어진 수를 나누게 하는 최솟값 따라서 $$|\{k|(2\nmid k)\}|\times (strength(2)+1)\\+\\ |\{k|(2\mid k)\wedge(3\nmid k)\}|\times (strength(3)+1)\\+\\ |\{k|(2\mid k)\wedge (3\mid k)\wedge (4\nmid k)\}|\times (strength(4)+1)\\+\\ \vdots$$ 를 구해주면 된다. $\mathrm{lcm}$ 단위로 커지기 때문에, 전처리할 $strength(k)$의 종류가 그리 많지 않다는 ..

문제 링크 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: $N ≤ 3\ 000, Q ≤ 3\ 000$ (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 $ ≤ 10^5, Z_j =0$ (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자료구조들이 있을 것이다. 그렇게 다음의 3가지 풀이가 있다: Merge sort tr..

문제 링크재밌는 트리 DP 문제였다.편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자.Subtask: $V_i > 0$ (17점)더보기그냥 최대한 많이 포함하면 이득이다.그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다.또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다.필자의 코드이다.Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점)더보기직선형 그래프에서 문제를 풀면 된다.Kadane 알고리즘과 꽤 비슷하다.각 노드 $i$마다 $\sum_{i\le k\le j}V_k$가 최대가 되게 하..

냐 K번째 수 문제 링크 냐 풀이 더보기 사실 루트질 연습하려고 담아둔 문제인데, 그냥 세그트리로 풀었다. 이게 머지 소트 트리 맞나? 아무튼 각 노드가 구간을 커버하는 배열의 정렬된 상태를 담는데... 이렇게 하면 쿼리를 $\mathcal O(\log n)$개의 구간에 대해 각각 $\mathcal O(\log n)$의 이진 탐색을 진행하여서 총 $\mathcal O(\log^2 n)$에 응답할 수 있게 된다. ヘビの JOI 君 문제 링크 풀이 쓰기 좀 귀찮네... 생각을 풀어서 쓰려니 귀찮다. 참고로 이 문제 기여에 나는 #Case_work를 넣었다. 깔끔하게 분류 안 하면 자꾸 꼬이는 듯. 풀이 더보기 물론 다익스트라다. 뭐 다른게 나올 일도 없지 않은가... 그 상태에서 뭘 어떻게 해야되냐가 문제인..

냠 수열과 쿼리 1 문제 링크 풀이 더보기 펜윅트리에서 각각이 구간을 정렬한 상태로 갖게 하면 된다. 거기에 이진탐색. 플3 날먹..!! AtCoder Beginner Contest 250 대회 링크 거의 한 5개월 만의 앳코더다. 그동안 코포 연습한게 있어서 민트 퍼포는 나오더라. Adjacent Squares 걍 Enlarged Checker Board 걍 Adjacent Swaps 걍 250-like Number $p\times q^3\le 10^{18}$ $p^4