링크 문제를 요약하겠습니다. 사분원 둘레 $n$개가 주어집니다. 이들을 잘 돌리고 조합하여 하나의 폐회로를 완성해야 합니다. 단, 두 개의 사분원 둘레가 만나는 부분은 부드럽게 이어져야 합니다. $4\le n\le 100;$ $1\le r\le 10\,000$ Yes / No로 답해주세요. 접근 1 naïve한 여러 방법들이 떠오릅니다 방향 고정 등으로 중복을 획기적으로 줄일 수 있을까요? → 그다지.. DP가 계속 맴도는데.. 좌우상하 DP로 점화식을 세워 볼까요? → 역시나 역부족.. 필요한 알짜 x, 알짜 y를 상태에 포함? → 결국 좀 애매합니다.. 이동 범위를 확인할 수 있을까요? → 딱히 연속적이지 않아서 무의미해 보입니다.. 다만.. 45도로 돌려볼 수 있을까요? → x,y를 복합적으로 고려..

문제 굉장히 재미있다. 예상 난이도는 플래티넘 2 정도? 고민에서 코딩까지 2시간 걸렸는데.. 이거 괜찮나 ㅋㅋ 풀이 더보기 기본적인 사항들 관찰 1. 많아야 $R$번의 청소를 한다. 관찰 2. 청소 경로가 차곡차곡 쌓이는 형태이다. 정확히는, 청소 경로 두 개가 교차할 경우, exchange argument에 의해 꼬인 걸 푸는 게 최적 따라서 청소 경로가 '껍데기처럼 벗겨낼 수 있다' 정도의 이야기 구현 어케하지.. 생각 1. 수직선을 긋고, 만나는 부분들은 이번에 갖고 가고, 만나지 않는 부분들은 최대한 어케 땡겨서 재귀적으로......?? 생각 2. 이렇게 밑도 끝도 없이 구현이 막막해진다면 뭔가 단순한 형태로의 변환을 도모해야 한다. 생각 3. 격자다. 격자에서 체비셰프 좌표계가 떠오르는 이동들..

굉장히 재밌는 문제입니다. 부분문제 1 ~ 4 부분문제 1 : $C-B$를 반환하면 됩니다. 부분문제 2~4 : 그래프로 모델링하여 해결할 수 있습니다. 인접한 두 방향의 이동을 스택을 이용해 표현할 수 있고, 이로써 그래프를 만들어 둘 수 있습니다. 쿼리마다 multisoure BFS를 해주면 쉽게 답을 구할 수 있습니다. 부분문제 5 다시 표현하면 $[B,B]$에서 $[C,C]$로 가는 최단 경로를 찾거나, 도달 불가능함을 판별하는 문제입니다. $[A,B]$와 $[C,D]$에 대한 문제의 약한 버전이어서, 확실히 해결하면 정해로 직결될 법한 느낌이 나는 부분문제입니다. 관찰 1. $H_B < H_C$는 '도달 가능'의 필요조건입니다. 높이는 이동하는 과정에서 항상 엄격하게 높아지기 때문입니다. 관찰 ..

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$는 불가능하다. 당연히 관찰할 수 있..