A에서는 디버깅에, B에서는 코딩에 시간을 쓰는 바람에 C를 대회 중에 해결하지 못해 아쉽습니다. 하지만 991등으로 마무리하여 티셔츠는 받게 되었습니다. 대회를 잘 봤는지와 무관하게, C번 문제가 꽤 흥미로워서 풀이를 남겨 놓고자 합니다. 우선, 문제 상황은 다음과 같습니다. 정점이 $N$개인 트리가 주어집니다. 각 정점 $v$에는 $M_v$개의 문자열이 주어집니다. 트리를 여러 개의 경로로 분할하되, 각 경로에 문자열 $s$가 포함되게 할 수 있다면 $s$는 mutually-learned 합니다. mutually-learned 한 문자열의 개수를 세는 것이 문제입니다. 모든 TC에 대해 $N$의 합은 $3\cdot 10^6$을 넘지 않습니다. 모든 TC에 대해 $\sum M_v$의 합은 $8\cdot..

별점 : 추천, [★★★☆★] 한국어 지문 : 링크, 번역이 구립니다 문제 요약 $n$-비트 정수 집합을 관리하는 자료구조가 있습니다. ($64$-비트 정수, $32$-비트 정수랑 같은 맥락이고 역시 $n$은 $2$의 거듭제곱) 이 자료구조에 일련의 정수 삽입 후, 컴파일을 거친 뒤, 일련의 정수 조회를 할 수 있습니다. 이때 컴파일 과정에서 버그가 발생합니다. 버그는 $n$ 비트의 순서가 어떤 순열에 따라 치환되는 형식으로 나타납니다. 정수 삽입을 $w$(write)번 이내, 정수 조회를 $r$(read)번 이내로 하여 버그가 갖는 순열을 알아내세요. 부분문제 1 (20점) 문제를 제대로 이해했는지 확인하는 부분문제입니다. 다음의 $8$개 정수를 삽입하면 최대 두 곳의 순열이 뒤바뀐 위치에서 비트 $1..

이 문제는 IOI 2022의 예비 문제로 출제된 문제이기 때문에, 백준 외에 이 문제의 채점을 지원하는 사이트를 찾지 못했습니다. 백준에서 채점 방식을 수정하여 올린 투스텝 문제의 특성상, 이 문제는 10초의 시간제한과 함께 채점 우선순위가 2입니다. 따라서 채점 속도가 상당히 느리니 이 점 유의하시기 바랍니다. 번역 빠져도 이해에 무리가 없는 길고 형식적인 예제 설명과 그레이더 피드백 방식 설명은 생략하여 번역했습니다. 문제의 핵심 $X = 1,2,\ldots,n$에서 크기 $k$의 조합 $Y = 1,2,\ldots,n$에서 크기 $k-1$의 순열 일 때, $X\overset f \to Y$인 $f$를 조건에 맞게 잘 구성하라는 문제입니다. 조건은 $f(x)=y$일 때, $y$가 $x$의 $k$개 원소..

요약 겹치지 않는 구간 $N$개가 주어집니다. 각 구간을 $K$만큼 연장하여 구간 사이사이에 빈틈이 없도록 메꾸고 싶습니다. 그런 $K$를 연속된 구간의 범위을 줄 때마다 찾아서 답하는 문제입니다. 풀이 부분문제 1은 별 의미가 없고, 부분문제 2는 파라매트릭 서치를 하면서 확장영역을 그리디하게 뒷쪽으로 몰아주는 전형적인 방법으로 풀면 됩니다. 이때, 그리디하게 확장영역을 몰아주는 아이디어를 기억해 둡시다. 전체 문제를 풀어봅시다. $N$이 $3\,000$으로 굉장히 작기 때문에 $O(N^2)$ 전처리를 해두고 매 쿼리에 $O(1)$으로 답하는 것이 가능합니다. ...이제 그 방법을 고민해 봅시다! 관찰 1. 구간 두 개를 두고 간격이 $2K$ 넘게 벌어지면 이 $K$는 불가능하다. 당연히 관찰할 수 있..

개인적으로 백준에서 보는 것보다 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를 하면 된다. 근데 이 부분을 그냥 풀 수는 없다는 것을 알 수 있고, 최대 노끈 길이를 파라메트릭 서치를 통해 고정하고서 결정 문제를 풀면 된다. 자식 노드들을 매번 정렬해주면서 풀어야 하므..