본문 바로가기

분류 전체보기

(38)
$\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..
One, Two, Three 출제 후기 2024년 1월 2일에 군대를 가게 되었다. 군대에 가게 되면 대학생이 아니게 되니 대학생 대회들에 멋진 문제를 내서 대학생들에게 풀리겠다는 생각으로 훈련소와 후반기 교육을 하면서 문제들을 만들게 되었다. One Two Three는 ainta님의 문제 스타일에 영향을 받은 문제이다. 신탁, 하나 둘 셋, 점 연결하기, comparing plants를 풀면서 인위적이지 않은 설정들에서 재미있는 관찰들을 추가하면서 문제를 풀어나가는 것이 재미있었다. 특히 신탁이라는 문제를 풀면서 하나의 시행을 다양하게 변환하면서 점점 문제를 풀어나가는 과정이 인상깊었다. 그래서 나도 ainta님처럼 간결한 문제를 만들고 싶었다. 점 연결하기, 돌 가져가기 문제들을 보면 길이 N의 수열을 주고 적당한 시행을 줘서 문제를 완성..
RUN 2024 Spring Contest 풀이(내가 출제한 문제들) E. Two Histograms0. 직사각형 ($[x_1, x_2] \times [y, y]$)의 시작칸은 $(x_1, y)$으로 정의한다.직사각형 ($[x_1, x_2] \times [y, y]$)의 끝칸은 $(x_1, y)$, $(x_2, y)$로 정의한다.어떠한 직사각형이 $x=i$에 있다는 것은 시작칸의 $x$좌표가 $i$라는 것이다.직사각형을 흰색/검은색으로 칠했다는 것은 시작칸을 흰색, 시작칸이 아닌 끝칸을 검은색으로 칠했다는 것이다.직사각형을 검은색/흰색으로 칠했다는 것은 시작칸을 검은색, 시작칸이 아닌 끝칸을 흰색으로 칠했다는 것이다. 1.1. 어떠한 그림이 2개의 히스토그램의 교집합으로 칠해질 필요충분조건을 구하자. 그림이 2개의 히스토그램의 교집합으로 표현된다고 하자.검은색 칸들은 위를..
SNUPC 2022 G번 수 만들기 문제 링크: https://www.acmicpc.net/problem/25613 25613번: 수 만들기 각 테스트 케이스마다 한 줄에 만들 수 있는 수의 개수를 998 244 353으로 나눈 나머지를 출력한다. www.acmicpc.net 0. 숫자들을 $a_1, a_2, \cdots, a_k$ 순으로 나열했다고 하자. 괄호를 적당히 넣어서 분수를 만들었다고 할 때, 다음을 관찰할 수 있다. $a_1$은 분자에 간다. $a_2$는 분모에 간다. $a_3, a_4, \cdots, a_k$는 분모/분자 어디에나 갈 수 있다. 3번째 관찰을 $a_i$부터 $a_k$까지 괄호를 씌우면 $a_{i+1}, \cdots, a_k$까지 분자에 있었으면 분모로, 분모에 있었으면 분모로 위치를 변경할 수 있기 때문이다...
ICPC 2019 Seoul Regional E번 Network Vulnerability 문제 링크: https://www.acmicpc.net/problem/17972 17972번: Network Vulnerability Your program is to read from standard input. The first line contains a positive integer n representing the number of intervals, where n ≤ 2,000. In the following n lines, each contains a pair of left and right endpoints of an interval. You may assume tha www.acmicpc.net 240402 수정) 3에서 풀이가 틀렸다. $(l_{i+1}, l_i)$에 구간이 존재하는 것..
ICPC 2019 Seoul Regional C번 Islands 문제 링크: https://www.acmicpc.net/problem/17970 17970번: Islands Your program is to read from standard input. The input starts with a line containing an integer n (5 ≤ n ≤ 100,000), where n is the number of villages in each island. The villages are numbered from 1 to n. In the following two lines, each line contains www.acmicpc.net 1. 정점의 순서들이 가지는 성질에 대해서 알아보자. 하나의 섬에서 $1$번째 정점부터 $i$번째 정점까지 하나의 구간을 ..