개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 선발고사 문제 치고는 꽤 쉽다. 하지만 구현이 만만치 않다... 예제 속 그림을 보면 중요한 관찰이 눈에 쉽게 보인다. 바로 두 경로는 수직 구간 혹은 수평 구간을 정확히 하나 공유한다는 것이다. 이를 바탕으로 수평에 대해서 한 번 풀어주고, 수직에 대해서 같은 방식으로 한 번 풀어준다고 생각하고 한쪽만 고려해보자. 수직 구간을 공유한다면 수직 구간의 양 끝점을 기준으로 경로가 정확히 나뉜다. 이를 구간합 배열을 잘 이용하여 합쳐주면 된다. 솔직히 좋은 문제는 아니라고 생각한다... #include #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define siz(x) int((x).si..

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 한 자릿수 서브태스크 배점들을 보고 왜 이렇게 짜게 주나 했는데, 하나씩 풀다 보니까 기가 막힌 점수 배분인 것 같다. 부분 문제 1 ~ 4 풀이는 노드의 번호를 1-base 기준으로 작성했고, 부분 문제 5 풀이는 0-base 기준으로 작성했습니다. 궁금하신 점은 댓글로 남겨주시면 답변해 드리겠습니다! 문제 요약 "모든 $[i,j]$꼴의 정점 집합에 대해 만들어진 각 virtual tree의 가중치의 합을 구하라." 정도이다. 부분 문제 1 (5점) $N\le 300$이다. $O(N^3)$이 넉넉하게 돌아갈 수준이다. 모든 $[i,j]$를 직접 돌면서 dfs를 돌리면 된다. 웬만해서는 코드를 짜보려고 했는데, 점수 대비 구현량의 가성..

문제가 요구하는 바가 상당히 단순하다. 자력으로 푼 어려운 테크닉이 없는 첫 다이아 4 문제이다! Ob.1 ) 리프 노드는 노끈의 시작점이다. Ob.2 ) $($간선 수 - $\sum_v \left \lfloor \frac {\deg(v)}2 \right \rfloor)$가 최소 노끈 개수이다. 각 노드에서 어떻게 연결되는지를 주목하면 알 수 있는 부분. 사용할 노끈의 개수가 고정되었으니, 최소 노끈 길이만 구해주면 된다. 각 서브트리에서 어떤 노끈을 부모 노드에서 더 고려할지 같은 것들을 정해주기 위해 트리 DP를 하면 된다. 근데 이 부분을 그냥 풀 수는 없다는 것을 알 수 있고, 최대 노끈 길이를 파라메트릭 서치를 통해 고정하고서 결정 문제를 풀면 된다. 자식 노드들을 매번 정렬해주면서 풀어야 하므..

문제 링크 문제 요약 prefix와 suffix를 잡는데, prefix length + suffix length s) return true; Mp = max(Mp,p[i]); } return false; } int main() ..

문제 링크 적당히 타격감있는 기댓값 DP 문제다. divide by zero 예외를 놓치면 틀릴 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define all(x) begin(x), end(x) #define siz(x) int((x).size()) #define Mup(x,y) x = max(x,y) #define mup(x,y) x = min(x,y) #define fi first #define se second #define dbg(...) fprintf(stderr,__VA_ARGS__) using ld = lon..

문제 링크 백설공주와 난쟁이와 비슷한 것도 같다. 물론 안 풀어봤다. 아무튼 이 문제는 랜덤 알고리즘으로 푸는 문제이다. 처음 접하는 컨셉이라 신선하고 좋다. 문제 요약 길이 $N$의 정수 sequence $A$가 주어진다. 이 때 $A$의 각 원소는 distinct하다. 자연수 $M\in [3,10^9]$을 골라 모든 $A_i$에 대해 $\mathrm{mod\ } M$을 취해줬을 때, $A$의 majority가 존재하게 하는 $M$을 찾아라. 제한 $1\le N\le 5\ 000$ $1\le A_i\le 10^9$ 문제 풀이 Monte Carlo algorithm은 적당한 시간 내에 동작하지만, 확률적으로 정답을 구하지 못할 수 있는 알고리즘을 말한다. 시간이 충분히 빠르다면 여러 번 수행함으로서 정답..

문제 링크 으... 어려워... 여태 풀었던 앳코더 문제들 중에 레이팅이 kenkooo 기준으로 제일 높다. (거의 꽉 찬 옐로우) 내가 보기에는 다이아도 줄 만한 것 같다. 발상이 너무 어렵다... 짜증나는 점이 하나 있는데, ABC 공식 풀이가 뭐가 많이 부족하다는 것이다. 잘못된 점도 많고 설명도 친절하지 않다. 문제 요약 웹 페이지에 웹 카운터는 접속 횟수를 측정한다. $i=0,1,2,\ldots,23$에 대해서, 매일 $i$시마다 다음의 접속 가능성이 존재한다. 만약 $c_i=$'T'라면 철수는 $X$%의 확률로 웹 페이지에 접속한다. 만약 $c_i=$'A'라면 영희는 $Y$%의 확률로 웹 페이지에 접속한다. $N$번째 접속이 영희에 의한 것일 확률을 $\mathrm{mod }\ 99824435..

문제 링크 Suffix array를 이용하여 "문자열 $S$의 회전 $\le$ 문자열 $T$의 회전"을 만족하는 쌍의 개수를 세는 문제이다. (단, $N=|S|=|T|$) 회전(rotate)을 관리할 때는 원래 문자열을 두 번 연속해서 붙여주는 것이 경험적으로 유용하다. 왜냐하면 붙여 만든 새 문자열의 길이가 $N$인 각 부분 문자열들이 원래 문자열의 회전이기 때문이다. 붙여서 관리하겠다는 것까지는 알겠다. 이제는 효율적으로 $S$의 회전들과 $T$의 회전들을 비교해야 한다. $S$의 회전마다 $T$의 SA에다가 이진 탐색으로 패턴 매칭을 시켜주는 것은 어떨까? 괜찮은 생각이지만 아직은 제한에 못 미친다. $S$와 $T$를 전부 때려넣고 SA를 돌릴 수는 없을까? 이게 핵심이다. $\color {red}..