1. Cowmpetency먼저 $(a_j, h_j)$ 쌍들이 어떤 형태로 제시될 수 있는지를 생각해 보자. 만약 $a_1 h_1$이면 너무 당연히 모순이 된다. $h_1 사실 상황이 저렇게 되면 $(a_2, h_2)$ 쌍은 존재하는 게 큰 의미가 없다. 그래서 그런 쌍들을 모두 제거하고 생각해도 된다. 이제 남은 쌍들을 생각해 보면, $(a_j, h_j)$ 쌍들을 $a_j$의 크기 순으로 정렬했을 때, 무조건 $h_j \le a_{j+1}$임을 알 수 있다. (여기까지 확인하는 것은 정렬을 한 번 해놓고 적당한 처리로 $O(n \log n)$에 할 수 있다. 자세한 내용은 코드를 참고하자.) 이제 각각의 $(a_j, h_j)$ 쌍에 대해 생각해 보자. $mx[i]$를 $c_1, c_2, \cdots,..
1. Bovine Acrobatics문제를 읽어 보면 다음과 같은 그리디한 전략이 통함을 알 수 있다.각 타워의 맨 아래에 있는 소들의 집합 $S$를 관리하자. $S$의 크기는 항상 $m$ 이하여야 한다.크기가 작은 소부터 차례로 보면서, 다음 과정을 반복한다. 현재 보는 소의 크기를 $x$라고 하자.만약 $S$ 안에 $x - k$ 이하의 크기를 가진 소가 있다면, 그 소 아래에 현재 소를 넣을 수 있다. 즉, $S$에서 $x - k$ 이하의 크기를 가진 원소 하나를 빼고, $x$를 넣는다.그렇지 않고, $|S| $\min S > x-k$이고, $|S| = m$이라면, 이 소는 사용할 수 없다.위 과정과 같이 하면 사용한 소의 개수가 최대가 된다.증명을 하진 않았지만 직관적으로 위 방법에서 소를 더 집어..
USACO 2024-2025 February (Silver)
1. The Best Lineup사전순으로 최대인 것을 찾는 문제는 보통 그리디한 접근 방식을 가지는 경우가 많다. 사전순으로 최대라는 개념은 정의 자체가 그리디하기 때문이다. 그래서 이 문제의 경우도 앞부터 채워나가면서 가장 큰 수를 그리디하게 넣으려는 접근이 성립한다. 문제에 주어진 연산을 최대 한 번 해서 만들 수 있는 결과 수열을 유효한 수열이라고 하자. 맨 앞 자리에서부터 최대한 큰 수 넣기를 시도해 보면서, 해당 수열이 유효한지를 계속 확인하면 된다. (어떤 수열이 유효하면 그 접두사들도 모두 유효해야 하므로...) 최종 답의 형태를 보면, 큰 수 여러 개가 같은 것이 여러 개끼리 나오면서, 점점 줄어드는 형태를 상상할 수 있다. 따라서 $v$를 $N$부터 $1$까지 내리면서, $v$를 최대 ..
USACO 2024-2025 January (Silver)
1. Cow Checkups$a_i = b_j$인 모든 $(i, j)$ 쌍에 대해, $A$의 구간을 적당히 뒤집었을 때 $a_i$가 $j$번 위치에 오도록 하는 경우의 수를 구해 보자. $i = j$인 경우는 따로 처리해 준다. 뒤집은 구간이 $i$번을 포함하지 않는 경우가 있고, 뒤집은 구간의 가운데에 $i$번 위치가 있는 경우가 있다. $i \neq j$인 경우를 보자. 편의상 $i 구간 $[i, j]$의 경우 이 조건을 만족하고,여기서 양옆을 같은 길이만큼 늘려도 이 조건을 만족한다.따라서 이러한 구간이 총 $\min(i, n-j+1)$개 있음을 알 수 있다. 이것을 모든 $i$와 $j$에 대해 계산하면 $O(n^2)$ 정도 시간 복잡도에 문제를 해결할 수 있다. 시간 복잡도를 줄이기 위해서는 $a..
앞으로 다양한 대회(OI / ICPC)에 나온 기출문제 풀이들을 써 보려고 한다. 한국어 자료가 없는 대회들을 위주로 작성할 것 같고, 한국어 자료가 있더라도 쓰고 싶으면 쓸 것 같다.이 게시글은 둘러보기 카테고리에 작성되어 있으며, 아래 목록의 모든 글들은 문제풀이 - 기출문제 카테고리에 작성된다.대회 정렬 순서는 중요도 순서 + 비슷하면 내가 좋아하는 순서대로 정렬했고, 같은 대회 내에서는 최근 문제부터 정렬해 두었다.이미 써둔 글이 있더라도 퀄리티가 조금 떨어진다고 생각하는 글들은 수록하지 않았다. 그 외에 빠뜨린 게 있는 것 같다면 댓글로 제보를 부탁합니다.IOI KOI USACO2024 - 2025December ContestSilverJanuary ContestSilverFebruary Con..
1. Cake Game$N$이 짝수라는 조건을 놓치기 쉽다. 먼저 이 부분을 잘 읽어야 한다. 게임을 직접 손으로 돌려보며 다양한 관찰을 해 보면, 몇 가지 관찰을 할 수 있다. 대부분의 경우, 선공이 가운데쯤에 어떤 "큰 뭉치"를 만들고, 해당 뭉치를 마지막까지 안 빼앗기는 게 최적임을 관찰할 수 있다. 이것을 조금 더 엄밀하게 쓰면 다음과 같다: 맨 첫 턴에, 선공은 가운데의 두 더미를 합친다. 그리고, 후공이 양쪽 끝 더미 중 하나를 가져갈 경우, 선공은 자신의 더미가 가운데에 오도록 가운데 근처에서 적당히 다시 합친다. 이렇게 하면 선공은 자신이 만든 큰 더미를 끝까지 지켜 가져갈 수 있고, 후공은 그 더미를 제외한 나머지 더미를 모두 가져가게 된다. 더미를 만드는 과정에 따라, 마지막에 남는 더..
옛날 함수컵에 나온 인터랙티브 문제로, 굉장히 쉬운 문제이지만 흥미로워서 글을 써 본다.링크문제$N$개의 스위치가 일렬로 있고, 스위치 사이에 각각 하나씩 총 $N-1$개의 전구가 있다. $N$은 짝수다.처음에는 모든 전구가 꺼져 있다. A와 B 두 사람이 게임을 한다. 총 $N/2$턴으로 진행되며, 각 턴은 다음과 같이 진행된다.먼저 A가 아직까지 안 눌러진 스위치 하나를 누른다.다음으로 B가 아직까지 안 눌러진 스위치 하나를 누른다.이때 두 스위치 사이의 전구들은 켜짐/꺼짐 순서가 반전된다.B는 마지막에 켜진 전구가 꺼진 전구보다 더 많아야 이긴다. B의 필승 전략을 찾아라.풀이풀이는 굉장히 전형적인 유형이지만, 처음 보는 경우 굉장히 신기한 유형이다.스위치들을 인접한 것끼리 두 개씩 묶자. 이러면 ..
뭔가 백준 솔브 수가 높거나 주변 사람들이 많이 얘기를 하는데 나는 뭔지 잘 모르겠는 문제들이 많았고, 이런 문제들을 좀 모아서 풀어 보기로 했다. 첫 번째 문제는 유명한 세그비츠 문제인 수열과 쿼리 25로 정했다. 세그비츠 문제를 아예 안 풀어 본 건 아닌데, 이 문제는 안 풀어봤었고, 뭔가 나만 모르는 웰노운 같아서 풀어봤다. 링크접근이런 특이한 형태의 세그먼트 트리를 쓰는 문제는 일반적으로 적당한 퍼텐셜 함수를 만들어서 푸는 경우가 많다. 가장 대표적인 예시가 수열과 쿼리 26인데, 이 경우 min 연산이나 max 연산을 할 때 서로 다른 수의 개수가 줄어드는 경우가 많다는 사실을 이용해 퍼텐셜 함수를 정의한다. 이 문제도 비슷한 생각을 할 수 있다. 비트 연산의 성질상,and 1이나 or 0은 원..