79brue의 PS 블로그

시즌 4가 시작된 뒤 처음으로 생긴 랜덤 마라톤이다. 이번 주에 걸린 문제들은 다음과 같다.A. He is offside!몇 년 전에 타 OJ에서 풀었던 문제가 여기에 다시 나올 거라고는 상상도 못했다…지문에 쓰여 있는 것을 그대로 구현하면 된다. 수비수 중 두 번째로 골문에 가까운 사람과 공격수 중 가장 골문에 가까운 사람의 거리를 비교하면 된다. 정렬을 이용하면 구현이 편해진다.B. Brain Fold (Hard)IPSC 문제 역시 여기서 볼 거라고 생각하지 못했다. IPSC는 따지자면 외국에서 열리는 구데기컵 같은 개념이라, 랜덤 디펜스에서 만났을 때 썩 유쾌하지는 않다. (문제 자체가 구데기라기보다는, 뭔가 상당히 애드혹적인 느낌의 문제들도 많이 출제되는 것 같다.) 종이접기 문제들을 어느 정도 ..

조이슥 맛 셋을 하나 돌고 싶었는데, 리프가 추천해줘서 풀었다. 딱히 시간을 재면서 풀진 않았다.https://codeforces.com/contest/1943A. MEX Game 1Alice가 $[0, v]$ 사이의 모든 값을 가져갈 조건이 다음과 동치임을 보일 수 있다.$[0, v]$ 사이의 모든 값이 1개 이상 있다.$[0, v]$ 사이의 값 중 $a_1, \cdots, a_n$에 정확히 1개 있는 값이 최대 하나이다.증명은 단순하다. 저 조건을 만족하기만 하면, Alice는 현재 남아 있는 가장 적은 값을 가져가는 그리디로 모든 값을 가져갈 수 있다. 반면, 저 조건을 만족하지 않는다면, Bob은 정확히 1개 있는 여러 개의 값 중 하나를 소진해 Alice가 해당 수를 가져가지 못하게 막을 수 있..

BOJ 15986. &+ +&먼저 모든 $A[i] \wedge B[j]$의 합을 구해 보자. $Acnt[x]$를 $A$의 원소들 중 $2^x$의 비트가 $1$인 것의 개수라고 하고, 마찬가지로 $Bcnt[x]$를 정의하자. 비트별로 따로따로 생각하면 답이 $\sum Acnt[i] Bcnt[i] 2^i$임을 쉽게 알 수 있다. 다음으로 모든 $A[i] + B[j]$의 AND 값을 구해 보자. 이것도 역시 비트별로 생각할 것이다. 즉, 모든 $A[i] + B[j]$ 값에 $2^i$의 비트가 켜져 있는지를 검사할 것이다. 먼저 $i=0$일 때부터 시작해 보자. $2^0$의 비트가 켜져 있으려면 $A$는 모두 홀수, $B$는 모두 짝수거나 그 반대여야 한다. $i$가 더 커지는 경우에는 어떻게 검사할 수 있을까..

문제 링크15685B+alpha를 짜고 풀었다. 지금까지 해본 다양한 문제풀이들 중에서도 기억에 남을 정도로 힘들었던 것 같다. 자력솔한 문제 중에서는 최소 3위 안에 드는 것 같다. 해싱을 쓰는 쉬운 풀이가 있다고 하니 구현할 생각이 있다면 그쪽 풀이를 써 보도록 하자. 문제를 요약하면 다음과 같다.그래프 $G$에서 간선 $k$개를 지워서 이분 그래프로 만들 수 있는 $k$의 최솟값 $k_{min}$이 $2$ 이하인지 판정한다.$k_{min}$이 $2$ 이하라면, 그래프 $G$에서 $k_{min}$개의 간선을 지워 이분 그래프로 만드는 경우의 수를 출력한다.접근 방식이 문제에서는 $k_{min}$이 $0$, $1$, $2$인지 각각에 대해서만 판정하면 된다. 따라서 $k_{min}$의 값이 이들 중에 ..

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..

D5 이상 랜덤 ICPC 문제 10개를 뽑았다.3. Big Brother반평면 교집합 기초 연습문제다. 어딘가에서 라이브러리를 긁어와서 풀었다.7. Fair Distribution$N=1$인 경우는 사전에 N을 출력하고 종료하는 식으로 처리해 주자. $N \ge 2$일 때를 생각해 보자. 각 빌딩의 높이를 $G_i + R_i x$ 꼴로 표현할 수 있다. $x$는 임의의 양의 정수가 될 수 있다. 그런데 모든 빌딩의 높이를 $lcm(R_1, \cdots, R_N)$의 배수만큼 올려놓고 생각할 수 있어서 사실상 $x$는 모든 정수라고 생각해도 문제없다. 일단 처음에 신경써야 할 것은 $gcd(R_1, R_2, \cdots, R_N)$의 값이다. 만약 배분한 $G$값의 합의 차이가 이 $gcd$ 값의 배수가 ..

올해 KAIST에서 열린 런 봄 대회에 검수진으로 참여했다. 처음으로 온사이트 대회를 검수해 보아서 신기한 경험을 많이 해 본 것 같다. 풍선을 달아 주거나 온사이트 대회 안내 등의 경험을 처음으로 해 봐서 재미있었다. 문제 셋은 전체적으로 좋지만, (특히 어려운 문제의 경우) 구현량이 많아서 제한 시간 내에 풀기 힘든 셋이었다고 생각한다. G는 특히 기억에 남는 문제로 최근에 본 문제들 중에서도 매우 좋은 편에 속하는 것 같다.A. RUN 수뺄 수 있는 가장 큰 수를 그리디하게 빼면 된다. 증명이 생각보다 어려운데, 재미있으니 스스로 해 볼 가치가 있다고 생각한다.B. 문자열과 쿼리$f(i, j, k)$의 값을 더하는 것으로 생각하지 말고, 새로운 함수 $g(i, j)$를 정의하자. $f(i, j, k..

그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..