본문 바로가기

전체 글

 (35)
2024 KAIST 14th ICPC Mock Competition 문제 출제 후기 조금 늦었지만 이번 카이스트 가을대회에 출제한 문제들의 비하인드를 이야기해보자 한다. 1. Same segment원래 골드 문제를 위한 문제였다. 가볍게 풀 수 있는 문제를 생각하기 위해서 익숙한 토픽들을 여러 개 훑는 중에 "주어진 구간 몇 개의 합이 자연수 K로 같은 음이 아닌 정수의 수열"이라는 토픽이 떠올랐다. 포함관계에 있는 구간이 없으면 그리디하게 앞에서부터 K/0을 채우면 되고, 포함관계에 있는 구간이 존재한다면 두 구간의 차집합에 0을 채우면 되는 아주 쉬운 문제였다. K가 답에 영향을 미치지 않는다는 아이디어도 괜찮아서 다항시간 풀이를 떠올리면 문제를 풀 수 있도록 N 이 문제를 발전시키기 위해 포함관계에 있는 두 구간의 차집합에 0을 채우는 과정을 더 빠르게 할 수 없을까 생각했지만, ..
색종이 붙이기 문제 링크 1. $N, M \leq 400$ 모든 칸을 다 덮을 수 있는 색종이의 집합을 $S$라고 하자. 각 $w$에 대해서 $(w, h) \in S$인 $h$의 범위는 $h \leq f(w)$의 형태로 나타난다. 이때 $f(w)$는 $w$에 대한 감소 함수이다. 따라서 $(w, h) \in S$를 판별하는 결정 문제를 $O(N+M)$번 해결해주면 해당 문제를 해결할 수 있다. 이 문제는 prefix sum을 이용해서 $O(NM)$에 쉽게 해결할 수 있다. 2. Maximal rectangle에 대하여 Maximal 직사각형이란, 내부에는 칠해진 칸이 없고 해당 직사각형을 포함하는 직사각형은 내부에 칠해진 칸이 있는 직사각형을 의미한다. 다시 말하면 직사각형의 각 변의 테두리에 칠해진 칸이 있는 직사각..
2024 KAIST 14th ICPC Mock Competition 풀이 A. Automata Embedding더보기1. $f(i+1) \leq f(i)+1$이는 kmp failure function의 특징 중 하나이다. $S[1...f(i+1)] = S[i+1-f(i+1)+1...i+1]$이라면 $S[1 ... f(i+1)-1] = S[i+1-f(i+1)+1 ... i]$이기 때문이다. 2. $f(i)$와 $i$를 잇는 화살표들을 평면 위에 그릴 수 있다는 것과 동치인 것은, 구간 $[f(i), i]$들을 정점으로 하고 두 구간이 겹치지만 포함관계에 없는 경우 간선으로 이은 그래프가 이분그래프인 것이다.pf) 각 화살표를 위에 그리면 그룹 1, 아래에 그리면 그룹 2라고 하자. 같은 그룹에 있는 화살표들은 겹치면 안 되고, 이는 구간으로 만들어진 그래프에서 두 구간이 겹치지..
[IOI 2024] Hieroglyphs 문제 링크: https://www.acmicpc.net/problem/32267 제곱 미만 LCS가 나오는 레전드 문제이다. 문제를 읽고 적지 않은 충격을 받았을 불쌍한 국가대표들... 0. 기본적인 관찰문자열 $S$ 안에 있는 문자 $x$의 개수를 $count(S, x)$로 정의하자. UCS가 존재한다면 UCS 내부에 들어간 문자 $x$의 개수는 $min(count(A, x), count(B, x))$이다.  $count(A, x) \leq count(B, x)$라면 $x$를 $A$의 문자, 아닌 경우에는 $x$를 $B$의 문자라고 하자. 앞으로 편의상 universal common sequence를 ucs, common sequence를 cs라고 부르자.1. Subtask 2의 일부$count(A, ..
아인타, 빈타, 그리고 씬타 문제 링크: https://www.acmicpc.net/problem/32037 구사과님의 problem solving에 있는 문제이다. 안타깝게도 나와 구사과님을 제외하고 1명 밖에 안 풀었다. 1. Graph construction $S$를 sink, $T$를 source라고 했을 때 다음과 같이 그래프를 만들어보자. 모든 간선의 capacity는 1이다. 모든 $1 \leq i \leq n$에 대해 $S \rightarrow (i, 0)$모든 $1 \leq i \leq n$에 대해서 $(i, 0) \rightarrow (A[i], 1)$, $(i, 0) \rightarrow (B[i], 1)$모든 $1 \leq i \leq 10000$에 대해서 $(i, 1) \rightarrow (i, 2)$모든 ..
$\prod_{i=1}^N(R_i-L_i+1)$개의 트리 출제 후기 이번에는 UCPC에 문제를 성공적으로 출제했다. 문제가 만들어진 과정을 알아보자. 문제 출제처음에는 쉬운 플래티넘 문제를 만드려고 했다. 플래티넘 문제는 대회중에 많은 사람들이 풀고, 대회가 끝나고도 많은 사람들이 풀어서 좋다. 세팅하기도 쉽고, (기하 문제나 실수 문제를 내지 않는 이상) 검수하기도 쉽다. 단점은 대회의 승패를 가르는 문제가 아니라는 것과, 나중에 문제를 돌아봤을 때 문제 출제에 대한 뿌듯함이 줄어든다는 것이다. 하지만 나는 문제를 만들 당시에 2개의 어려운 문제가 있었기 때문에 무난한 문제를 만들고 싶었다. (2문제는 런 봄대회에 출제되었다) 처음에 생각한 문제는 LFIS 와 같이 exponential하게 증가하는 조건을 주고 특정 수열의 길이가 logN 이하라는 성질을 이용해서 푸는..
재미있는 문제란 뭘까 (P5-P2) 보호되어 있는 글입니다.
USACO 2024 January Contest (Gold Division) 백준 링크: https://www.acmicpc.net/category/1023 1. Walking in Manhattan 1. 두 직선의 교점에서 오른쪽으로 가고 있다고 가정하자. 방향을 위로 바꾸는 경우는 시작한 교점의 x좌표와 홀짝성이 다른 가장 가까운 y축에 평행한 직선을 만나는 것이다. 위로 가고 있을 때에도 방향을 바꾸는 경우가 마찬가지이다. 따라서 x축과 평행한 각 직선에서 그 다음에 어떠한 직선을 탈지 구할 수 있다. 2. $i$번째 직선의 다음 직선을 $f(i)$라고 하자. y축과 평행한 i번 직선, x축과 평행한 j번 직선의 교점을 $(i, j)$로 표현하자. $(i, j)$에서 움직이다보면 $(f^k(i), f^k(j))$로 이동하게 된다. sparse table을 사용해 $f^k(i..

티스토리툴바