79brue의 PS 블로그

문제 링크 엄청 유명한 수학 루비 문제인데, 난 수학에 자신이 없어서 딱히 건드려 본 적이 없었다. 오늘따라 루비를 풀어보고 싶어서 잡기 시작했다. 엄밀한 증명이나 풀이 위주로 적는다기보다는 생각의 흐름 위주로 기록을 남겨 보려고 한다.예제 분석일단 문제의 풀이에 대한 감이 전혀 잡히지 않아서 예제를 가지고 놀아 봤다. 간단한 랜덤화 시뮬레이션 코드를 짜서 시행의 선택에 따라 어떤 결과가 나오는지를 알아보았다. 다양한 방법으로 시행을 해 본 결과, 다음과 같은 두 가지 추측을 하게 되었다.여러 가능한 시행 중 어떤 것을 선택하더라도, 모든 수를 $0$ 이상으로 만드는 데 필요한 시행 횟수가 같다.어떤 방법으로 시행을 완성하더라도 최종 상태가 동일하다.이 관찰을 통해 어떤 수열 $A$에 대해 이 문제의 답..

BOJ 17670. 난난을 $N$조각으로 잘랐을 때, 마지막 난을 누가 가져가야 할 지 생각해 보자. 각 사람별로, 왼쪽부터 $P_i$만큼의 난을 먹었을 때 전체 행복도의 $\frac{i}{N}$만큼을 얻게 되는 $P_i$를 구하자. 이때 $P_{N-1}$이 가장 큰 사람에게 맨 오른쪽 조각을 $P_{N-1}$부터 잘라서 주면, 마지막 사람은 $\frac{1}{N}$만큼의 행복도를 얻고, 남은 사람들 모두 남은 조각들로 최소 $\frac{N-1}{N}$의 행복도를 얻을 수 있는 상태가 된다. 이제 여기서 다음 사람은 아직 난을 받지 못한 사람 중 $P_{N-2}$가 가장 큰 사람에게 주고, 그 다음 사람은 $P_{N-3}$이 가장 큰 사람에게 주고, 이를 반복하면 모든 사람에게 항상 조건을 만족하도록 난..

세 번째 마라톤이다. 앞 두 마라톤을 전부 풀었지만 문제의 난이도는 거의 비슷한 것 같다. P3보다 높은 난이도가 나오기를 기다리고 있는데, 아직은 때가 아닌 것 같다.A. Поиски다음 세 가지 케이스로 나눌 수 있다.$x>0$: 문자열에 L과 R이 둘 다 존재하거나, R의 개수가 $x$ 이하면 가능하다.$x L과 R이 둘 다 존재하거나, L의 개수가 $-x$ 이하면 가능하다.$x=0$: 문자열에 L과 R이 둘 다 존재하면 가능하다.#include using namespace std;typedef long long ll;string str;int lc, rc;int main(){ cin >> str; for(char c: str){ if(c=='L') lc++; e..

두 번째 마라톤이다. 1주차 마라톤을 올솔했지만 2주차 문제들의 난이도 역시 거의 비슷한 (조금 더 낮은) 분포로 나왔다. 어째서인지 A번 문제는 나오지 않았는데, 다른 분들이 주신 정보에 의하면 해당 난이도대에 추천할 만한 문제가 없어서 일어나는 현상이라고 한다. 문제가 하나 적었음에도 E번과 H번을 잘못 읽어서 자체 하드 모드에 빠졌다… E는 불편도를 최댓값 대신 합으로 생각해서 30분 이상 고민하다가 결국 문제를 다시 읽고 틀렸음을 파악했다. H번은 선장의 배가 무조건 "중심으로 align된다"를 "align된다"로 읽어서 접근 방향 자체를 완전히 말려 (사실 이건 실력 이슈가 더 큰 것 같긴 하다) 역시 오랜 시간을 허비했다. 아직 solved.ac 웹페이지가 안 돌아와서 별조각은 못 받았다. 받..

시즌 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}$의 값이 이들 중에 ..