아인타, 빈타, 그리고 씬타
문제 링크: 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)$모든 ..
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$까지 분자에 있었으면 분모로, 분모에 있었으면 분모로 위치를 변경할 수 있기 때문이다...
