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

오늘 티어 많이 올린듯 후후 JOI 국가의 행사 문제 링크 3가지 풀이가 존재한다고 한다. 참고 풀이 더보기 멀티소스 다익스트라로 전처리를 해준다. 각 노드 $v$에 대해 구한 최단거리를 $\text{value}[v]$라고 하자. 문제가 $\displaystyle \min _{\text{v}\in \text{경로}} \text{value}[v]$ 쿼리를 푸는 문제로 단순화된다. $\text{value}[v]$의 크기에 따른 크루스칼 변형을 떠올릴 수 있다. 그렇게 구성되는 스패닝 트리 위의 간선을 타는 경로가 최적이다. 따라서 구성된 스패닝 트리로 sparse table을 구성한다. 쿼리를 sparse table로 처리한다. 코드 더보기 구현이 워낙 길어져서, 모듈화시켜서 풀었다. 덕분에 디버깅 없이 1..

냠 굉장한 학생 문제 링크 풀이 더보기 각 학생은 $(a,b,c)$값을 지닌다. 만약 모든 다른 $(a',b',c')$에 대해 $a'>a,\ b'>b,\ c'>c$가 만족한다면 굉장하다. 따라서 $(a,b,c)$를 $a$에 대한 오름차순으로 정렬한 뒤, $\text{RMQ}$ 세그트리에서 $b$번 인덱스에 $c$를 넣는 식으로 관리하면 문제를 풀 수 있다. List of Unique Numbers 문제 링크 $\text{last_pos}[x]$를 관리하면서 풀면 된다. 정사각형 만들기 문제 링크 정확한 내용을 모르겠어서 디코에 질문 올렸다. 풀이 더보기 코드 더보기 #include using namespace std; #define rep(i,a,b) for (auto i=(a); i> n >> m; i..

냠 수열과 쿼리 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

오늘 기분이 좀 안 좋았었는데 문제가 잘 풀려서 싹 나았다. +) 32일 스트릭 뱃지 달성 +) 세그트리 태그 티어 플래5 달성 냅색문제 문제 링크 기억에, 옛날에 못 풀고 끙끙댔던 것 같은데 오늘 풀어보니까 풀이가 바로 떠올랐고, 구현도 쉬웠다. 풀이 더보기 $N\le 30$이니까 meet in the middle을 써야 한다는 것이 보일 수 밖에 없다. $\lfloor N/2\rfloor$랑 $N-\lfloor N/2\rfloor$개로 각각 나눠서 모든 경우를 나열한 뒤에 이진 탐색으로 하나씩 확인해주면 된다. 구현도 간단해서 코드는 생략한다. 데이터 만들기 1 문제 링크 APIO 2013 기출이다. 최단경로를 입문하는 사람한테 반례에 대한 사고력을 높여줄 만한 문제들인 것 같다. 풀이. 더보기 간단..

공항 문제 링크 각 비행기를 도착하는 순서대로 남은 조건을 만족하는 게이트에 도킹시키는 문제이다. 물론 도킹 수가 최대가 되는 것이 목적이다. 풀이 더보기 게이트의 선택지는 $1\cdots g_i$이다. $g_i$가 큰 비행기들은 굳이 작은 게이트를 택함으로써 $g_i$가 작은 비행기들의 자리를 뺏을 이유가 없다. 따라서 $g_i$ 이하 중 가장 큰 게이트를 택하는 그리디 전략이 성립할 수 있다. 근데... 증명은... 어케하지..? Overplanting 문제 링크 jinhan814님 코드가 깔끔하길래 본계정으로 다시 풀었다. 풀이. 더보기 직사각형의 합집합의 넓이를 구하는 유형인데, $N$이 작다. 그냥 좌표압축 느낌으로 풀이하면 되는데, 구현이 중요하다. 코드 더보기 query, update을 밖으..

LCM 문제 링크 개인적으로 오랫동안 고민했던 문제이다. 거의 4번? 정도에 거쳐서 풀다 미뤘다를 반복했다. 풀이 더보기 $\mathrm{lcm}(x,y)=xy/\gcd(x,y)$인데, 분모가 유동적이니까 $\gcd(x,y)$를 결정했을 때 $xy$의 최솟값을 각각 구해주는 방식으로 접근하면 된다. 손으로는 자연스러운 접근인데, 이상하게 코드로 짤 생각을 못했다. $\gcd(a+n,b+n)|(b-a)(\mathrm{wlog}\ a\le b)$이라는 사실을 이용해 $b-a$의 약수들만 훑어주면 된다. 코드 더보기 $x|(b-a)$ 검사를 빼먹었는데 예제가 돌아가서 눈치를 못 채고 있었다. 그리고 $a=b$인 경우도 빼먹고 있었다. 점점 실력이 떨어지는 느낌이다 ㅋㅋㅋ 이런건 좀 그만 실수해!! #inclu..

살짝 호들갑이기는 한데, 어쨌든 블루를 달성했다. 며칠 '블루 가자!!' 이러면서 치는데 계속 못 가다가 간발의 차로 블루에 들어와서 더 기분이 좋았던 것 같다. 아무튼 목표는 퍼플이므로 다시 담담하게 버추얼을 돌리면서 레이팅을 올려야 한다. 그래서 대충 계획 같은 걸 세웠다: Codeforces Anytime 기준 1700을 달성한 뒤 코드포스 복귀하자. Upsolving 리스트 풀기, 26문제다. 대부분 Div.2 D 난이도, 1900~2000이다. = 대충 플4 난이도. 플4 많이 풀자! 완전 다른 얘기긴 한데 코포 찾다가 이 문제를 내가 리스트로 깔끔하게 풀었는데, 꼭 리스트여야 하는지, 그렇다면 왜? 혹은 다른 방법? 등을 정리해보자. interactive 문제에 익숙해지자.